HDU 2243 考研路茫茫——单词情结(AC自动机+DP+快速幂）

题目链接

错的上头了...

这题是DNA的加强版，26^1 +26^2... - A^1-A^2...

先去学了矩阵的等比数列求和，学的是第二种方法，扩大矩阵的方法。剩下就是各种模板，各种套。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
#define LL unsigned __int64
#define N 100001
int t,trie[N][26],que[N],o[N],fail[N];
LL p[201][201],mat[201][201];
void CL()
{
    memset(trie,-1,sizeof(trie));
    memset(p,0,sizeof(p));
    memset(o,0,sizeof(o));
    t = 1;
}
void insert(char *s)
{
    int i,root,len;
    len = strlen(s);
    root = 0;
    for(i = 0; i < len; i ++)
    {
        if(trie[root][s[i]-'a'] == -1)
            trie[root][s[i]-'a'] = t ++;
        root = trie[root][s[i]-'a'];
    }
    o[root] = 1;
}
void build_ac()
{
    int head,tail,front,i;
    head = tail = 0;
    for(i = 0; i < 26; i ++)
    {
        if(trie[0][i] != -1)
        {
            fail[trie[0][i]] = 0;
            que[tail++] = trie[0][i];
        }
        else
        {
            trie[0][i] = 0;
        }
    }
    while(head != tail)
    {
        front = que[head++];
        if(o[fail[front]])
            o[front] = 1;
        for(i = 0; i < 26; i ++)
        {
            if(trie[front][i] != -1)
            {
                que[tail++] = trie[front][i];
                fail[trie[front][i]] = trie[fail[front]][i];
            }
            else
            {
                trie[front][i] = trie[fail[front]][i];
            }
        }
    }
}
void work()
{
    int i,j;
    for(i = 0; i < t; i ++)
    {
        if(o[i]) continue;
        for(j = 0; j < 26; j ++)
        {
            if(o[trie[i][j]]) continue;
            p[i][trie[i][j]] ++;
        }
    }
    for(i = 0; i < t; i ++)
    {
        p[i][t+i] = p[t+i][t+i] = 1;
    }
    t <<= 1;
}
LL qmod(LL n)
{
    int i,j,k;
    LL c[201][201],ans = 0;
    while(n)
    {
        if(n&1)
        {
            memset(c,0,sizeof(c));
            for(i = 0; i < t; i ++)
            {
                for(j = 0; j < t; j ++)
                {
                    for(k = 0; k < t; k ++)
                    {
                        c[i][j] += mat[i][k]*p[k][j];
                    }
                }
            }
            memcpy(mat,c,sizeof(mat));
        }
        memset(c,0,sizeof(c));
        for(i = 0; i < t; i ++)
        {
            for(j = 0; j < t; j ++)
            {
                for(k = 0; k < t; k ++)
                {
                    c[i][j] += p[i][k]*p[k][j];
                }
            }
        }
        memcpy(p,c,sizeof(p));
        n >>= 1;
    }
    for(i = t/2; i < t; i ++)
    {
        ans += mat[0][i];
    }
    return ans-1;
}

LL fastmod(LL a,LL k)
{
    LL b = 1;
    while(k)
    {
        if(k&1)
            b = a*b;
        a = a*a;
        k = k/2;
    }
    return b;
}
LL getnum(LL p,LL k)
{
    if (k <= 0) return 1;
    if (k%2 == 0)
        return ((getnum(p,k/2 - 1))*((1 + fastmod(p,k/2 + 1))) + fastmod(p,k/2));
    else
        return ((getnum(p,(k + 1)/2 - 1))*((1 + fastmod(p,(k + 1)/2))));
}
int main()
{
    int i,j,m;
    LL n;
    char ch[101];
    while(scanf("%d%I64u",&m,&n)!=EOF)
    {
        CL();
        for(i = 1; i <= m; i ++)
        {
            scanf("%s",ch);
            insert(ch);
        }
        build_ac();
        work();
        for(i = 0; i < t; i ++)
        {
            for(j = 0; j < t; j ++)
            {
                mat[i][j] = (i == j);
            }
        }
        printf("%I64u
",getnum(26,n)-1-qmod(n+1));
    }
}