Luo Valley P4548 - [CTSC2006] Singing Kingdom (Probability Generation Function)

Luo Valley

PGF entry into the door.

First introduce the basic concept of PGF. For random variables\(X\)\(X\)The value is always non-negative, we are\(P(v)\)\(X=v\)The probability, then we define\(X\)The probability generator function is\(F(x)=\sum\limits_{n\ge 0}P(n)x^n\). The more general generated function is different, and for probability generation functions\(F(1)=1\)It is inevitable because\(X\)The sum of the probability of all values\(1\). also,\(X\)Expectation\(E(X)\)It can also be expressed as\ (\ SUM \ LIMITS_ {n \ ge 0} p (n) · n = f ‘(1) \)\(X\)Various variant can also be expressed as\(F”(1)+F'(1)-F'(1)^2\)This can be fundamentally formula\(E(X^2)-E(X)^2\)Push it.

Next, consider this question. We set up\(P(x)\)Singing for just singing\(x\)Second probability,\(Q(x)\)In order to sing at least\(x+1\)Second probability, remember\(F(x),G(x)\)\(P(x),Q(x)\)PGF, then consider\(F,G\)What is connected? First:

\[P(x)+Q(x)=P(x-1)(x\ge 1)\]

This is because at least\(x\)The probability of seconds is just right\(x\)Second probability plus at least\(x+1\)Second probability.

The form of writing into PGF is


We will then from the name of the chief\(a\)The angle column. We consider a moment\(t\)If you sing\(t\)There have been no names of the chief after the second.Next\(len\)Just sing the name of the chief after the secondSo this probability is\ (Q (x) · \ dfrac {1} {n ^ {len}} \)Consider this probability\(P\)In the form of, we consider what the name of the chief is the first time, we assume that at the moment\(t+t’\)\(t’\in[1,len]\)So this probability is\ (P (t + t ‘) · \ DFRAC {1} {n ^ {len-t’}} \), but one\(t’\)​​Do not necessarily meet the conditions. It is not difficult to find that due to our temple\([t+1,t+len]\)The part of the sing is just the name of the chief, but because of our temple\(t+t’\)Always sing the name of the chief, so there must be\(a_i=a_{t-t’+i}\)\(a\)There is a length of length\(t’\)Border. If we set up\(b_i\)\(a\)Whether there is a length\(i\)Border, then

\ [Q (x) · \ dfrac {1} {n ^ {len}} = \ SUM \ LIMITS_ {T ‘= 1} ^ {len} B_ {t’} · p (t + t ‘) · \ DFRAC {1} {n ^ {len-t ‘}} \]

Write a PGF form is

\ [g (x) · (\ DFRAC {1} {n} x) ^ {len} = \ SUM \ LIMITS_ {T ‘= 1} ^ {len} B_ {t’} · f (x) · (\ DFRAC {1} {n} x) ^ {len-t ‘} \]

Consider combining two styles. Remember a child to guide:


Take\(x=1\)You can:


That is to say, equal\(G(1)\).

The answer will be substituted to the second style:

\ [g (1) \ DFRAC {1} {n ^ {len}} = \ SUM \ LIMITS_ {T ‘= 1} ^ {len} b_ {t’} · f (1) \ DFRAC { 1} {n ^ {len-t ‘}} \]

Combination\(F(1)=1\)You can:

\ [E (x) = \ SUM \ LIMITS_ {i = 1} ^ {len} B_i · n ^ {i} \]

Hash / KMP Ask Border, linearly solving the answer.

const int MAXN=1e5;const int BS=333337;const int HMOD=1004535809;const int MOD=10000;void print(int x){	static int d[6];int len=0;	while(x) d[len++]=x%10,x/=10;	while(len<4) d[len++]=0;	for(int i=3;~i;i--) printf("%d",d[i]);	printf("\n");}int n,qu,len,a[MAXN+5],pre[MAXN+5],suf[MAXN+5],pw[MAXN+5],pwn[MAXN+5];void solve(){	scanf("%d",&len);for(int i=1;i<=len;i++) scanf("%d",&a[i]);	for(int i=1;i<=len;i++) pre[i]=(pre[i-1]+1ll*a[i]*pw[i-1])%HMOD;	suf[len+1]=0;for(int i=len;i;i--) suf[i]=(1ll*suf[i+1]*BS+a[i])%HMOD;	int res=0;for(int i=1;i<=len;i++) if(pre[i]==suf[len-i+1]) res=(res+pwn[i])%MOD;	print(res);}int main(){	int qu;scanf("%d%d",&n,&qu);	for(int i=(pwn[0]=1);i<=MAXN;i++) pwn[i]=1ll*pwn[i-1]*n%MOD;	for(int i=(pw[0]=1);i<=MAXN;i++) pw[i]=1ll*pw[i-1]*BS%HMOD;	while(qu--) solve();	return 0;}