<span>POJ - 1625 Censored! </span>
希望自己能成为日更博主
题目连接：http://poj.org/problem?id=1625
题目大意：给你n个字母，再给你p个字符串，问有多少个长度为m的只由给出的n个字母构成的字符串，且字符串不能包括给出的p个字符串；
题解：因为这个题不用取模，所以得使用高精度，参考了博客：https://www.cnblogs.com/shangyu/p/3730815.html；这个题和HDU 2243很像，只要把他的矩阵快速幂换成高精度就可以了。dp[i+1][next] = dp[i+1][next]+dp[i][j] ， dp[i][j] 表示长度为 i 在第j个结点的方案数，next为当前j点所能走到的下一个合法的结点。求不含啥啥字符串的个数时，建立ac自动机时都会有end[now]|=end[fail[now]] ，表示如果当前结点fail指向的结点被标记了，那么当前节点也要被标记。
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<queue> 5 #include<string.h> 6 using namespace std; 7 8 const int base=1e4; 9 const int DIG=4; 10 const int maxn = 11100; 11 const int MX = 1110; 12 int n,m,p; 13 int id[2200]; 14 15 struct tire{ 16 int nxt[maxn][2200],fail[maxn],end[maxn],tot,root,vis[maxn]; 17 int newNode(){ 18 for(int i=0;i<n;i++) nxt[tot][i] = -1; 19 end[tot++] = 0; 20 return tot-1; 21 } 22 void Init(){ 23 tot = 0; 24 root = newNode(); 25 } 26 void Insert(char *buf){ 27 int len = strlen(buf),i,u = root; 28 for(i=0;i<len;i++){ 29 int x = id[buf[i]]; 30 if(nxt[u][x]==-1) nxt[u][x] = newNode(); 31 u = nxt[u][x]; 32 } 33 end[u] = 1; 34 } 35 void build(){ 36 queue <int> q; 37 fail[root] = root; 38 for(int i=0;i<n;i++){ 39 if(nxt[root][i]==-1) nxt[root][i] = root; 40 else{ 41 fail[nxt[root][i]] = root; 42 q.push(nxt[root][i]); 43 } 44 } 45 while(!q.empty()){ 46 int now = q.front(); 47 q.pop(); 48 for(int i=0;i<n;i++){ 49 if(nxt[now][i]==-1) nxt[now][i] = nxt[fail[now]][i]; 50 else{ 51 fail[nxt[now][i]] = nxt[fail[now]][i]; 52 q.push(nxt[now][i]); 53 } 54 } 55 end[now]|=end[fail[now]]; 56 } 57 } 58 }ac; 59 60 struct bignum 61 { 62 int a[110],len; 63 bignum() 64 { 65 memset(a,0,sizeof(a)); 66 len=1; 67 } 68 bignum(int v) 69 { 70 memset(a,0,sizeof(a)); 71 len=0; 72 do{ 73 a[len++]=v%base; 74 v/=base; 75 }while(v); 76 } 77 bignum(const char s[]) 78 { 79 memset(a,0,sizeof(a)); 80 int k = strlen(s); 81 len = k/DIG; 82 if(k%DIG) len++; 83 int cnt = 0; 84 for(int i = k-1; i >= 0 ; i-=DIG){ 85 int t = 0; 86 int kk = i-DIG+1; 87 if(kk<0) kk =0; 88 for(int j = kk ; j <= i ; j++) 89 t = t*10+s[j]-'0'; 90 a[cnt++] = t; 91 } 92 } 93 bignum operator + (const bignum &b) const 94 { 95 bignum res; 96 res.len=max(len,b.len); 97 int i; 98 for(i=0;i<res.len;i++) 99 res.a[i]=0; 100 for(i=0;i<res.len;i++){ 101 res.a[i]+=((i<len)?a[i]:0)+((i<b.len)?b.a[i]:0); 102 res.a[i+1]+=res.a[i]/base; 103 res.a[i]=res.a[i]%base; 104 } 105 if(res.a[res.len]>0) res.len++; 106 return res; 107 } 108 void output() 109 { 110 printf("%d",a[len-1]); 111 for(int i=len-2;i>=0;i--) 112 printf("%04d",a[i]); 113 printf("\n"); 114 } 115 }dp[110][110]; 116 117 void solve() 118 { 119 for(int i=1;i<=m;i++) 120 for(int j=0;j<=ac.tot;j++) 121 dp[i][j]=bignum(0); 122 dp[0][0]=bignum(1); 123 for(int i=0;i<m;i++){ 124 for(int j=0;j<ac.tot;j++){ 125 for(int k=0;k<n;k++){ 126 if(ac.end[ac.nxt[j][k]]) continue; 127 dp[i+1][ac.nxt[j][k]]= dp[i+1][ac.nxt[j][k]]+dp[i][j]; 128 } 129 } 130 } 131 bignum ans=bignum(0); 132 for(int j=0;j<ac.tot;j++) 133 ans=ans+dp[m][j]; 134 ans.output(); 135 } 136 137 char s1[MX]; 138 139 int main() 140 { 141 scanf("%d%d%d",&n,&m,&p); 142 ac.Init(); 143 scanf("%s",s1); 144 for(int i=0;i<n;i++){ 145 id[s1[i]]=i; 146 } 147 for(int i=0;i<p;i++) 148 scanf("%s",s1),ac.Insert(s1); 149 ac.build(); 150 solve(); 151 return 0; 152 }
投递中国石油等公司10个岗位 >