[CTSC2006]歌唱王国 Tags:题解 题意 链接:在空串后不断随机添加字符,直到出现串\(S_i\)为止.求最终串的期望长度.\(\sum |S_i|\le 5*10^6\) 题解 以下内容来自\(YMD\)的2018年集训队论文 很奇怪的生成函数题: 令\(f[i]\)表示串最终长度为\(i\)的概率,\(g[i]\)表示到达长度\(i\)还没有结束的概率.分别对应生成函数\(F(x),G(x)\).最后要求的就是\(F'(1)\)(求导,相当于每个概率都乘上了指数也就是长度,变成了期

[CTSC2006]歌唱王国Singleland Time Limit: 30 Sec Memory Limit: 162 MB Description 在歌唱王国,所有人的名字都是一个非空的仅包含整数1~n的字符串.王国里生活着一大群咕噜兵,他们靠不停的 歌唱首领--牛人酋长们的名字来获取力量.咕噜兵每一次歌唱过程是这样的:首先,他从整数生成器那儿获得一 个数字,然后花一个时间单位将此数字唱出来,如果他发现某个牛人酋长的名字已经被歌唱出来(即此名字是歌唱 序列的一个连续子串),那么这次歌唱过程

题解 读错题了,是最后留下一个牛人首长歌颂他,和其他人没有关系,t就相当于数据组数 结论题,具体可看 https://www.zhihu.com/question/59895916/answer/196874145 最后一个求导(1 - z)不拆,最后代入1的时候会消掉,就得出了这个结论 代码 #include <iostream> #include <cstdio> #include <vector> #include <algorithm> #inclu

题面 传送门 给定一个长度为\(L\)的序列\(A\).然后每次掷一个标有\(1\)到\(m\)的公平骰子并将其上的数字加入到初始为空的序列\(B\)的末尾,如果序列B中已经出现了给定序列\(A\),即\(A\)是\(B\)的子串,则停止, 求序列\(B\)的期望长度.\(L ≤ 10^5\) 题解 不知道概率生成函数是什么的可以看看这篇文章,题解也在里面了 //minamoto #include<bits/stdc++.h> #define R register #define fp(i,a

传送门 orz ymd 考虑构造生成函数:设\(F(x) = \sum\limits_{i=0}^\infty f_ix^i\),其中\(f_i\)表示答案为\(i\)的概率:又设\(G(x) = \sum\limits_{i=0}^\infty g_ix^i\),其中\(g_i\)表示经过了\(i\)步之后还没有结束的概率.那么答案显然是\(F'(1)\). 考虑在还没有结束的序列之后加入一个字符,那么有可能结束也有可能没有结束,即\(F(x) + G(x) = xG(x) + 1\). 两边

传送门 这题\(\mathrm{YMD}\)去年就讲了,然而我今年才做(捂脸) 考虑生成函数,设\(f_i\)表示最终串长为\(i\)的概率,其概率生成函数为\(F(x)=\sum f_ix^i\),设\(g_i\)表示做到长度为\(i\)没结束的概率,其概率生成函数为\(G(x)=\sum g_ix^i\),那我们要求的就是\(F'(1)\) 考虑他们之间的关系,首先如果在一个没有结束的串后接一个字符,那么这个串可能结束也可能没结束,可以得到\(F(x)+G(x)=xG(x)+1\),两边对\

题目传送门 Desctiption 见题面. Solution 人类智慧... 考虑这样一个赌博游戏,现在有一个猴子,它随机从 \(1\sim n\) 中选一个打出来.现在有若干个赌徒,他们一开始都有 \(\$1\),现在有一个字符串 \(S\),赌徒在第一次押猴子会打 \(S_1\),如果赢了就回收 \(\$ n\) ,如果输了就可以滚他的蛋了.如果赌徒赢了就继续押猴子会打 \(S_2\),如果赢了就回收 \(\$ n^2\) ,否则就可以滚蛋了.以此类推,并且猴子每打一个字都会新加进来一个赌

洛谷题面传送门 PGF 入门好题. 首先介绍一下 PGF 的基本概念.对于随机变量 \(X\),满足 \(X\) 的取值总是非负整数,我们即 \(P(v)\) 表示 \(X=v\) 的概率,那么我们定义 \(X\) 的概率生成函数为 \(F(x)=\sum\limits_{n\ge 0}P(n)x^n\).较一般的生成函数有所不同的是,对于概率生成函数 \(F(1)=1\) 必然成立,因为 \(X\) 取遍所有值的概率之和为 \(1\).此外,\(X\) 的期望 \(E(X)\) 也可表示为 \

[BZOJ1152]歌唱王国(生成函数,KMP) 题面 BZOJ 洛谷 题解 根据\(YMD\)论文来的QwQ. 首先大家都知道普通型生成函数是\(\displaystyle \sum_{i=0}^{\infty}a_ix^i\),类似的定义概率生成函数\(\displaystyle F(x)=\sum_{i=0}^\infty P(X=i)x^i\).其中\(P(X=i)\)表示\(X\)这个随机变量为\(i\)的概率. 那么我们可以知道几个结论:\(\displaystyle F(1)=\s

[题解]歌唱王国(概率生成函数+KMP)+伦讲的求方差 生成函数的本质是什么呀!为什么和It-st一样神 设\(f_i\)表示填了\(i\)个时候停下来的概率,\(g_i\)是填了\(i\)个的时候不停下的来的概率,规定\(f_0=g_0=1\) 两个生成函数是 \[ G(x)=\sum g(i)x^i \\ F(x)=\sum f(i)x^i \] 可以得到一些关系: 在后面随意加上一个字符 \[ xG(x)+1=F(x)+G(x) \] 直接强行接上原串: \[ x^LG(x)(\dfrac

概率生成函数\(g(x)=\sum_{i\geq 0}t_ix^i\),\(t_i\)表示结果为\(i\)的概率 令\(f(x)\)表示i位表示串结束时长度为i的概率,\(G(x)\)表示i位表示串长度为i时不结束的概率 有如下关系 \[①:f(x)+g(x)=1+g(x)x \] 意义:\(f(x)+g(x)\)即为串长达\(i\)位的概率,即\(i-1\)位不结束的概率 定义一个字符串的border为一个既为它前缀又为它后缀的非空串 定义\(b_i\)表示\([[1,2,\cdots,i]\

题面 概率生成函数 对于菜鸡博主来说好难啊 其一般形式为$F(x)=\sum\limits_{i=0}^∞[x==i]x_i$,第i项的系数表示离散变量x取值为i的概率 一般的两个性质:$F(1)=1,E(x)=F'(1)$ 这里用$F(x)$表示结束时的串长的概率生成函数,$G(x)$表示到长度到达...而串未结束的概率生成函数,字符串长为len,那么有: ①$F(x)+G(x)=x*G(x)+1$,含义是长度达到x的概率:左边就是字面意思,右边$x*G(x)$表示x-1时未结束的概率,然后加

题目传送门 分析: 这道题很神仙,我们给出低配版解法和高配版解法2333 低配版: 首先知道这样一个公式...(证明去高配版) 当一个字符串S其中S [ 1 , i ] = S [ n - i + 1 , n ]时,则称S [ 1 , i ]为S的一个border Ans[n]=sigma( S [ 1, i ]为S的border) m ^ i 嗯... 有了这个之后,我们就可以kmp或者hash求解了 但是,hash只能处理取到S的答案,而kmp可以做到处理出所有S前缀的答案 这里就用kmp(

正题 题目链接:https://www.luogu.com.cn/problem/P4548 题目大意 \(t\)次询问,给出一个长度为\(m\)的串\(S\)和一个空串\(T\),每次在\(T\)后面随机加入\(1\sim n\)的字符,直到\(T\)中出现\(S\)为止,求期望次数. \(1\leq n\leq 10^5,t\leq 50,1\leq m\leq 10^5\) 解题思路 对于一个随机的数字\(X\),它的概率生成函数是一个形如 \[F(x)=\sum_{i=0}^\infty

(可以参考hdu4652,因此推导过程比较省略) 类似的定义$f_{i}$和$g_{i}$,同样去插入$len$个字符,但注意到并不是任意一个位置都可以作为结尾,$i+j$可以作为结尾当且仅当$s[0,j)=s[len-j,j)$ 令两者生成函数分别为$F(x)$和$G(x)$,则有$G(x)=\sum_{i\in S}m^{i}\frac{F(x)}{x^{i}}$,其中$S=\{i|s[0,i)=s[len-i,len)\}$(根据定义$len\in S$),可以通过kmp或哈希求出 答案即

Search GO 说明:输入题号直接进入相应题目,如需搜索含数字的题目,请在关键词前加单引号 Problem ID Title Source AC Submit Y 1000 A+B Problem 10983 18765 Y 1036 [ZJOI2008]树的统计Count 5293 13132 Y 1588 [HNOI2002]营业额统计 5056 13607 1001 [BeiJing2006]狼抓兔子 4526 18386 Y 2002 [Hnoi2010]Bounce 弹飞绵羊 43

看了jcvb的WC2015交流课件.虽然没懂后面的复合逆部分,但生成函数感觉受益良多. 指数生成函数 集合中大小为 i 的对象的权值是 \( a_i \) ,该集合的生成函数是 \( \sum\limits_{i>=0} \frac{a_i}{i!} x^i \) 一个重要式子: \( \sum\limits_{i=0}^{\infty} \frac{A^i}{i!} = e^A \) .其中 A 可以是一个多项式. 对于有标号对象的计数.可以“拼接”,即 “大小为 i 的集合的带标号方案” 与

本文由 埃姆杰 翻译.未经许可,禁止转载!英文出处:Future Insights. 内容提要 使用许多独立组件构建应用程序的想法并不新鲜.Web Component的出现,是重新回顾基于组件的应用程序开发模式的好时机.我们可以从这个过程中受益,了解如何使用现有技术完成目标,并且在未来做出自己的前端Web应用. 什么是组件? 软件开发是一个语义丰富(术语通常不止一个意思)的领域.很显然,这里的“组件”是一个很泛的称呼,所以有必要指明我们想要表达的,在前端Web应用的语言环境中的意思. 前端Web

Time Limit: 60 Sec  Memory Limit: 512 MBSubmit: 505  Solved: 204 Description 巧克力王国里的巧克力都是由牛奶和可可做成的.但是并不是每一块巧克力都受王国人民的欢迎,因为大家都不喜 欢过于甜的巧克力.对于每一块巧克力,我们设x和y为其牛奶和可可的含量.由于每个人对于甜的程度都有自己的 评判标准,所以每个人都有两个参数a和b,分别为他自己为牛奶和可可定义的权重,因此牛奶和可可含量分别为x 和y的巧克力对于他的甜味程度即为ax

描述 河蟹王国有一位河蟹国王,他的名字叫羊驼.河蟹王国富饶安定,人们和谐相处.有一天,羊驼国王心血来潮,想在一部分人中挑出最和谐的人.于是,羊驼国王将他的子民排成了一列(==!!b汗~好长呀).每个人都有一个初始的和谐值.羊驼国王每次会选择一个区间[L,R],这个区间中和谐值最大的人就是国王选出的人.而且,在某一时间,区间[L’,R’]里的人会变得熟悉,因此他们每个人的和谐值都会上升一个相同的值C.羊驼国王想知道,对于每一次选择,他选出的最大和谐值是多少. 输入格式 第一行是一个数N(1<=N<