生活随笔
收集整理的這篇文章主要介紹了
POJ 2778 DNA Sequence （AC自动机+矩阵快速幂）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
題目鏈接
MMM個病毒串，求長度為NNN的不包含病毒的字符串種類數
思路
把所有的病毒串建ACACAC自動機，failfailfail指針指向的節點如果標記過（包含病毒串）當前也是不合法串 。
然后我們可以得到一個節點可以合法轉移的矩陣，最后求矩陣N矩陣^N矩陣N，統計答案即可。
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <stdio.h>
#include <iostream>
#include <numeric>
#include <algorithm>
#include <cstring>
#include <time.h>
#define LL long long
#define P pair<int, int>
#define lowbit(x) (x & -x)
#define mem(a, b) memset(a, b, sizeof(a))
#define mid ((l + r) >> 1)
#define lc rt<<1
#define rc rt<<1|1
#define endl '\n'
const int maxn
= 1e5 + 5;
const int inf
= 0x3f3f3f3f;
const int mod
= 100000;
using namespace std
;struct Matrix
{int n
;LL mat
[151][151];Matrix(){}Matrix(int _n
) {n
= _n
;for (int i
= 0; i
< n
; ++i
) {for (int j
= 0; j
< n
; ++j
) {mat
[i
][j
] = 0;}}}Matrix
operator *(const Matrix
&b
) const{Matrix ans
= Matrix(n
);for (int i
= 0; i
< n
; ++i
) {for (int j
= 0; j
< n
; ++j
) {for (int k
= 0; k
< n
; ++k
) {ans
.mat
[i
][j
] += mat
[i
][k
] * b
.mat
[k
][j
];ans
.mat
[i
][j
] %= mod
;}}}return ans
;}
};
Matrix
Pow(Matrix a
, int n
) {Matrix ans
= Matrix(a
.n
);Matrix tmp
= a
;for (int i
= 0; i
< a
.n
; ++i
) {ans
.mat
[i
][i
] = 1;}while (n
) {if (n
& 1) ans
= ans
* tmp
;tmp
= tmp
* tmp
;n
>>= 1;}return ans
;
}char s
[maxn
];
struct Trie
{int nex
[maxn
][4], fail
[maxn
], end
[maxn
];int root
, p
;int newnode() {for (int i
= 0; i
< 4; ++i
) {nex
[p
][i
] = -1;}end
[p
++] = 0;return p
- 1;}inline void init() {p
= 0;root
= newnode();}inline int id(char c
) {if (c
== 'A') return 0;if (c
== 'C') return 1;if (c
== 'T') return 2;return 3;}inline void insert(char s
[]) {int now
= root
;for (int i
= 0; s
[i
]; ++i
) {if (nex
[now
][id(s
[i
])] == -1)nex
[now
][id(s
[i
])] = newnode();now
= nex
[now
][id(s
[i
])];}end
[now
] = 1;} inline void build() {queue
<int> que
;fail
[root
] = root
;for (int i
= 0; i
< 4; ++i
) {if (nex
[root
][i
] == -1)nex
[root
][i
] = root
;else {fail
[nex
[root
][i
]] = root
;que
.push(nex
[root
][i
]);}}while (!que
.empty()) {int now
= que
.front();que
.pop();if (end
[fail
[now
]]) end
[now
] = 1;for (int i
= 0; i
< 4; ++i
) {if (nex
[now
][i
] == -1) nex
[now
][i
] = nex
[fail
[now
]][i
];else {fail
[nex
[now
][i
]] = nex
[fail
[now
]][i
];que
.push(nex
[now
][i
]);}}}}inline Matrix
getMatrix() {Matrix ans
= Matrix(p
);for (int i
= 0; i
< p
; ++i
) {for (int j
= 0; j
< 4; ++j
) {if (end
[i
] || end
[nex
[i
][j
]]) continue;ans
.mat
[i
][nex
[i
][j
]]++;}}return ans
;}
}ac
;int main
() {ios
::sync_with_stdio(0);cin
.tie(0), cout
.tie(0);int m
, n
;scanf("%d%d", &m
, &n
);ac
.init();for (int i
= 0; i
< m
; ++i
) {scanf("%s", s
);ac
.insert(s
);}ac
.build();Matrix tmp
= ac
.getMatrix();tmp
= Pow(tmp
, n
);int ans
= 0;for (int i
= 0; i
< ac
.p
; ++i
) {ans
+= tmp
.mat
[0][i
];}ans
%= mod
;printf("%d\n", ans
);return 0;
}
總結
以上是生活随笔為你收集整理的POJ 2778 DNA Sequence （AC自动机+矩阵快速幂）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
