题目链接
题意
给定(N)个词根，每个长度不超过(5). 问长度不超过(L(Llt 2^{31}))，只由小写字母组成的，至少包含一个词根的单词，一共可能有多少个？
思路
状态（AC自动机）及状态转移（矩阵快速幂）的想法基本与上一题poj 2778 DNA Sequence 状态及状态转移 AC自动机 矩阵快速幂类似。
不同处有两点：
上一题是问不包含任何一个危险子串的有多少个，这一题是问至少包含一个，直接按上题做法求得答案用总数减去它即可。
**错误做法**：只保留能够通过$fail$指针到达某个单词结尾状态的节点，将其他节点全部删去。
上题中之所以需要删去所有能够到达危险状态的点，是因为它们绝对不能作为中间状态而存在。而本题中不能通过fail指针到达单词结尾的点是可以作为中间状态而存在的，毕竟是要借助它们才能到达结尾状态的。
上一题是求指定长度的，本题是求长度小于等于(L)的。
记关系矩阵为(A)，则上一题是求(A^n)，而这一题是求$$I+A+A2+...+An$$这也是可以用矩阵快速幂做的，
记(S_k=I+A+A^2+...+A^{k-1})，则有
[pmatrix{A^kcr S_k}=pmatrix{A&0\I&I}pmatrix{A^{k-1}\S_{k-1}}$$就又可以欢乐地用矩阵快速幂做了~
// 此外，从中得到启示，等比数列求和也都可以这么做了，比如这道题里面的$26+26^2+...+26^l$，记$T_k=26+26^2+...+26^{k-1}$，则有
$$pmatrix{a^k\T_k}=pmatrix{26&0\1&1}pmatrix{a^{k-1}\T_{k-1}}]
但是只能说是自娱自乐一下...。
// 此外，本题的输出是要求模(2^64)，于是可以直接用(unsigned long long)，输出注意是(\%I64u)
Code
#include <bits/stdc++.h>
#define SIZE 26
#define maxn 32
using namespace std;
typedef unsigned long long ULL;
int cnt;
typedef struct {
ULL mat[maxn<<1][maxn<<1];
void init(ULL x, int cnt){
memset(mat, 0, sizeof(mat));
for(int i=0; i<cnt; i++) mat[i][i] = x;
}
void print(int cnt) const {
for (int i = 0; i < cnt; ++i) {
for (int j = 0; j < cnt; ++j) printf("%lld ", mat[i][j]); printf("
");
}
}
} Matrix;
Matrix m0, m1, m2;
ULL add(ULL a, ULL b) { return a + b; }
ULL mul(ULL a, ULL b) { return a * b; }
Matrix mulm(const Matrix& a, const Matrix& b, int cnt) {
Matrix temp;
temp.init(0, cnt);
for (int i = 0; i < cnt; ++i) {
for (int j = 0; j < cnt; ++j) {
for (int k = 0; k < cnt; ++k) temp.mat[i][j] = add(temp.mat[i][j], mul(a.mat[i][k], b.mat[k][j]));
}
}
return temp;
}
Matrix addm(const Matrix& a, const Matrix& b, int cnt) {
Matrix temp;
temp.init(0, cnt);
for (int i = 0; i < cnt; ++i) for (int j = 0; j < cnt; ++j) temp.mat[i][j] = add(a.mat[i][j], b.mat[i][j]);
return temp;
}
Matrix poww(Matrix m, ULL n, int cnt) {
Matrix a = m, ret;
ret.init(1, cnt);
while (n) {
if (n & 1) ret = mulm(ret, a, cnt);
a = mulm(a, a, cnt);
n >>= 1;
}
return ret;
}
int son[maxn][SIZE], fail[maxn], tot;
ULL mat[maxn][maxn];
bool flag[maxn];
void insert(char* s, int len) {
int p = 0;
for (int i = 0; i < len; ++i) {
if (son[p][s[i]-'a'] == -1) {
flag[++tot] = 0;
for (int j = 0; j < SIZE; ++j) son[tot][j] = -1;
son[p][s[i]-'a'] = tot;
}
p = son[p][s[i]-'a'];
}
flag[p] = true;
}
void build() {
queue<int> que;
fail[0] = 0;
for (int i = 0; i < SIZE; ++i) {
if (son[0][i] == -1) son[0][i] = 0;
else {
fail[son[0][i]] = 0;
que.push(son[0][i]);
}
++mat[0][son[0][i]];
}
while (!que.empty()) {
int x = que.front(); que.pop();
for (int i = 0; i < SIZE; ++i) {
if (son[x][i] == -1) son[x][i] = son[fail[x]][i];
else {
fail[son[x][i]] = son[fail[x]][i];
flag[son[x][i]] |= flag[fail[son[x][i]]];
que.push(son[x][i]);
}
++mat[x][son[x][i]];
}
}
}
void init() {
flag[tot = 0] = 0;
memset(mat, 0, sizeof mat);
memset(m0.mat, 0, sizeof m0.mat);
memset(m1.mat, 0, sizeof m1.mat);
memset(m2.mat, 0, sizeof m2.mat);
for (int i = 0; i < SIZE; ++i) son[0][i] = -1;
}
int n, l;
char s[10];
int mp[maxn];
void work() {
init();
for (int i = 0; i < n; ++i) {
scanf("%s", s);
insert(s, strlen(s));
}
build();
cnt = 0;
for (int i = 0; i <= tot; ++i) if (!flag[i]) mp[cnt++] = i;
for (int i = 0; i < cnt; ++i) {
for (int j = 0; j < cnt; ++j) {
m0.mat[i][j] = mat[mp[i]][mp[j]];
}
}
for (int i = 0; i < cnt; ++i) m0.mat[i+cnt][i] = m0.mat[i+cnt][i+cnt] = 1;
Matrix fnl = poww(m0, l, cnt<<1);
for (int i = cnt; i < (cnt<<1); ++i) {
for (int j = 0; j < cnt; ++j) {
m1.mat[i-cnt][j] = fnl.mat[i][j];
m2.mat[i-cnt][j] = fnl.mat[i][j+cnt];
}
}
Matrix ret = addm(mulm(m1, m0, cnt), m2, cnt);
ULL sub = 0;
for (int i = 0; i < cnt; ++i) sub = add(sub, ret.mat[0][i]);
Matrix mm;
mm.mat[0][0] = 26, mm.mat[0][1] = 0, mm.mat[1][0] = 1, mm.mat[1][1] = 1;
Matrix mmfnl = poww(mm, l, 2);
ULL sum = add(mul(26, mmfnl.mat[1][0]), mmfnl.mat[1][1]);
ULL ans = add(sum, -sub);
printf("%I64u
", ans);
}
int main() {
while (scanf("%d%d", &n, &l) != EOF) work();
return 0;
}