小购物网站建设,东莞做网站推广,临沂自助建站软件,广东省建设执业资格注册中心官方网站正题
题目链接:https://www.luogu.com.cn/problem/P4548 题目大意 ttt次询问#xff0c;给出一个长度为mmm的串SSS和一个空串TTT#xff0c;每次在TTT后面随机加入1∼n1\sim n1∼n的字符#xff0c;直到TTT中出现SSS为止#xff0c;求期望次数。 1≤n≤105,t≤50,1≤m≤10…正题
题目链接:https://www.luogu.com.cn/problem/P4548 题目大意
ttt次询问给出一个长度为mmm的串SSS和一个空串TTT每次在TTT后面随机加入1∼n1\sim n1∼n的字符直到TTT中出现SSS为止求期望次数。
1≤n≤105,t≤50,1≤m≤1051\leq n\leq 10^5,t\leq 50,1\leq m\leq 10^51≤n≤105,t≤50,1≤m≤105 解题思路
对于一个随机的数字XXX它的概率生成函数是一个形如 F(x)∑i0∞P(Xi)xiF(x)\sum_{i0}^\infty P(Xi)x^iF(x)i0∑∞P(Xi)xi F′(x)∑i1∞P(Xi)ixi−1F(x)\sum_{i1}^\infty P(Xi)ix^{i-1}F′(x)i1∑∞P(Xi)ixi−1 不难发现数字XXX的期望值就是E(X)F′(1)E(X)F(1)E(X)F′(1) 然后还有一个不知道有啥用的XXX的方差大概就是离散程度 V(X)F′′(1)F′(1)−F′(1)2V(X)F(1)F(1)-F(1)^2V(X)F′′(1)F′(1)−F′(1)2
这题的话设两个生成函数F(x)F(x)F(x)表示停止时间XXX的概率生成函数还有一个G(x)G(x)G(x)表示没有停止时间的概率不是概率生成函数具体地 G(x)∑i0∞P(iX)xiG(x)\sum_{i0}^\infty P(iX)x^iG(x)i0∑∞P(iX)xi 然后我们就有两个式子 xG(x)1F(x)G(x)xG(x)1F(x)G(x)xG(x)1F(x)G(x) 这个式子的含义很好理解在还没有结束的序列后面加入一个字符要么结束了要么没结束。 (xn)mG(x)∑i1m(xn)m−ibiF(x)\left(\frac{x}{n}\right)^mG(x)\sum_{i1}^m \left(\frac{x}{n}\right)^{m-i}b_iF(x)(nx)mG(x)i1∑m(nx)m−ibiF(x) bib_ibi表示iii是否是串SSS的一个borderborderborder这个式子的意思就是说在直接在未结束的TTT后面插入一个SSS此时可能提前结束。
然后这两个式子怎么用呢我们对第一个式子求导就有 G(x)G′(x)F′(x)G′(x)⇒F′(x)G(x)G(x)G(x)F(x)G(x)\Rightarrow F(x)G(x)G(x)G′(x)F′(x)G′(x)⇒F′(x)G(x) 也就是说我们要求的E(X)F′(1)G(1)E(X)F(1)G(1)E(X)F′(1)G(1) 然后直接带入第二个式子因为有F(1)1F(1)1F(1)1所以 (1n)mG(1)∑i1m(1n)m−ibiF(1)\left(\frac{1}{n}\right)^mG(1)\sum_{i1}^m \left(\frac{1}{n}\right)^{m-i}b_iF(1)(n1)mG(1)i1∑m(n1)m−ibiF(1) ⇒G(1)∑i1mnibi\Rightarrow G(1)\sum_{i1}^mn^ib_i⇒G(1)i1∑mnibi 用KMPKMPKMP求出bbb数组即可。
时间复杂度O(Tm)O(Tm)O(Tm) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e510,P1e4;
ll T,m,n,pw[N],a[N],nxt[N];
signed main()
{scanf(%lld%lld,m,T);pw[0]1;for(ll i1;iN;i)pw[i]pw[i-1]*m%P;while(T--){scanf(%lld,n);ll ans0;for(ll i1;in;i)scanf(%lld,a[i]);for(ll i2,j0;in;i){while(ja[j1]!a[i])jnxt[j];j(a[j1]a[i]);nxt[i]j;}for(ll in;i;inxt[i])(anspw[i])%P;printf(%04lld\n,ans);}return 0;
}
