GYM103119B. Boring Problem【期望+AC自动机+高斯消元】

GYM103119B. Boring Problem

简要题意 ：

给定 $n$ 个长度都为 $m$ 的字符串 $T_1,T_2,\dots ,T_n$。这些字符串（包括之后出现的字符串）都只包含前 $k$ 个小写字母。对于给定的字符串 $S$，考虑以下过程：

1. 如果 $S$ 包含某个 $T_j$ 作为子串，则结束过程。
2. 否则，在 $S$ 之后以 $p_i$ 的概率添加第 $i$ 个小写字母，然后回到第 1 步。

定义 $f(S;T,p)$ 为过程结束时 $S$ 的期望长度。

给定字符串 $R$，对每个 $i=1,2,\dots ,|R|$，求出 $f(R[:i];T,p)$ 对 $10^9+7$ 取模后的结果。

• $1\le n\le 100$。
• $1\le n?m\le 10000$。
• $1\le k\le 26$。
• $1\le |R|\le 10000$。

分析 ：

建出 AC 自动机，$f_i$ 表示在点 $i$ 的答案，对于每个点 $i$ 都有方程 $f_i=1+{\sum }_j{P}_j\times f_{next(i,j)}$ ，当然叶子节点的方程直接等于 0 了。

由于这是一个 AC 自动机，所以如果一个点的父亲只有它一个儿子，那么它的 $f$ 值就可以用深度比它小的若干个点的 $f$ 值表示出来。考虑 保留一些关键点，剩下的点的 $f$ 值用关键点的值来表示。可以发现我们只需要保留 其父亲的儿子个数超过 $1$ 的点，由于叶子节点的个数为 $n$ ，所以保留的点的个数也是 $O(n)$ 的，高斯消元即可。

具体来说就是原本有 $nm$ 个点，如果一个点的父亲只有它一个儿子，就能用它父亲的方程解出它的值（如果把深度小于它的点的值看为已知的话）。所以我们把关键点的值看成未知数，把非关键点按深度从小到大，依次用其父亲的方程解出非关键点的值。现在每一个点都用关键点个的未知数表示出来了，考虑我们还没有用到的方程，一定还剩关键点个（因为用了非关键点个），于是 $O(n)$ 个未知数 $O(n)$ 个方程，高斯消元求出关键点的 $f$ 值，然后代入非关键点。时间复杂度 $O(nmk+n^3)$ ，可以通过此题。

#include <bits/stdc++.h> 
#define N 20004
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int n,m,k,num=1;
ll p[30],inv[30],inv100; 
char s[N],t[N];
int nxt[N][27],son[N],fail[N],fa[N];
ll ksm(ll x,ll y){
    ll res=1;while(y){
    if(y&1) res=res*x%mod;x=x*x%mod; y>>=1;}return res;
}
void add(int &x,int y){
    if(nxt[x][y]){
     x=nxt[x][y]; return; }nxt[x][y]=++num,son[x]++,fa[num]=x,x=num;
}
queue<int> q;
void init(){
    fail[1]=1;for(int i=1;i<=k;i++){
    if(!nxt[1][i]) nxt[1][i]=1;else fail[nxt[1][i]]=1,q.push(nxt[1][i]);}int x;while(!q.empty()){
    x=q.front(); q.pop();for(int i=1;i<=k;i++){
    if(!nxt[x][i]) nxt[x][i]=nxt[fail[x]][i];else fail[nxt[x][i]]=nxt[fail[x]][i],q.push(nxt[x][i]);}}
}
ll f[N][516],id[N],g[516][516],cnt,res[N];
void build(){
    id[1]=++cnt; f[1][1]=1;for(int i=2;i<=num;i++) if(son[fa[i]]>1) id[i]=++cnt,f[i][id[i]]=1;q.push(1); int x,y,z=0; ll invv;while(!q.empty()){
    x=q.front(); q.pop();if(!id[x]){
    for(int i=0;i<=cnt;i++) f[x][i]=f[fa[x]][i];f[x][0]=(f[x][0]+mod-1)%mod;for(int i=1;i<=k;i++){
    if(nxt[fa[x]][i]==x){
     invv=inv[i]; continue; }y=nxt[fa[x]][i];for(int j=0;j<=cnt;j++) f[x][j]=(f[x][j]-p[i]*f[y][j]%mod+mod)%mod;}for(int i=0;i<=cnt;i++) f[x][i]=f[x][i]*invv%mod;}for(int i=1;i<=k;i++) if(fa[nxt[x][i]]==x) q.push(nxt[x][i]);}for(int x=1;x<=num;x++){
    if(son[x]==1) continue; ++z;for(int i=0;i<=cnt;i++) g[z][i]=f[x][i];if(son[x]){
    for(int i=1;i<=k;i++){
    y=nxt[x][i];for(int j=0;j<=cnt;j++) g[z][j]=(g[z][j]-p[i]*f[y][j]%mod+mod)%mod;}g[z][0]=(g[z][0]-1+mod)%mod;}}for(int i=1;i<=cnt;i++){
    x=i; while(!g[x][i]) x++;for(int j=0;j<=cnt;j++) swap(g[x][j],g[i][j]);invv=ksm(g[i][i],mod-2);for(int j=i+1;j<=cnt;j++){
    ll l=g[j][i]*invv%mod;for(int r=0;r<=cnt;r++) g[j][r]=(g[j][r]-g[i][r]*l%mod+mod)%mod;}}for(int i=cnt;i>=1;i--){
    g[i][0]=g[i][0]*ksm(g[i][i],mod-2)%mod,g[i][i]=1;for(int j=i-1;j>=1;j--){
    ll l=g[j][i];for(int r=0;r<=cnt;r++)g[j][r]=(g[j][r]-g[i][r]*l%mod+mod)%mod;}}g[0][0]=mod-1;for(int i=1;i<=num;i++)for(int j=0;j<=cnt;j++)(res[i]+=f[i][j]*(mod-g[j][0])%mod)%=mod;
}
int main(){
    
// freopen("test.in","r",stdin);cin>>n>>m>>k;inv100=ksm(100,mod-2);for(int i=1;i<=k;i++) cin>>p[i],p[i]=p[i]*inv100%mod,inv[i]=ksm(p[i],mod-2);int now;for(int i=1;i<=n;i++){
    scanf("%s",s+1); now=1;for(int i=1;i<=m;i++) add(now,s[i]-'a'+1);}init();build();scanf("%s",t+1); n=strlen(t+1);now=1; bool tag=0;for(int i=1;i<=n;i++){
    now=nxt[now][t[i]-'a'+1];if(!res[now]) tag=1;if(tag) cout<<i<<'\n';else cout<<(res[now]+i)%mod<<'\n';}
}