# 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

$F(x)+G(x)=1+xG(x)$

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:

$F'(x)+G'(x)=xG'(x)+G(x)$

Take$$x=1$$You can:

$E(x)=F'(1)=G(1)$

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} \]

const int MAXN=1e5;const int BS=333337;const int HMOD=1004535809;const int MOD=10000;void print(int x){	static int d;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=1);i<=MAXN;i++) pwn[i]=1ll*pwn[i-1]*n%MOD;	for(int i=(pw=1);i<=MAXN;i++) pw[i]=1ll*pw[i-1]*BS%HMOD;	while(qu--) solve();	return 0;}