题目
题目链接：http://poj.org/problem?id=2778
给出 \(n\) 个长度不超过 \(10\) 且仅由 \(\operatorname{A,C,T,G}\) 组成的串 \(s_i\)，问有多少个长度为 \(m\) 的仅由 \(\operatorname{A,C,T,G}\) 串不存在任意一个子串为 \(s\)。
\(n\leq 10,m\leq 2\times 10^9\)。
吐槽
从星期五开始写，差不多 \(40min\) 过了样例，但是交到 POJ 上一直 WA。
周六发现是矩阵乘法中两个元素相乘可能超过 int 的范围，改了之后一直 TLE。
周日早上心态大崩开始和标程对拍，发现完全没有问题。一度怀疑是 POJ 评测环境的问题。但是标程本地需要 \(70ms\)，我的代码本地 \(300ms\)。感觉不至于在 POJ 上能慢个 \(700ms\) 吧所以就没管。
晚上优化了矩阵乘法的常数，代码降到了 \(70ms\)，终于在 POJ 上过了。跑了 \(500+ms\)。。。
POJnb。
思路
首先建立 AC 自动机，定义一个点 \(x\) 有 \(end[x]=1\) 当且仅当满足以下条件之一：
- 存在一个串在点 \(x\) 结束。
- 存在一个串在点 \(x\) 的祖先结束
- \(end[fail[x]]=1\)。
那么如果 \(end[x]=1\)，那么最终的串就不能存在一个子串等于根到 \(x\) 所构成的字符串。
那么可以把加字母的过程看做在 AC 自动机上一个点在移动，假设要加入一个字母 \(a\)，那么这个点 \(p\) 就移动到 \(c[p][a]\) 的位置。
那么一个串是合法的当且仅当这一个点没有经过 \(end=1\) 的点。
由于 AC 自动机上的点不超过 \(n\times |S|\leq 100\) 个，可以用矩阵乘法优化。
时间复杂度 \(O(n^3|S|^3\log m)\)。
代码
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=110,M=5,MOD=100000;
int n,m,Q,ans;
char s[N];
inline int ID(char ch)
{
if (ch=='A') return 1;
if (ch=='C') return 2;
if (ch=='T') return 3;
return 4;
}
struct Matrix
{
int a[N][N];
Matrix() { memset(a,0,sizeof(a)); }
}mat;
struct ACA
{
int tot,c[N][M],fail[N];
bool end[N];
inline void ins(char *s)
{
int len=strlen(s),p=0;
for (int i=0;i<len;i++)
{
int id=ID(s[i]);
if (!c[p][id]) c[p][id]=++tot;
p=c[p][id];
}
end[p]=1;
}
inline void build()
{
queue<int> q;
for (int i=1;i<=4;i++)
if (c[0][i]) q.push(c[0][i]);
while (q.size())
{
int u=q.front(); q.pop();
if (end[fail[u]]) end[u]=1;
for (int i=1;i<=4;i++)
if (c[u][i])
{
fail[c[u][i]]=c[fail[u]][i];
q.push(c[u][i]);
if (end[u]) end[c[u][i]]=1;
}
else c[u][i]=c[fail[u]][i];
}
}
inline void updmat()
{
for (int i=0;i<=tot;i++)
for (int j=1;j<=4;j++)
if (!end[i] && !end[c[i][j]])
mat.a[i][c[i][j]]++;
}
}AC;
Matrix operator *(Matrix a,Matrix b)
{
Matrix c;
for (int i=0;i<=AC.tot;i++)
for (int j=0;j<=AC.tot;j++)
for (int k=0;k<=AC.tot;k++) //这个地方 AC.tot 写成 N 就会 T。。。
c.a[i][j]=(c.a[i][j]+1LL*a.a[i][k]*b.a[k][j])%MOD;
return c;
}
inline Matrix fpow(Matrix a,int k)
{
Matrix b;
b.a[0][0]=1;
for (;k;k>>=1,a=a*a)
if (k&1) b=b*a;
return b;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
scanf("%s",s);
AC.ins(s);
}
AC.build(); AC.updmat();
mat=fpow(mat,m);
for (int i=0;i<=AC.tot;i++)
ans=(ans+mat.a[0][i])%MOD;
printf("%d\n",ans);
return 0;
}