挺神仙的一道题。
先建出来 (AC) 自动机，考虑在上面 (DP) ，设 (f[i]) 为在AC自动机上 (i) 节点时期望还有多长才能结束。
若 (i) 为一个字符串的结尾，则 (f[i]=0)
否则 (displaystyle f[i]=1+frac{f[tr[i][j]]}{26})
然后高斯消元解方程就行了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
using namespace std;
int T, n, len, tot = 1;
const int mod = 1e9 + 7, N = 205;
int ch[N][27], fail[N], isend[N], f[N][N];
char s[15];
LL ksm(LL a, LL b, LL mod)
{
LL res = 1;
for (; b; b >>= 1, a = a * a % mod)
if (b & 1)res = res * a % mod;
return res;
}
const int inv26 = ksm(26, mod - 2, mod);
void Insert()//AC自动机插入
{
int now = 1, c;
for (int i = 1; i <= len; ++i)
{
c = s[i] - 'a' + 1;
if (!ch[now][c])ch[now][c] = ++tot;
now = ch[now][c];
}
isend[now] = 1;
}
void build()
{
int x; queue<int>q;
fail[1] = 1;
for (int i = 1; i <= 26; ++i)
{
if (ch[1][i])q.push(ch[1][i]), fail[ch[1][i]] = 1;
else ch[1][i] = 1;
}
while (!q.empty())
{
x = q.front(); q.pop();
for (int i = 1; i <= 26; ++i)
{
if (ch[x][i])fail[ch[x][i]] = ch[fail[x]][i], q.push(ch[x][i]);
else ch[x][i] = ch[fail[x]][i];
}
}//上面是建fail指针
for (int i = 1; i <= tot; ++i)
{
f[i][i] = 1;
if (isend[i])continue;
f[i][0] = 1;
for (int j = 1; j <= 26; ++j)(f[i][ch[i][j]] += mod - inv26) %= mod;
}//建方程，注意0是等号左边，1~n是等号右边
}
void work()//高斯消元基本操作
{
for (int i = 1; i <= tot; ++i)
{
for (int j = i + 1; j <= tot; ++j)
if (!f[i][i] && f[j][i])swap(f[i], f[j]);
if (!f[i][i])continue;
int k = ksm(f[i][i], mod - 2, mod);
for (int j = 0; j <= tot; ++j)f[i][j] = (LL)f[i][j] * k % mod;
for (int j = 1; j <= tot; ++j)
{
if (j == i)continue;
int k = f[j][i];
for (int t = 0; t <= tot; ++t)((f[j][t] -= (LL)k * f[i][t] % mod) += mod) %= mod;
}
}
}
int main()
{
cin >> T;
while (T--)
{
memset(ch, 0, sizeof(ch)); memset(fail, 0, sizeof(fail)); memset(isend, 0, sizeof(isend)); memset(f, 0, sizeof(f));
tot = 1;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%s", s + 1); len = strlen(s + 1);
Insert();
}
build(); work();
printf("%lld
", (LL)f[1][0]*ksm(f[1][1], mod - 2, mod) % mod);//高斯消元求解
}
return 0;
}