lyzlyz?lyzlyz!

看到这套题的时候，我作出如下的条件反射：

然而这次却没有人能膜拜了。。。

T1

有一只猴子在电脑上随机地打字，每次只可能打0或1，问第一次打出一个特定串S时猴子打的字符串的期望长度。

令nxt[i]表示在第i位失配时最多可匹配的前缀，f[i]表示匹配到|S|-i+1位时字符串的期望长度。

那么显然f[|S|]=0且：

[tex]f[i]=\frac{f[i+1]+f[nxt[i]]}{2}[/tex]

这就可以用高斯消元来解决，然而O(n³)的复杂度并不能获得满分。

通过移项可以得到：

[tex]f[i+1]=2*f[i]-f[nxt[i]]-2[/tex]

那么显然f[i]可以用xf[0]+y来表示，那么观察等式就可以发现x恒=1。

只要递推求出-y就是最终的答案了！

T2

有一个抽奖游戏，有N₁次单抽机会和N₂次11连抽机会。每抽一次1%抽到UR，9%抽到SR，90%抽到R，若11连抽都抽到R那么最后一张10%变成UR，90%变成SR。求用完所有抽奖机会抽到UR数量小于M的概率。

发现单抽和11连抽是互相独立的，那么可以分开考虑。

令f[i][j]表示i次单抽抽到j张UR的概率，那么：f[1][0]=0.99 f[1][1]=0.01

[tex]f[i][j]=f[i-1][j]*f[1][0]+f[i][j-1]*f[1][1][/tex]

显然f[i]是f[i-1]与f[1]的卷积，即f[i]=f[1]ⁱ，可以用类似快速幂（还是矩阵乘法？我也不知道）的方法+FFT解决。

对于11连抽可以dp处理出抽到1~11张UR的概率，那么同样自乘N₂次即可。

最后对两个自乘得到的数组再进行一次FFT，就可以统计答案了。

T3

NPC问题，考验选手的模拟和暴搜剪枝能力。

这样一道JB题没有任何营养，所以拒绝订正。

【Codes】

#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
const int M=1000010;
const int mod=1000000007;
int n,i,j;
char s[M];
int next[M],Next[M];
ll f[M];
ll Abs(ll x){
	if (x>0)return x;else return -x;
}
int main(){
    scanf("%s",s);
    n=strlen(s);
    for (i=n;i;i--)s[i]=s[i-1];
    i=1;j=0;
    while (i<=n){
        if (!j||s[i]==s[j]){i++;j++;next[i]=j;}
            else j=next[j];
    }
    for (i=1;i<=n;i++){
        Next[i]=next[i];
        while (Next[i]&&(s[i]-'0')^1!=s[Next[i]]-'0')Next[i]=next[Next[i]];
    }
    for (i=0;i<n;i++)Next[i]=Next[i+1];
    f[0]=0;
    for (i=1;i<=n;i++)f[i]=(2*f[i-1]-f[Next[i-1]]-2-mod)%mod;
	printf("%lld\n",Abs(f[n]));
}

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
typedef long double ld;
using namespace std;
const int M=1000010;
const ld pi=acos(-1);
int N1,N2,n,i,j;
ld orz[110][110];
struct cp{ld x,y;}f[M],F[M],g[M],ans[M],Ans[M],cur[M];
cp operator +(cp a,cp b){
	return (cp){a.x+b.x,a.y+b.y};
}
cp operator -(cp a,cp b){
	return (cp){a.x-b.x,a.y-b.y};
}
cp operator *(cp a,cp b){
	return (cp){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};
}
void fft(cp *a,int n,int flag){
    for (int i=n>>1,j=1;j<n;j++){
        if (i<j)swap(a[i],a[j]);
        int k=n>>1;
        for (;i&k;i^=k,k>>=1);i^=k;
    }
    for (int m=2;m<=n;m<<=1){
        cp w=(cp){cos(2*pi*flag/m),sin(2*pi*flag/m)};
        cur[0]=(cp){1,0};
        for (int i=1;i<(m>>1);i++)cur[i]=cur[i-1]*w;
        for (int i=0;i<n;i+=m)
            for (int j=i;j<i+(m>>1);j++){
                cp u=a[j],v=a[j+(m>>1)]*cur[j-i];
                a[j]=u+v;
                a[j+(m>>1)]=u-v;
            }
    }
}
int main(){
	scanf("%d%d%d",&N1,&N2,&n);
	orz[0][0]=1;
	for (i=1;i<=11;i++){
		orz[i][0]=orz[i-1][0]*0.99;
		for (j=1;j<=i;j++)orz[i][j]=orz[i-1][j]*0.99+orz[i-1][j-1]*0.01;
	}
	for (i=1;i<=11;i++)F[i].x=orz[11][i];
	ld rp=1;
	for (i=1;i<=11;i++)rp=rp*0.9;
	F[1].x+=rp*0.1;
	for (i=1;i<=11;i++)F[0].x+=F[i].x;
	F[0].x=1-F[0].x;
	f[0].x=0.99;f[1].x=0.01;
	int m=N1+N2*11,N=1;
	while (N<m)N<<=1;
	ans[0].x=Ans[0].x=1;
	fft(ans,N<<1,1);
	fft(f,N<<1,1);
	fft(Ans,N<<1,1);
	fft(F,N<<1,1);
	while (N1){
		if (N1&1)for (i=0;i<N<<1;i++)ans[i]=ans[i]*f[i];
		for (i=0;i<N<<1;i++)f[i]=f[i]*f[i];
		N1>>=1;
	}
	while (N2){
		if (N2&1)for (i=0;i<N<<1;i++)Ans[i]=Ans[i]*F[i];
		for (i=0;i<N<<1;i++)F[i]=F[i]*F[i];
		N2>>=1;
	}
	for (i=0;i<N<<1;i++)ans[i]=ans[i]*Ans[i];
	fft(ans,N<<1,-1);
	ld ANS=0;
	for (i=0;i<n;i++)ANS+=ans[i].x/(N<<1);
	printf("%.3lf\n",(double)(ANS*100));
}