BJ 集训测试13 钢琴

http://www.elijahqi.win/archives/2827
题意给一个序列（<=1e6）给一个字符集大小为n且<=100 每次1/n的概率生成其中一个字符 求每个前缀生成的期望

公式：dp[i]=dp[next[i]]+n^i;

证明

#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i = x ;i <= y; ++ i)
#define repd(i,x,y) for(register int i = x  ; i >= y; -- i)
using namespace std;
typedef long long ll;inline char gc(){static char now[1<<16],*S,*T;if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}return *S++;
}
template<typename T>inline void read(T&x)
{char c;x = 0;do { c = gc(); }while(!isdigit(c));do { x = x * 10 + c - '0'; c = gc(); }while(isdigit(c));
}
const int OUT_LEN = 1024 * 1024;
char obuf[OUT_LEN], *oh = obuf;
inline void write_char(char c) {if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;*oh++ = c;
}template<class T>
inline void W(T x) {static int buf[30], cnt;if (x == 0) write_char('0');else {if (x < 0) write_char('-'), x = -x;for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;while (cnt) write_char(buf[cnt--]);}
}
inline void flush() {fwrite(obuf, 1, oh - obuf, stdout);
}const int mod = 1e9 + 7,M = 1e6+50;
int n,m,nxt[M],a[M],f[M];void get()
{int p = 0;rep(i,2,m){while(p && a[p + 1] != a[i]) p = nxt[p];if(a[p + 1] == a[i]) ++p;nxt[i] = p;}
}int main()
{read(n); read(m);rep(i,1,m) read(a[i]);get();ll k = n;rep(i,1,m){f[i] = (1ll*f[nxt[i]] + k) % mod;k = k * n % mod;}rep(i,1,m) W(f[i]),write_char('\n');flush();return 0;
}

如果不想背公式可以像我一样n*m 卡卡常数即可

设dp[i]表示第i个前缀的期望生成次数 那么我该怎么转移来呢 首先我随机生成一个 那么至少期望步数是+1 那么我剩下部分怎么办我就枚举字符集 然后算一下我从上一次匹配这个到我这里期望差是多少 即可 所以可以先kmp 但是kmp直接暴力跳跃next会出问题所以先像AC自动机一样预处理出这个转移然后每次可以o(1)做了

dp[i]=1+(1/n)sigma(j!=i){dp[i]-dp[trans[i][j]]}

#include<cstdio>
#include<cctype>
#include<algorithm>
#define N 1000010
#define mod 1000000007
using namespace std;
inline char gc(){static char now[1<<16],*S,*T;if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}return *S++;
}
inline int read(){int x=0,f=1;char ch=gc();while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();}while(isdigit(ch)) x=x*10+ch-'0',ch=gc();return x*f;
}
const int OUT_LEN = 1024 * 1024;
char obuf[OUT_LEN], *oh = obuf;
inline void write_char(char c) {if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;*oh++ = c;
}
template<class T>
inline void W(T x) {static int buf[30], cnt;if (x == 0) write_char('0');else {if (x < 0) write_char('-'), x = -x;for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;while (cnt) write_char(buf[cnt--]);}
}
inline void flush() {fwrite(obuf, 1, oh - obuf, stdout);
}
int dp[N],n,m,a[N],nxt[N],trans[N][101];
inline int calc(const int &a,const int &b){return a-b<=0?a-b+mod:a-b;
}
int main(){freopen("t1.in","r",stdin);
//  freopen("t1.out","w",stdout);n=read();m=read();int k=0;a[1]=read();dp[1]=n;for (int i=1;i<=n;++i) if (i==a[1]) trans[0][i]=1;for (int i=2;i<=m;++i){a[i]=read();while(k&&a[i]!=a[k+1]) k=nxt[k];if (a[i]==a[k+1]) ++k;nxt[i]=k; trans[i-1][a[i]]=i;dp[i]=dp[i-1]+n>=mod?dp[i-1]+n-mod:dp[i-1]+n;for (int j=1;j<=n;++j){if (j==a[i]) continue;trans[i-1][j]=trans[nxt[i-1]][j];int kk=trans[i-1][j];int tmp=calc(dp[i-1],dp[kk]);dp[i]=dp[i]+tmp>=mod?dp[i]+tmp-mod:dp[i]+tmp;}}for (int i=1;i<=m;++i) W(dp[i]),write_char('\n');flush();return 0;
}