题目大意：给定一些字符，将这些字符组成一个固定长度的字符串，但是字符串不能包含一些禁词，问你有多少种组合方式。
这是一道好题，既然出现了“一些”禁词，那么这题肯定和AC自动机有点关系了，对于这一题来说，因为我们需要的是求出在N^M种状态除去包含禁词的状态数，枚举肯定是不现实的了，我们唯一能做的只能是DP，但是怎么DP呢？只能是通过AC自动机来想了，由此我们来看一下trie树，我们知道trie树是可以表示不同字符串前后缀的转移关系的，但是这一题并不是要我们求出字串中是否有禁词，而是要我们求出除了禁词的其他组合方式，那么我们可不可以通过trie树直接看出来呢？答案是可以的，但是我们要改进一下。
如果我们把trie树中的Next数组补齐，比如在ACGT中含有禁词ACC，C，我们可以构建如下图的一个trie树
我们可以看到这棵trie树补齐了一般trie树不存在的边，其实就是把不存在的对应k子节点指向当前节点的fail节点的k节点，这样我们就可以找到所有元素转移的状态关系了，得到了这个东西，那么我们就可以用DP来把状态转移全部搞出来了，组成一个m长度的单词，只要我们不从失败状态（禁词的结尾）转出或者转入就OK了。
这样一开DP就很容易理解了，状态转移方程dp[i+1][转移状态]=dp[i][trie树上某个节点]+dp[i+1][转移状态]（转移状态是指的是其他节点转移过来的情况），那么怎么标定非法情况呢？我们不仅要把单词结尾标记为非法状态，如果当前位置fail指针的指向的k位置也为单词结尾，那么当前位置的指向的k位置也必须标记为非法状态，因为我们不能从这个节点转出（也就意味着这个单词是包含着另一个单词的）。
1 #include2 #include 3 #include 4 #define MAX 130 5 6 using namespace std; 7 8 static int sum_node, Hash_Table[MAX]; 9 static char str[200]; 10 11 struct node 12 { 13 int if_end,num;//注意end位置不仅是标记单词的结束，而且还表示了是否能状态转移 14 node *fail, *Next[MAX]; 15 }Mem_Pool[MAX], *Trie_Node[MAX], *Queue[MAX * 2]; 16 struct BigInterget 17 { 18 int A[25]; 19 enum { MOD = 10000 }; 20 BigInterget()//构析函数用于初始化大数，A[0]表示大数的长度 21 { 22 memset(A, 0, sizeof(A)); 23 A[0] = 1; 24 } 25 void set(int x)//用于设定一个32位的整数 26 { 27 memset(A, 0, sizeof(A)); 28 A[0] = 1; A[1] = x; 29 } 30 void print(void) 31 { 32 printf("%d", A[A[0]]); 33 for (int i = A[0] - 1; i > 0; i--) 34 { 35 if (A[i] == 0){ printf("0000"); continue; } 36 for (int k = 10; k*A[i] < MOD; k *= 10) 37 printf("0"); 38 printf("%d", A[i]); 39 } 40 printf("\n"); 41 } 42 int& operator [] (int pos) { return A[pos]; } 43 const int& operator [] (int pos) const { return A[pos]; } 44 45 BigInterget operator + (const BigInterget &B) 46 { 47 BigInterget C; 48 C[0] = max(A[0], B[0]); 49 for (int i = 1; i <= C[0]; i++) 50 C[i] += A[i] + B[i], C[i + 1] += C[i] / MOD, C[i] %= MOD; 51 if (C[C[0] + 1] > 0)C[0]++;//进位 52 return C; 53 } 54 }; 55 static BigInterget dp[52][MAX]; 56 57 struct node *create_new_node(void); 58 void put_letter_to_hash(const int); 59 void Insert(struct node *); 60 void build_ac_automation(struct node *); 61 62 int main(void) 63 { 64 int Word_Length, Forbidden_Word_Sum, Letter_Type_Sum; 65 while (~scanf("%d%d%d", &Letter_Type_Sum, &Word_Length, &Forbidden_Word_Sum)) 66 { 67 sum_node = 0; 68 memset(Hash_Table, 0, sizeof(Hash_Table)); 69 node *root = create_new_node(); 70 put_letter_to_hash(Letter_Type_Sum); 71 72 for (int i = 0; i < Forbidden_Word_Sum; i++) 73 Insert(root); 74 build_ac_automation(root); 75 76 for (int i = 0; i <= Word_Length; i++) 77 for (int j = 0; j < sum_node; j++) 78 dp[i][j] = BigInterget(); 79 dp[0][0].set(1); 80 81 for (int i = 0; i < Word_Length; i++) 82 for (int j = 0; j < sum_node; j++) 83 { 84 if (Mem_Pool[j].if_end)//不能从非法状态中转入 85 continue; 86 for (int k = 0; k < Letter_Type_Sum; k++) 87 { 88 if (Mem_Pool[j].Next[k]->if_end)//不能从非法状态中转出 89 continue; 90 int id = Mem_Pool[j].Next[k]->num; 91 dp[i + 1][id] = dp[i][j] + dp[i + 1][id]; 92 } 93 } 94 BigInterget ans = BigInterget(); 95 for (int i = 0; i < sum_node; i++) 96 ans = ans + dp[Word_Length][i]; 97 ans.print(); 98 } 99 return EXIT_SUCCESS;100 }101 102 struct node *create_new_node(void)103 {104 node *tmp = &Mem_Pool[sum_node];105 tmp->fail = NULL;106 tmp->if_end = 0;107 tmp->num = sum_node++;108 memset(tmp->Next, NULL, sizeof(struct node*)*MAX);109 return tmp;110 }111 112 void put_letter_to_hash(const int Letter_Type_Sum)113 {114 getchar();//去掉回车换行115 gets(str);116 117 for (int i = 0; i < Letter_Type_Sum; i++)118 Hash_Table[str[i]] = i;119 }120 121 void Insert(struct node *root)122 {123 gets(str);124 struct node *tmp_ptr = root;125 126 for (int i = 0; str[i] != '\0'; i++)127 {128 int id = Hash_Table[str[i]];129 if (tmp_ptr->Next[id] == NULL)130 tmp_ptr->Next[id] = create_new_node();131 tmp_ptr = tmp_ptr->Next[id];132 }133 tmp_ptr->if_end = 1;134 }135 136 void build_ac_automation(struct node *root)137 {138 int head = 0, tail = 0;139 node *out = NULL;140 root->fail = NULL;141 Queue[tail++] = root;142 143 while (head != tail)144 {145 out = Queue[head++];146 for (int i = 0; i < MAX; i++)147 if (out->Next[i] != NULL)148 {149 if (out == root)150 out->Next[i]->fail = root;151 else152 {153 out->Next[i]->fail = out->fail->Next[i];154 //如果还找到在其他地方找到和他一样的元素，那么我们就把失败指针指向这个元素,同时要设定合法状态155 out->Next[i]->if_end = out->fail->Next[i]->if_end ? 1 : out->Next[i]->if_end;156 }157 Queue[tail++] = out->Next[i];158 }159 else160 {161 if (out == root) out->Next[i] = root;162 else out->Next[i] = out->fail->Next[i];163 }164 }165 }
另外这个题要用到大数加法，在网上找了个很好的模板，以后就用这个了
参考：