POJ_2778
如果做过POJ_1625的话，dp思路还是比较容易想到的，如果没做过的话可以参考一下《Trie图的构建、活用与改进》这篇文章的思想。
但遇到的一个问题是，对于如此巨大无比的n我们要怎么去优化呢？这个还是依赖于动态转移方程的形式。我们可以看出这个题目的动态转移方程一个确定的和式方程，即对于任意第i+1阶段的状态j，都可以表示成f[i+1][j]=a1*f[i][1]+a2*f[i][2]+...+ax*f[i][x]，那么所有x个状态的转移方程就可以用一个大的矩阵的乘法表示出来，具体的构造方式如下图：
这样自然就可以用二分矩阵来加快运算了。
不过这个算法虽然能够AC，但是耗时还是比较长的。
#include<stdio.h>
#include<string.h>
#define MAXD 100
#define D 100000
int M, N, e, p, P[MAXD], next[MAXD][4], flag[MAXD], q[MAXD];
char gene[20];
long long int f[40][MAXD][MAXD], t[MAXD][MAXD];
void add(int cur, int k)
{
++ e;
flag[e] = 0;
memset(next[e], 0, sizeof(next[e]));
next[cur][k] = e;
}
void init()
{
int i, j, k, cur;
e = 0;
memset(next[e], 0, sizeof(next[e]));
flag[e] = 0;
for(i = 0; i < M; i ++)
{
scanf("%s", gene);
for(j = 0; gene[j]; j ++)
{
switch(gene[j])
{
case 'A' : {gene[j] = '0'; break;}
case 'T' : {gene[j] = '1'; break;}
case 'C' : {gene[j] = '2'; break;}
case 'G' : {gene[j] = '3'; break;}
}
}
cur = 0;
for(j = 0; gene[j]; j ++)
{
k = gene[j] - '0';
if(!next[cur][k])
add(cur, k);
cur = next[cur][k];
}
flag[cur] = 1;
}
for(i = 0; i < 4; i ++)
if(!next[0][i])
add(0, i);
}
void pow_mod(int n)
{
int i, j, k, x;
long long int ans;
x = ++ p;
if(n == 1)
{
for(i = 0; i <= e; i ++)
for(j = 0; j <= e; j ++)
f[x][i][j] = f[0][i][j];
return ;
}
pow_mod(n / 2);
for(i = 0; i <= e; i ++)
for(j = 0; j <= e; j ++)
{
ans = 0;
for(k = 0; k <= e; k ++)
ans = (ans + f[x + 1][i][k] * f[x + 1][k][j]) % D;
f[x][i][j] = ans;
}
if(n % 2)
{
for(i = 0; i <= e; i ++)
for(j = 0; j <= e; j ++)
{
ans = 0;
for(k = 0; k <= e; k ++)
ans = (ans + f[x][i][k] * f[0][k][j]) % D;
t[i][j] = ans;
}
for(i = 0; i <= e; i ++)
for(j = 0; j <= e; j ++)
f[x][i][j] = t[i][j];
}
}
void solve()
{
int i, j, k, u, front, rear;
long long int ans;
front = rear = P[0] = 0;
q[rear ++] = 0;
while(front != rear)
{
u = q[front ++];
for(i = 0; i < 4; i ++)
{
j = next[u][i];
if(j != 0)
{
q[rear ++] = j;
if(u == 0)
P[j] = 0;
else
{
for(k = P[u]; k != 0; k = P[u])
if(next[k][i])
break;
P[j] = next[k][i];
}
if(flag[P[j]])
flag[j] = 1;
}
else
{
for(k = P[u]; k != 0; k = P[u])
if(next[k][i])
break;
next[u][i] = next[k][i];
}
}
}
memset(f[0], 0, sizeof(f[0]));
for(i = 0; i <= e; i ++)
{
if(flag[i])
continue;
for(j = 0; j < 4; j ++)
{
k = next[i][j];
if(flag[k])
continue;
f[0][k][i] = 1;
}
}
p = 0;
pow_mod(N);
ans = 0;
for(i = 0; i <= e; i ++)
ans = (ans + f[1][i][0]) % D;
printf("%lld\n", ans);
}
int main()
{
while(scanf("%d%d", &M, &N) == 2)
{
init();
solve();
}
return 0;
}