POJ2778
题意：只有四种字符的字符串（A, C, T and G），有M中字符串不能出现，为长度为n的字符串可以有多少种。
题解：在字符串上有L中状态，所以就有L*A（字符个数）中状态转移。这里自动机的build的hdu2222略有不同。
那一题中通过询问时循环来求she的he，但是如果he不能出现，she就算不是禁止的字符串也不可出现，所以在build的时候就记录所有不能出现的状态。
if (end[ fail[now] ]) end[now]++;
然后用一个矩阵F来记录可以相互到达的状态就OK了。
矩阵可以理解为用长度为1的字符串两个状态可以相互达到，而F=F^n，F[i][j]就是字符串长度为n时状态i到状态j的路径。
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <queue>
#include <set>
using namespace std; const int N = ;
const int A = ;
const int M = ;
const int MOD = ; typedef vector<int> vec;
typedef vector<vec> mat; mat mul(mat &A, mat &B)
{
mat C(A.size(), vec(B[].size()));
for (int i = ; i < A.size(); ++i) {
for (int k = ; k < B.size(); ++k) {
for (int j = ; j < B[].size(); ++j) {
C[i][j] = (C[i][j] + (long long)A[i][k] * B[k][j]) % MOD;
}
}
}
return C;
} // A^n
mat pow(mat A, int n)
{
mat B(A.size(), vec(A.size()));
for (int i = ; i < A.size(); ++i)
B[i][i] = ;
while (n > ) {
if (n & ) B = mul(B, A);
A = mul(A, A);
n >>= ;
}
return B;
} struct ACAutomata { int next[N][A], fail[N], end[N];
int root, L; int idx(char ch)
{
switch(ch) {
case 'A': return ;
case 'C': return ;
case 'T': return ;
case 'G': return ;
}
return -;
}
int newNode()
{
for (int i = ; i < A; ++i) next[L][i] = -;
end[L] = ;
return L++;
}
void init()
{
L = ;
root = newNode();
}
void insert(char buf[])
{
int len = strlen(buf);
int now = root;
for (int i = ; i < len; ++i) {
int ch = idx(buf[i]);
if (next[now][ch] == -) next[now][ch] = newNode();
now = next[now][ch];
}
end[now]++;
}
void build()
{
queue<int> Q;
fail[root] = root;
for (int i = ; i < A; ++i) {
if (next[root][i] == -) {
next[root][i] = root;
} else {
fail[ next[root][i] ] = root;
Q.push( next[root][i] );
}
}
while (Q.size()) {
int now = Q.front();
Q.pop();
if (end[ fail[now] ]) end[now]++; //!!
for (int i = ; i < A; ++i) {
if (next[now][i] == -) {
next[now][i] = next[ fail[now] ][i];
} else {
fail[ next[now][i] ] = next[ fail[now] ][i];
Q.push(next[now][i]);
}
}
}
} int query(int n)
{
mat F(L, vec(L));
for (int i = ; i < L; ++i) {
for (int j = ; j < L; ++j) {
F[i][j] = ;
}
}
for (int i = ; i < L; ++i) {
for (int j = ; j < A; ++j) {
int nt = next[i][j];
if (!end[nt]) F[i][nt]++;
}
}
F = pow(F, n);
int res = ;
for (int i = ; i < L; ++i) {
res = (res + F[][i]) % MOD;
}
return res;
} } ac; char buf[];
int main()
{
int m, n;
while (~scanf("%d%d", &m, &n)) {
ac.init();
while (m--) {
scanf("%s", buf);
ac.insert(buf);
}
ac.build();
printf("%d\n", ac.query(n));
} return ;
}
HDU 2243上题要求不存在给定字符串，而这题要求存在至少一个。于是方法就是总方法减去不存在的就是答案了。
题目要求是小于等于L的，所以矩阵加一维记录前缀和就好了。
#include <bits/stdc++.h> using namespace std; typedef unsigned long long ull;
typedef vector<ull> vec;
typedef vector<vec> mat;
const int N = ;
const int A = ;
const int M = ; mat mul(mat &A, mat &B)
{
mat C(A.size(), vec(B[].size()));
for (int i = ; i < A.size(); ++i) {
for (int k = ; k < B.size(); ++k) {
for (int j = ; j < B[].size(); ++j) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
return C;
} mat pow(mat A, ull n)
{
mat B(A.size(), vec(A.size()));
for (int i = ; i < A.size(); ++i)
B[i][i] = ;
while (n > ) {
if (n & ) B = mul(B, A);
A = mul(A, A);
n >>= ;
}
return B;
} struct ACAutomata { int next[N][A], fail[N], end[N];
int root, L; int idx(char ch)
{
return ch - 'a';
}
int newNode()
{
for (int i = ; i < A; ++i) next[L][i] = -;
end[L] = ;
return L++;
}
void init()
{
L = ;
root = newNode();
}
void insert(char buf[])
{
int len = strlen(buf);
int now = root;
for (int i = ; i < len; ++i) {
int ch = idx(buf[i]);
if (next[now][ch] == -) next[now][ch] = newNode();
now = next[now][ch];
}
end[now]++;
}
void build()
{
queue<int> Q;
fail[root] = root;
for (int i = ; i < A; ++i) {
if (next[root][i] == -) {
next[root][i] = root;
} else {
fail[ next[root][i] ] = root;
Q.push( next[root][i] );
}
}
while (Q.size()) {
int now = Q.front();
Q.pop();
if (end[ fail[now] ]) end[now]++;
for (int i = ; i < A; ++i) {
if (next[now][i] == -) {
next[now][i] = next[ fail[now] ][i];
} else {
fail[ next[now][i] ] = next[ fail[now] ][i];
Q.push(next[now][i]);
}
}
}
} ull query(ull n)
{
mat F(L+, vec(L+));
for (int i = ; i <= L; ++i) {
for (int j = ; j <= L; ++j) {
F[i][j] = ;
}
}
for (int i = ; i <= L; ++i) F[i][L] = ;
for (int i = ; i < L; ++i) {
for (int j = ; j < A; ++j) {
int nt = next[i][j];
if (!end[nt]) F[i][nt]++;
}
}
F = pow(F, n+);
return F[][L] - ;
} } ac; char aff[];
int main()
{
int n;
ull m;
while (~scanf("%d%llu", &n, &m)) {
ac.init();
while (n--) {
scanf("%s", aff);
ac.insert(aff);
}
ac.build();
ull ans1 = ac.query(m);
mat F(, vec());
mat S(, vec()); S[][] = ; S[][] = ;
F[][] = ; F[][] = ;
F[][] = ; F[][] = ;
F = pow(F, m);
S = mul(F, S);
ull ans2 = S[][];
printf("%llu\n", ans2 - ans1);
}
return ;
}
POJ1625
同poj2778，不过没有取模操作，需要大数。
大数不可以矩阵快速幂吗？内存不够……
使用dp递推，递推公式也比较简单。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
#include <map> using namespace std; typedef vector<int> vec;
typedef vector<vec> mat;
const int N = ;
const int A = ; map<char, int> mp; struct BigInt
{
const static int mod = ;
const static int DLEN = ;
int a[],len;
BigInt()
{
memset(a,,sizeof(a));
len = ;
}
BigInt(int v)
{
memset(a,,sizeof(a));
len = ;
do
{
a[len++] = v%mod;
v /= mod;
}while(v);
}
BigInt(const char s[])
{
memset(a,,sizeof(a));
int L = strlen(s);
len = L/DLEN;
if(L%DLEN)len++;
int index = ;
for(int i = L-;i >= ;i -= DLEN)
{
int t = ;
int k = i - DLEN + ;
if(k < )k = ;
for(int j = k;j <= i;j++)
t = t* + s[j] - '';
a[index++] = t;
}
}
BigInt operator +(const BigInt &b)const
{
BigInt res;
res.len = max(len,b.len);
for(int i = ;i <= res.len;i++)
res.a[i] = ;
for(int i = ;i < res.len;i++)
{
res.a[i] += ((i < len)?a[i]:)+((i < b.len)?b.a[i]:);
res.a[i+] += res.a[i]/mod;
res.a[i] %= mod;
}
if(res.a[res.len] > )res.len++;
return res;
}
BigInt operator *(const BigInt &b)const
{
BigInt res;
for(int i = ; i < len;i++)
{
int up = ;
for(int j = ;j < b.len;j++)
{
int temp = a[i]*b.a[j] + res.a[i+j] + up;
res.a[i+j] = temp%mod;
up = temp/mod;
}
if(up != )
res.a[i + b.len] = up;
}
res.len = len + b.len;
while(res.a[res.len - ] == &&res.len > )res.len--;
return res;
}
void output()
{
printf("%d",a[len-]);
for(int i = len-;i >= ;i--)
printf("%04d",a[i]);
printf("\n");
}
}; struct ACAutomata { int next[N][A], fail[N], end[N];
int root, L; int idx(char ch)
{
return mp[ch];
}
int newNode()
{
for (int i = ; i < A; ++i) next[L][i] = -;
end[L] = ;
return L++;
}
void init()
{
L = ;
root = newNode();
}
void insert(char buf[])
{
int len = strlen(buf);
int now = root;
for (int i = ; i < len; ++i) {
int ch = idx(buf[i]);
if (next[now][ch] == -) next[now][ch] = newNode();
now = next[now][ch];
}
end[now]++;
}
void build()
{
queue<int> Q;
fail[root] = root;
for (int i = ; i < A; ++i) {
if (next[root][i] == -) {
next[root][i] = root;
} else {
fail[ next[root][i] ] = root;
Q.push( next[root][i] );
}
}
while (Q.size()) {
int now = Q.front();
Q.pop();
if (end[ fail[now] ]) end[now]++; //!!
for (int i = ; i < A; ++i) {
if (next[now][i] == -) {
next[now][i] = next[ fail[now] ][i];
} else {
fail[ next[now][i] ] = next[ fail[now] ][i];
Q.push(next[now][i]);
}
}
}
}
mat query(int n)
{
mat F(L, vec(L));
for (int i = ; i < L; ++i) {
for (unsigned j = ; j < mp.size(); ++j) {
int nt = next[i][j];
if (!end[nt]) F[i][nt]++;
}
}
return F;
} } ac; char word[];
BigInt dp[][];
int main()
{
int n, m, p;
while (~scanf("%d%d%d", &n, &m, &p)) {
ac.init();
getchar();
gets(word);
mp.clear();
for (unsigned i = ; i < strlen(word); ++i) mp[ word[i] ] = i;
while (p--) {
gets(word);
ac.insert(word);
}
ac.build();
mat F = ac.query(m); int now = ;
dp[now][] = ;
for (int i = ; i < ac.L; ++i) dp[now][i] = ;
for (int i = ; i <= m; ++i) {
now ^= ;
for (int j = ; j < ac.L; ++j) dp[now][j] = ;
for (int j = ; j < ac.L; ++j)
for (int k = ; k < ac.L; ++k)
if (F[j][k]) dp[now][k] = dp[now][k] + dp[now^][j] * F[j][k];
}
BigInt res = ;
for (int i = ; i < ac.L; ++i) res = res + dp[now][i];
res.output();
}
return ;
}