题目传送门
分析：
这道题很神仙，我们给出低配版解法和高配版解法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（相信hash很简单（大雾））
那么我们设 f [ i ] 为递推到第 i 位的答案
我们先处理出fail数组
那么S[ 1 , i ]的border的集合就是S[ 1 , i ]本身加上S[ 1 , fail [ i ] ]的border集合
所以得出递推式
f [ i ] = f [ fail [ i ] ] + m ^ i
算到 n 就是答案了
高配版：
首先我们要知道生成函数的表达式：
F(i) = sigma( i = 0...+∞) Ai * x ^ i
我们从生成函数定义概率生成函数，其中代价为 i 的事件发生的概率为 Ai：
那么我们可以知道：
F(1) = 1
相当于x取1时，F(1)代表的是所有情况的概率和，其值为1是显然正确的，就是事件本身
然后我们考虑期望代价E(x)
E(x) = sigma( i = 0...+∞)Ai * i
因为当 i 为0时不做贡献，所以 i 可以从1开始
接下来有一个有趣的事情，我们把F(x)求导
F'(x)=sigma( i =1...+∞)Ai * i * x ^ ( i - 1 )
我们再取F'(1) = sigma( i = 1...+∞)Ai * i
与E(x)做一下比较，我们惊奇地发现：
E(x) = F'(1)
这是巧合吗？还是冥冥之中的必然？
这也说明了，概率和期望是有必然的联系的
于是我们进入正题
设函数F(x)表示结束时长度为 i 的概率，G(x)表示长度到了 i 还没有结束的概率
那么我们得到这个等式：
F(x) + G(x) = 1 + G(x) * x
分为每一位考虑，其实就是整个递推的过程，你在i - 1位没有结束的概率，就是你在 i 位结束和在 i 位没结束的概率和
这个式子记为1式
然后我们考虑求解。。。
我们往G(x)上强行加 (1/m x)^n 这个串一定会结束，然而这个串可能提前结束，因为之前的串里可能有S的border
我们枚举border的长度
首先定义ai=0或1 代表S[ 1 , i ]是否为S的border
于是可以得到这个式子。。。
G(x) * ( 1/m * x) ^ n = sigma(i=1...n) ai * F(x) * (1/m * x) ^ ( n - i )
不好说这个式子，但感（hu）性（luan）分析一下挺正确的2333
这只Darknesses笨笨的，讲不清楚
把这个式子记为2式
然后我们大♂力推式子
首先对1式求导
F'(x) + G'(x) = G(x) + G'(x) * x
要求F'(1)诶。。。
直接取吧2333
然后惊奇地发现
F'(1)=G(1)
第二个再取1试试
G(1) * (1/m) ^ n = sigma(i=1...n) ai * F(1) * (1/m) ^ ( n - i )
因为F(1)=1，我们再把(1/m) ^ n除过去
G(1)=sigma(i=1...n) ai * m ^ i
所以Ans[n]=E(x)=F'(1)=G(1)=sigma( S[ 1 , i ]为S的border ) m^i
得证了。。。
呵呵呵。。。
生成函数真神仙。。。
数学太菜了2333
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<queue>
#include<iostream>
#define maxn 1000005
#define MOD 1000000007
using namespace std;
inline int getint()
{
int num=0,flag=1;char c;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
while(c>='0'&&c<='9')num=num*10+c-48,c=getchar();
return num*flag;
}
int n,m;
long long a[maxn],pw[maxn];
long long ans;
long long fail[maxn],f[maxn];
int main()
{
m=getint(),n=getint(),f[0]=1;
for(int i=1;i<=n;i++)a[i]=getint(),f[i]=f[i-1]*m%MOD;
fail[0]=-1;
for(int i=2;i<=n;i++)
{
for(int j=fail[i-1];j>=0;j=fail[j])
if(a[i]==a[j+1]){fail[i]=j+1,(f[i]+=f[j+1])%=MOD;break;}
}
for(int i=1;i<=n;i++)printf("%lld\n",f[i]);
}
View Code
代码不能直接AC哦，它输出的式S所有前缀的答案2333
代码短，证明还真长呢2333