利用AC自动机构建一个 DFA, 该 DFA 不经过任何模式串。然后问题转化为在一个图上找经过 n 条边的路径条数。
代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef long long LL;
int n, m, cnt= 0;
LL mat[200][200]= {0};
struct Node{
int next[4];
int fail, flag;
void init(){
for( int i= 0; i< 4; ++i ) next[i]= 0;
fail= -1; flag= 0; }
}tb[200];
inline int toInt( char ch ){
switch( ch ){
case 'A': return 0;
case 'T': return 1;
case 'G': return 2;
case 'C': return 3;
}
}
void insert( char* s ){
int rt= 0;
while( *s ){
int t= toInt( *s );
if( tb[rt].next[t]== 0 ){
tb[++cnt].init();
tb[rt].next[t]= cnt;
}
rt= tb[rt].next[t]; s++;
}
tb[rt].flag= 1;
}
char str[15];
int que[200], head, tail;
void bfs(){
head= tail= 0; que[0]= 0;
int p, q;
while( head<= tail ){
int now= que[head++];
for( int t= 0; t< 4; ++t )
if( tb[now].next[t] ){
p= tb[now].next[t]; q= tb[now].fail;
while( q!= -1 && !tb[q].next[t] ) q= tb[q].fail;
if( q== -1 ) tb[p].fail= 0;
else{
tb[p].fail= tb[q].next[t];
tb[p].flag|= tb[ tb[p].fail ].flag;
}
que[++tail]= p;
}
else{
q= tb[now].fail;
while( q!= -1 && !tb[q].next[t] ) q= tb[q].fail;
if( q== -1 ) tb[now].next[t]= 0;
else tb[now].next[t]= tb[q].next[t];
}
}
}
inline void mult( LL x[200][200], LL y[200][200] ){
LL z[200][200];
for( int i= 0; i<= cnt; ++i )
for( int j= 0; j<= cnt; ++j ){
z[i][j]= 0;
for( int k= 0; k<= cnt; ++k )
z[i][j]+= x[i][k]* y[k][j];
z[i][j]%= 100000;
}
for( int i= 0; i<= cnt; ++i )
for( int j= 0; j<= cnt; ++j ) y[i][j]= z[i][j];
}
int main(){
scanf("%d%d",&m, &n ); tb[0].init();
for( int i= 0; i< m; ++i ){
scanf("%s", str );
insert( str );
}
bfs();
for( int i= 0; i<= cnt; ++i )
if( tb[i].flag== 0 )
for( int j= 0; j< 4; ++j )
if( tb[ tb[i].next[j] ].flag== 0 ) mat[i][ tb[i].next[j] ]++;
LL ans[200][200]= {0};
for( int i= 0; i<= cnt; ++i ) ans[i][i]= 1;
while( n ){
if( n& 1 ) mult( mat, ans );
mult( mat, mat ); n>>= 1;
}
LL res= 0;
for( int i= 0; i<= cnt; ++i )
if( tb[i].flag== 0 ) res+= ans[0][i];
printf("%I64d\n", res% 100000 );
return 0;
}
分享到:
相关推荐
PKU 、POJ ACM/ICPC300多题的代码,还有各种典型问题的分类代码
ACM PKU_poj 1197 仓库问题源代码,愿与大家共享。若谁更好的代码,多谢提供。
用Java代码实现POJ(PKU)上题2494!
PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks
acm 1001 到1009代码,已通过验证
O(nlogn)凸包问题 poj2187
http://acm.pku.edu.cn/JudgeOnline/ acm的AC解题报告
acm pku poj 1000 1001 1002 1003 1201
1011,1012,1013,1014,1015,1017,1026,1028,1032,1035,1041,1046,1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 ...
acm.pku.edu.cn/OnlineJudge上一些已经通过的代码
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
PKU 1000-1050我ac的代码!绝对保证质量!
POJ1151 Atlantis的源代码,非常经典线段树应用的题目,求面积。
poj1088原代码, 这是最新的版本, 经过我们dhuACM团队合作而编写的!
pku 123 题目代码 pku acm poj
“北京大学程序在线评测系统”是一个免费的公益性网上程序设计题库,网址为http://poj.grids.cn/ 及 http://acm.pku.edu.cn/JudgeOnline,它包含2000多道饶有趣味的程序设计题,题目大部分来自ACM国际大学生程序设计...
#include using namespace std; #define M 1000000 char t[M+1],p[M+1]; int lent,lenp; bool kmp(char *t,char *p) { int i,j; for(i=lenp,j=0;i;i++) { if(t[i]!=p[j]) return false;...}
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
pku acm 1007 DNA Sorting代码 逆序数 排序 解题报告请访问:http://blog.csdn.net/china8848
poi3252,北大acm里面的题目代码。