POJ2778 – DNA Sequence(AC自动机+快速矩阵幂)

POJ2778

【题意】给出M(<=10)个病毒DNA字符串，每个串长度不超过10。然后给出一个长度为N(<=2000000000)的只能由’A’,’C’,’T’,’G’组成的DNA字符串，问能 组成多少个不包含病毒串的字符串。

【分析】n的范围很大，需要快速矩阵幂，但是怎么构建矩阵呢；在《十个利用矩阵乘法解决的经典题目(Maxtrix67)》这篇文章中有提到有向图的矩阵，从任意一点到另外点经过几步有几种走法，可以建一个邻接矩阵，则通过k步就是矩阵的k次方；而这题可以用AC自动机建立有向图矩阵，稍微有些不同的是这个 矩阵初始距离的两点之间的边数，构建fail指针的时候也需要加上判断前缀和是否含有病毒。这样最后对状态图建的二维矩阵的n次方就是最后初始点0到各点之间的转移可能数。

【AC CODE】187ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
#include <bitset>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 10*10+10;
const LL MOD = 100000;
int id[300];
struct Trie{
	int cnt;
	int ch[MAXN][4], fail[MAXN];
	bool end[MAXN];
	int newnode()
	{
		clc(ch[cnt],-1);
		end[cnt++] = 0;
		return cnt-1;
	}
	void init()
	{
		cnt = 0;
		newnode();
		clc(end,0);
	}
	void insert(char *s)
	{
		int u = 0,len = strlen(s);
		rep(i,0,len)
		{
			int& c = ch[u][id[s[i]]];
			if(-1 == c)
				c = newnode();
			u = c;
		}
		end[u] = true;
	}
	void get_fail()
	{
		queue<int> q;
		fail[0] = 0;
		rep(i,0,4)
		{
			int& c = ch[0][i];
			if(~c)
			{
				fail[c] = 0;
				q.push(c);
			}
			else c = 0;
		}
		while(!q.empty())
		{
			int u = q.front();q.pop();
			rep(i,0,4)
			{
				int& c = ch[u][i];
				int p = ch[fail[u]][i];
				if(end[p]) end[c] = true;//当前面字符串的后缀为病毒串时该串也不能用
				if(~c)
				{
					fail[c] = p;
					q.push(c);
				}
				else c = p;
			}
		}
	}
}ac;
struct MATRIX{
	LL num[MAXN][MAXN];
}x;
int cnt;

MATRIX mul_mod(const MATRIX& a, const MATRIX& b)
{
	MATRIX ans;
	clc(ans.num,0);
	rep(i,0,cnt)
	{
		rep(j,0,cnt)
		{
			rep(k,0,cnt)
				ans.num[i][j] += a.num[i][k]*b.num[k][j];
			ans.num[i][j] %= MOD;
		}
	}
	return ans;
}
MATRIX pow_mod(MATRIX x, int n)
{
	MATRIX ans;
	clc(ans.num,0);
	rep(i,0,cnt) ans.num[i][i] = 1;
	while(n)
	{
		if(n&1)  ans = mul_mod(ans,x);
		x = mul_mod(x,x);
		n >>= 1;
	}
	return ans;
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	id['A'] = 0,id['C'] = 1, id['T'] = 2, id['G'] = 3;
	int m,n;
	scanf("%d %d", &m, &n);
	ac.init();
	char str[20];
	rep(i,0,m)
	{
		scanf("%s", str);
		ac.insert(str);
	}
	ac.get_fail();
	cnt = ac.cnt;
	clc(x.num,0);
	rep(i,0,cnt)
	{
		rep(j,0,4)
			if(!ac.end[i] && !ac.end[ac.ch[i][j]])
				x.num[i][ac.ch[i][j]]++;
	}
	x = pow_mod(x,n);
	LL ans = 0;
	rep(i,0,cnt) ans += x.num[0][i];
	printf("%I64d\n", ans%MOD);
	return 0;
}