作文 题解

令$ss$为题中的重要串，$mm$为$ss$的长度，显然我们需要维护写出的字符串与$ss$的匹配。

考虑用 $\text{dp}\backslash text\{dp\}$ 来求解该题。令 $f_{i}f\_i$ 表示已经匹配到 $ss$ 的第 $ii$ 位时，在结束前匹配整个$ss$串的概率。由于 $ss$ 在第一次出现以后，就无需考虑后继的情况，那么边界条件就是 $f_m=1f\_m=1$，答案就是 $f_{0}f\_0$。

考虑状态$ii$接上句子$jj$的转移，设这个后继状态为$t{o}_{i,j}to\_\{i,j\}$：

1. 如果在接上句子$jj$的中途就出现了$ss$串整串，则$t{o}_{i,j}=mto\_\{i,j\}=m$；

2. 否则，令 $t{o}_{i,j}to\_\{i,j\}$ 就是接上 $jj$ 这个句子后，与 $ss$ 串匹配的长度。

则对于每个，可以从其所有后继状态中得到转移：

其中$00$为这一轮结束的概率。

预处理$t{o}_{i,j}to\_\{i,j\}$

可以考虑用$\text{kmp}\backslash text\{kmp\}$（自动机）维护，枚举串$jj$，依次接上每一位。

令$LL$表示出现的句子的总长，则暴力$\text{kmp}\backslash text\{kmp\}$的复杂度为 $O(m(nm+L))O(m(nm+L))$（因为在新接上串$jj$时，还要考虑前$ii$个字符的失配）；

而用$\text{kmp}\backslash text\{kmp\}$自动机维护的复杂度为$O(mL)O(mL)$。

求解$f_{i}f\_i$

对以上提到的转移，容易发现每个$ii$的后继$t{o}_{i,j}to\_\{i,j\}$构成的转移关系不具有拓扑序，即实际的转移可能是这种循环形式：

此时可以看成是以$f_{i}f\_i$为元的 $m+1m+1$ 元线性方程组，可以使用高斯消元进行求解，复杂度为$O(m^3)O(m^3)$。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

bool Mbe;
const int N=210,INF=1e9+10,P=1e9+7;

int n,m;
char s[N];
char t[1010][N];
int G[N][N],nxt[N][26],fail[N];
ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}

bool Med;
int main(){ 
	m=rd();
	rep(i,1,m) scanf("%s",t[i]+1);
	scanf("%s",s+1),n=strlen(s+1);
	rep(i,1,n) nxt[i-1][s[i]-'a']=i;
	rep(i,1,n) {
		rep(j,0,25) if(nxt[i][j]) fail[nxt[i][j]]=nxt[fail[i]][j];
		else nxt[i][j]=nxt[fail[i]][j];
	}
	rep(i,0,n-1) {
		rep(j,1,m) {
			int p=i;
			for(int k=1;t[j][k] && p!=n;++k) p=nxt[p][t[j][k]-'a'];
			G[i][p]++;
		}
	}
	rep(i,0,n-1) G[i][i]-=m+1,Mod2(G[i][i]);
	G[n][n]=G[n][n+1]=1;
	rep(i,0,n) {
		if(!G[i][i]){ 
			rep(j,i+1,n) if(G[j][i]) {
				swap(G[i],G[j]);
				break;
			}
		}
		assert(G[i][i]);
		ll inv=qpow(G[i][i]);
		rep(j,i,n+1) G[i][j]=G[i][j]*inv%P;
		rep(j,0,n) if(i!=j) drep(k,n+1,i) G[j][k]=(G[j][k]+1ll*(P-G[j][i])*G[i][k])%P;
	}
	printf("%d\n",G[0][n+1]);
}