【CF666C】Codeword
题意：一开始有一个字符串s，有m个事件，每个事件形如：
1.用一个新的字符串t来替换s
2.给出n，问有多少个长度为n的小写字母组成的字符串满足包含s作为其一个子序列？答案$\mod 10^9+7$
$m,n,\sum |t|\le 10^5$
题解：有一个结论：答案只与n和|s|有关，与s到底是什么无关。我们只考虑s在母串中第一次出现的位置。设$|s|=k$，假如s的每个字符出现的位置分别是$p_1p_2...p_k$，则对于$i\in [1,k]$，$(p_{i-1},p_i)$之间的字符都不能是$s_i$，所以这些位置都有25种可能。然后我们就可以将我们发现的结论形式化的写出来了。我们枚举$p_k$的位置，则有：
$ans=\sum\limits_{i=k}^{n}C_{i-1}^{k-1}\alpha^{n-i}(\alpha-1)^{i-k}$
但是如果我们每次都暴力计算的话复杂度难以接受。不过我们发现本质不同的|s|只有$\sqrt n$种，所以我们去重，然后将式子改写为：
$ans=\alpha^{n}\sum\limits_{i=k}^nC_{i-1}^{k-1}\alpha^{-i}(\alpha-1)^{i-k}$
我们对于每个|s|都预处理出后面那些东西，便可做到$O(1)$回答询问，时间复杂度$O(m\sqrt n)$。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=100010;
const ll P=1000000007;
int m,N,tot;
struct node
{
int n,len,org;
}p[maxn];
char str[maxn];
ll jc[maxn],ine[maxn],jcc[maxn],q[maxn],q1[maxn],qi[maxn],s[maxn],ans[maxn];
bool cmp(const node &a,const node &b)
{
return a.len<b.len;
}
inline ll c(int a,int b)
{
if(a<b) return 0;
return jc[a]*jcc[a-b]%P*jcc[b]%P;
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();
return ret*f;
}
int main()
{
m=rd(),scanf("%s",str),N=100000;
int i,j,a=strlen(str),b;
for(i=1;i<=m;i++)
{
if(rd()==1) scanf("%s",str),a=strlen(str);
else b=rd(),p[++tot].len=a,p[tot].n=b,p[tot].org=tot;
}
ine[0]=ine[1]=jc[0]=jc[1]=jcc[0]=jcc[1]=1;
for(i=2;i<=N;i++) jc[i]=jc[i-1]*i%P,ine[i]=P-(P/i)*ine[P%i]%P,jcc[i]=jcc[i-1]*ine[i]%P;
for(q[0]=q1[0]=qi[0]=i=1;i<=N;i++) q[i]=q[i-1]*26%P,q1[i]=q1[i-1]*25%P,qi[i]=qi[i-1]*ine[26]%P;
sort(p+1,p+tot+1,cmp);
for(i=1;i<=tot;i++)
{
a=p[i].len,b=p[i].n;
if(a!=p[i-1].len)
{
memset(s,0,sizeof(s[0])*a);
for(j=a;j<=N;j++) s[j]=(s[j-1]+q1[j-a]*qi[j]%P*c(j-1,a-1))%P;
}
ans[p[i].org]=q[b]*s[b]%P;
}
for(i=1;i<=tot;i++) printf("%lld\n",ans[i]);
return 0;
}