dna tdi cnblogs tin true clas fin strlen
传送门
AC自动机加DP就不说了
注意到 m <= 10,所以模式串很少。
而 n 很大就需要 log 的算法,很容易想到矩阵。
但是该怎么构建?
还是矩阵 A(i,j) = ∑A(i,k) * A(k,j),那么i到j的方案数就是j到k的方案数称k到j的方案数,那么直接矩阵快速幂即可
- #include <queue>
- #include <cstdio>
- #include <cstring>
- #define N 100001
- #define p 100000
- #define LL long long
- int n, m, cnt, ans;
- int next[N][4], fail[N], f[101][N];
- bool val[N];
- char s[N];
- std::queue <int> q;
- struct Matrix
- {
- int n, m;
- LL a[141][141];
- Matrix()
- {
- n = m = 0;
- memset(a, 0, sizeof(a));
- }
- }res;
- inline int idx(char x)
- {
- if(x == ‘A‘) return 0;
- if(x == ‘C‘) return 1;
- if(x == ‘T‘) return 2;
- if(x == ‘G‘) return 3;
- }
- inline void insert()
- {
- int i, x, now = 0, len = strlen(s + 1);
- for(i = 1; i <= len; i++)
- {
- x = idx(s[i]);
- if(!next[now][x])
- next[now][x] = ++cnt;
- now = next[now][x];
- }
- val[now] = 1;
- }
- inline void make_fail()
- {
- int i, now;
- for(i = 0; i < 4; i++)
- if(next[0][i])
- q.push(next[0][i]);
- while(!q.empty())
- {
- now = q.front();
- q.pop();
- for(i = 0; i < 4; i++)
- {
- if(!next[now][i])
- {
- next[now][i] = next[fail[now]][i];
- continue;
- }
- fail[next[now][i]] = next[fail[now]][i];
- val[next[now][i]] |= val[next[fail[now]][i]];
- q.push(next[now][i]);
- }
- }
- }
- inline Matrix operator * (Matrix x, Matrix y)
- {
- int i, j, k;
- Matrix ret;
- ret.n = x.n;
- ret.m = y.m;
- for(i = 0; i <= x.n; i++)
- for(j = 0; j <= y.m; j++)
- for(k = 0; k <= y.n; k++)
- ret.a[i][j] = (ret.a[i][j] + x.a[i][k] * y.a[k][j]) % p;
- return ret;
- }
- inline Matrix operator ^ (Matrix x, int y)
- {
- int i;
- Matrix ret;
- res.n = ret.m = cnt;
- for(i = 0; i <= cnt; i++) ret.a[i][i] = 1;
- for(; y; y >>= 1)
- {
- if(y & 1) ret = ret * x;
- x = x * x;
- }
- return ret;
- }
- int main()
- {
- int i, j, k;
- scanf("%d %d", &n, &m);
- for(i = 1; i <= n; i++)
- {
- scanf("%s", s + 1);
- insert();
- }
- make_fail();
- res.n = res.m = cnt;
- for(i = 0; i <= cnt; i++)
- {
- if(val[i]) continue;
- for(j = 0; j < 4; j++)
- if(!val[next[i][j]])
- res.a[i][next[i][j]]++;
- }
- res = res ^ m;
- for(i = 0; i <= cnt; i++)
- ans = (ans + res.a[0][i]) % p;
- printf("%d\n", ans);
- return 0;
- }
[POJ2778]DNA Sequence(AC自动机 + DP + 矩阵优化)
来源: http://www.bubuko.com/infodetail-2308127.html