首页 > 代码库 > 201. Non Absorbing DFA
201. Non Absorbing DFA
题意好难看懂的说。。。
有限状态自动机DFA是这么一个有序组<Σ, U, s, T, phi>；Σ代表输入字符集，表示此自动机的工作范围；U代表所有的状态集合；s是初始状态；T是最终状态；phi代表转移函数，定义为phi : U × Σ → U。
利用DFA进行字符串识别是要你做这么一件事情：The input of the automation is the string α over Σ. Initially the automation is in state s. Each step it reads the first character c of the input string and changes its state to phi(u, c) where u is the current state. After that the first character of the input string is removed and the step repeats. If when its input string is empty the automation is in the terminal state, it is said that it accepts the initial string α, in the other case it rejects it.
然后无聊的出题人给他加入了一个，b的东西：Nonabsorbing Edges，直译不吸收边。Define function χ : U × Σ → {0, 1}. When making a transition from some state u with some character c, the leading character is removed from the input string only if χ(u, c) = 0. If χ(u, c) = 1, the input string is kept intact and next transition is performed with the new state and the same character.
称这样的DFA为NADFA。
NADFA接受字符串的条件是：such automation accepts some string α if after a number of steps it transits to the terminal state and the input string becomes empty.
输入：第一行是字符集Σ。下来一行是k，表示状态数量。下一行第一个数字S代表初始状态，第二个数字L代表结束状态的数量，然后是L个数字，代表结束状态的编号。然后是一个k * |Σ|的矩阵，代表函数phi。然后再是一个同样大小的矩阵，代表函数X。最后是N。
题目就是要你求能被此，b形式下的DFA（NADFA）接受的长度为N的字符串数量。
竟然是ASC#2的A题！！！
然后发现SGU200~2**都是ASC的原题。。不忍直视了。。以我的智商看来SGU都刷不了了。。
不过SGU200题说到做到，决不放弃！BZOJ用来专门练一些算法。
怎么搞？？
DP是很显然的。用f[i][j]表示匹配到第i位时处在状态j的字符串数量。由于不可吸收边的存在，可以使用记忆化搜索预处理出状态的直接转移。
要用到高精度。。。压位大法好。。。
1 //{HEADS 2 #define FILE_IN_OUT 3 #include <cstdio> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cmath> 7 #include <ctime> 8 #include <algorithm> 9 #include <iostream> 10 #include <fstream> 11 #include <vector> 12 #include <stack> 13 #include <queue> 14 #include <deque> 15 #include <map> 16 #include <set> 17 #include <bitset> 18 #include <complex> 19 #include <string> 20 #define REP(i, j) for (int i = 1; i <= j; ++i) 21 #define REPI(i, j, k) for (int i = j; i <= k; ++i) 22 #define REPD(i, j) for (int i = j; 0 < i; --i) 23 #define STLR(i, con) for (int i = 0, sz = con.size(); i < sz; ++i) 24 #define STLRD(i, con) for (int i = con.size() - 1; 0 <= i; --i) 25 #define CLR(s) memset(s, 0, sizeof s) 26 #define SET(s, v) memset(s, v, sizeof s) 27 #define mp make_pair 28 #define pb push_back 29 #define PL(k, n) for (int i = 1; i <= n; ++i) { cout << k[i] << ‘ ‘; } cout << endl 30 #define PS(k) STLR(i, k) { cout << k[i] << ‘ ‘; } cout << endl 31 using namespace std; 32 void FILE_INIT(string FILE_NAME) { 33 #ifdef FILE_IN_OUT 34 #ifndef ONLINE_JUDGE 35 freopen((FILE_NAME + ".in").c_str(), "r", stdin); 36 freopen((FILE_NAME + ".out").c_str(), "w", stdout); 37 #endif 38 #endif 39 } 40 typedef long long LL; 41 typedef double DB; 42 typedef pair<int, int> i_pair; 43 const int INF = 0x3f3f3f3f; 44 //} 45 46 const int maxn = 1000 + 10; 47 const int maxl = 100 + 10; 48 const int maxm = 60 + 5; 49 const int maxc = 27; 50 const int base = 1000000000; 51 52 char sigma[maxc]; 53 int Snum, Size, S, k, L, n; 54 int teminal_state[maxn], phi[maxn][maxc], chi[maxn][maxc], trans[maxn][maxc]; 55 56 struct big_int { 57 int d[maxl]; 58 int len; 59 big_int() { 60 CLR(d); 61 len = 1; 62 } 63 big_int &operator += (const big_int &a) { 64 len = max(len, a.len); 65 REP(i, len) { 66 d[i] += a.d[i]; 67 if(base < d[i]) { 68 d[i + 1] += d[i] / base; 69 d[i] %= base; 70 } 71 } 72 for(; 0 < d[1 + len]; ++len); 73 return *this; 74 } 75 void print() { 76 printf("%d", d[len]); 77 for(int i = len - 1; 0 < i; --i) { 78 printf("%09d", d[i]); 79 } 80 puts(""); 81 } 82 }f[maxn][maxm]; 83 84 void dfs(int u, int c) { 85 if(chi[u][c] == 0) { 86 trans[u][c] = u; 87 } 88 if(trans[u][c]) { 89 return; 90 } 91 trans[u][c] = -1; 92 dfs(phi[u][c], c); 93 trans[u][c] = trans[phi[u][c]][c]; 94 } 95 96 int main() { 97 FILE_INIT("201"); 98 99 scanf("%s", sigma);100 Size = strlen(sigma);101 scanf("%d", &k);102 scanf("%d %d", &S, &L);103 REP(i, L) {104 scanf("%d", &teminal_state[i]);105 }106 REP(i, k) {107 REP(j, Size) {108 scanf("%d", &phi[i][j]);109 }110 }111 REP(i, k) {112 REP(j, Size) {113 scanf("%d", &chi[i][j]);114 }115 }116 scanf("%d", &n);117 REP(i, k) {118 REP(j, Size) {119 if(!trans[i][j]) {120 dfs(i, j);121 }122 }123 }124 f[S][0].d[1] = 1;125 REPI(i, 0, n - 1) {126 REP(j, k) {127 REP(c, Size) {128 if(trans[j][c] > 0) {129 f[phi[trans[j][c]][c]][i + 1] += f[j][i];130 }131 }132 }133 }134 big_int ans;135 REP(i, L) {136 ans += f[teminal_state[i]][n];137 }138 ans.print();139 140 return 0;141 }