題意很簡(jiǎn)單，假定文本集就是A,C,T,G，給定M個(gè)模式串，問(wèn)你長(zhǎng)度為N的文本不出現(xiàn)這些模式
串的可能性到底有多少種。。。
確實(shí)非常不直觀的樣子。。。
解法是先學(xué)學(xué)AC自動(dòng)機(jī)，建立起Trie圖，根據(jù)trie圖可以得到長(zhǎng)度為1的路徑矩陣，然后再快速
冥得到長(zhǎng)度為N的路徑矩陣。
說(shuō)起來(lái)都非常糾結(jié)，沒(méi)學(xué)過(guò)AC自動(dòng)機(jī)更加無(wú)法理解。學(xué)AC自動(dòng)機(jī)之前據(jù)說(shuō)得先學(xué)Trie樹(shù)和KMP
才好理解。學(xué)AC自動(dòng)機(jī)搞Trie圖就花費(fèi)了近2天了，然后弄懂這個(gè)題又是一天，好在基本明白了。
馬上快比賽了，從長(zhǎng)春換到金華也不知道是好是壞。。。還是弱菜啊。。。
貼下我的Trie圖+快速冥(直接二分了,沒(méi)有寫成數(shù)論里面那種算法)...
#include <stdio.h>
#include <
string.h>
#include <algorithm>
#include <queue>
using namespace std;
typedef
long long INT;
const int MOD = 100000;
const int MAX_P = 100;
const int MAX_D = 4;
int nIdx[256];
char szPat[MAX_P];
INT nMatrix[MAX_P][MAX_P];
INT B[MAX_P][MAX_P];
INT A[MAX_P][MAX_P];
void InitIdx()
{
nIdx['A'] = 0;
nIdx['C'] = 1;
nIdx['T'] = 2;
nIdx['G'] = 3;
}
struct Trie
{
Trie* fail;
Trie* next[MAX_D];
int no;
bool flag;
Trie()
{
fail = NULL;
memset(next, 0,
sizeof(next));
no = 0;
flag =
false;
}
};
Trie tries[MAX_D * MAX_P];
int nP;
Trie* pRoot;
Trie* NewNode()
{
memset(&tries[nP], 0,
sizeof(Trie));
tries[nP].no = nP;
return &tries[nP++];
}
void InitTrie(Trie*& pRoot)
{
nP = 0;
pRoot = NewNode();
}
void Insert(
char* pszPat)
{
Trie* pNode = pRoot;
while (*pszPat)
{
if (pNode->next[nIdx[*pszPat]] == NULL)
{
pNode->next[nIdx[*pszPat]] = NewNode();
}
pNode = pNode->next[nIdx[*pszPat]];
++pszPat;
}
pNode->flag =
true;
}
int BuildAC(Trie* pRoot)
{
memset(nMatrix, 0,
sizeof(nMatrix));
pRoot->fail = NULL;
queue<Trie*> qt;
qt.push(pRoot);
while (!qt.empty())
{
Trie* front = qt.front();
qt.pop();
for (
int i = 0; i < MAX_D; ++i)
{
if (front->next[i])
{
Trie* pNode = front->fail;
while (pNode && pNode->next[i] == NULL)
{
pNode = pNode->fail;
}
front->next[i]->fail = pNode? pNode->next[i] : pRoot;
if (front->next[i]->fail->flag ==
true)
{
front->next[i]->flag =
true;
}
qt.push(front->next[i]);
}
else {
front->next[i] = front == pRoot? pRoot : front->fail->next[i];
}
if (front->next[i]->flag ==
false)
{
nMatrix[front->no][front->next[i]->no]++;
}
}
}
return nP;
//節(jié)點(diǎn)總個(gè)數(shù)
}
void MultyMatrix(INT A[][MAX_P], INT B[][MAX_P], INT C[][MAX_P],
int nSize)
{
for (
int i = 0; i < nSize; ++i)
{
for (
int j = 0; j < nSize; ++j)
{
INT nSum = 0;
for (
int k = 0; k < nSize; ++k)
{
nSum = (nSum + A[i][k] * B[k][j]) % MOD;
}
C[i][j] = nSum;
}
}
}
void CopyMatrix(INT A[][MAX_P], INT B[][MAX_P],
int nSize)
{
for (
int i = 0; i < nSize; ++i)
{
for (
int j = 0; j < nSize; ++j)
{
A[i][j] = B[i][j];
}
}
}
void MatrixPower(INT M[][MAX_P],
int nSize, INT nP)
{
if (nP == 1)
{
CopyMatrix(A, M, nSize);
return;
}
MatrixPower(M, nSize, nP / 2);
MultyMatrix(A, A, B, nSize);
if (nP % 2)
{
MultyMatrix(B, M, A, nSize);
}
else {
CopyMatrix(A, B, nSize);
}
}
int main()
{
INT nM, nN;
InitIdx();
while (scanf("%I64d%I64d", &nM, &nN) == 2)
{
InitTrie(pRoot);
while (nM--)
{
scanf("%s", szPat);
Insert(szPat);
}
int nSize = BuildAC(pRoot);
MatrixPower(nMatrix, nSize, nN);
INT nAns = 0;
for (
int i = 0; i < nSize; ++i)
{
nAns = (nAns + A[0][i]) % MOD;
}
printf("%I64d\n", nAns % MOD);
}
return 0;
}