bzoj 1152 歌唱王国

Posted on | Edited on | Views:

概率生成函数 + kmp.

概率生成函数: 无情的复读机器人,通过生成函数的方法简化运算.

定义概率生成函数 $F(x)=\sum_{i=0}^{\infty} P(X=i) x^i$ ,其中 $P(X=i)$ 表示随机变量 $X$ 为 $i$ 的概率.

显然有 $F(1)=\sum_i P(X=i)=1$ .

期望 $E(X)=\sum_i i\cdot P(X=i)=F’(1)$ .

方差 $Var(X)=E(x^2)-E(x)^2=\sum_i i^2\cdot P(X=i)-(F’(1))^2=F’’(1)+F’(1)-(F’(1))^2$ .

记字符集大小为 $m$ ,字符串长度为 $n$ .

设 $f_i$ 表示结束时随机序列的长度,其概率生成函数为 $F(x)$ .

设 $g_i$ 为随机序列长度达到 $i$ 还没结束的概率,其普通生成函数为 $G(x)$ .

如果在一个未结束的序列后加一个数字,可能结束,也可能没结束, $1$ 是初始时序列为空的情况.
$$
F(x)+G(x)=1+G(x)\cdot x \quad (1)
$$
如果在一个未结束的序列后加上给定的序列,则一定会结束,也可能没添加完就结束了,此时已有序列一定是 border .

设 $a_i$ 表示给定序列的前缀 $i$ 是否为它的 border .
$$
G(x)\cdot (\frac{1}{m}x)^n=\sum_{i=1}^n a_i\cdot F(x)\cdot (\frac{1}{m}x)^{n-i}
\quad(2)
$$
要求的是 $F’(1)$ ,将 $(1)$ 式两边对 $x$ 求导后代入 $x=1$ ,得到
$$
F’(x)+G’(x)=x\cdot G’(x)+G(x) \\
F’(1)=G(1)
$$
将 $x=1$ 代入 $(2)$ 式,得到
$$
G(1)=\sum_{i=1}^n a_i\cdot F(1) \cdot m^i \\
F’(1)=\sum_{i=1}^n a_i\cdot m^i
$$
于是只需用 kmp 判断给定序列的每个前缀是不是它的 border 就可以了.

用 %04d 可以达到题目要求的输出效果,当然也可以自己写一下输出.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
typedef unsigned long long ull;
const int P=1e4;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
void inc(int &a,int b)
{
	a=add(a,b);
}
int mul(int a,int b)
{
	return a * b % P;
}
int n,m,T,pw[MAXN],s[MAXN],fail[MAXN];
int main()
{
	m=read(),T=read();
	pw[0]=1;
	for(int i=1;i<=100000;++i)
		pw[i]=mul(pw[i-1],m);
	while(T--)
	{
		int ans=0;
		n=read();
		for(int i=1;i<=n;++i)
			s[i]=read();
        for(int i=2;i<=n;++i)
        {
            int j=fail[i-1];
            while(j && s[j+1]!=s[i])
            	j=fail[j];
            if(s[j+1]==s[i])
            	++j;
            fail[i]=j;
        }
        for(int i=n;i;i=fail[i])
        	inc(ans,pw[i]);
        printf("%04d\n",ans);
	}
	return 0;
}