HDU2243 考研路茫茫――单词情结

Description

背单词，始终是复习英语的重要环节。在荒废了3年大学生涯后，Lele也终于要开始背单词了。
一天，Lele在某本单词书上看到了一个根据词根来背单词的方法。比如"ab",放在单词前一般表示"相反，变坏，离去"等。

于是Lele想，如果背了N个词根，那这些词根到底会不会在单词里出现呢。更确切的描述是：长度不超过L，只由小写字母组成的，至少包含一个词根的单词，一共可能有多少个呢？这里就不考虑单词是否有实际意义。

比如一共有2个词根 aa 和 ab ，则可能存在104个长度不超过3的单词，分别为
(2个) aa,ab,
(26个)aaa,aab,aac...aaz,
(26个)aba,abb,abc...abz,
(25个)baa,caa,daa...zaa,
(25个)bab,cab,dab...zab。

这个只是很小的情况。而对于其他复杂点的情况，Lele实在是数不出来了，现在就请你帮帮他。

Input

本题目包含多组数据，请处理到文件结束。
每组数据占两行。
第一行有两个正整数N和L。(0<N<6,0<L<2^31)
第二行有N个词根，每个词根仅由小写字母组成，长度不超过5。两个词根中间用一个空格分隔开。

Output

对于每组数据，请在一行里输出一共可能的单词数目。
由于结果可能非常巨大，你只需要输出单词总数模2^64的值。

Sample Input

2 3 aa ab 1 2 a

Sample Output

104 52

容斥

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

inline int f(char u){
    return u-'a';
}
struct tree{
    int f;
    bool w;
    int t[26];
}t[10001];
int n,m,num=0;
struct MX{
    unsigned long long c[50][50];
};
char s[1000];
bool ma[50],us[50];
queue <int> q;
MX a,o;
inline bool dfs(int x){
    if (x==0) return 1;
    if (t[x].w) return 0;
    if (us[x]) return ma[x];
    us[x]=1;
    return ma[x]=dfs(t[x].f);
}
inline void in(){
    int p=0,l,m=strlen(s);
    for (register int i=0;i<m;i++){
        l=f(s[i]);
        if (!t[p].t[l]) t[p].t[l]=++num;
        p=t[p].t[l];
    }
    t[p].w=1;
}
inline void mafa(){
    register int i;int k,p;
    q.push(0);t[0].f=0;
    while(!q.empty()){
        k=q.front();q.pop();
        for (i=0;i<26;i++)
        if (t[k].t[i]){
            p=t[k].f;
            while((!t[p].t[i])&&p) p=t[p].f;
            t[t[k].t[i]].f=(k==p)?0:t[p].t[i];
            q.push(t[k].t[i]);
        }
    }
}
inline MX cheng(MX x,MX y){
    register int i,j,k;
    MX z;
    for (i=0;i<=num;i++)
    if (ma[i])
    for (j=0;j<=num;j++)
    if (ma[j]){
        z.c[i][j]=0;
        for (k=0;k<=num;k++)
        if (ma[k])
        z.c[i][j]+=x.c[i][k]*y.c[k][j];
    }
    return z;
}
inline MX mi(MX x,int b){
    register int i,j;
    MX z=x;b--;
    while(b){
        if (b&1) z=cheng(z,x);
        b>>=1;
        x=cheng(x,x);
    }
    return z;
}
int main(){
    register int i,j;int u;
    unsigned long long ans;
    while(~scanf("%d%d",&n,&m)){
        u=ans=0;
        for (i=0;i<=num;i++)
        for (j=0;j<26;j++) t[i].t[j]=0;
        for (i=0;i<=num;i++) ma[i]=us[i]=t[i].w=t[i].f=0;
        num=1;
        a.c[0][0]=26;
        a.c[1][0]=a.c[1][1]=1;
        ma[1]=ma[0]=1;
        o=mi(a,m);
        ma[1]=ma[0]=0;
        ans=o.c[1][0]+o.c[0][0];
        for (i=0;i<=num;i++)
        for (j=0;j<=num;j++)
        a.c[i][j]=0;
        num=0;
        for (i=1;i<=n;i++){
              scanf("%s",s);
            in();
        }
        mafa();
        for (i=0;i<=num;i++)
        ma[i]=dfs(i);
        for (i=0;i<=num;i++)
        if (ma[i])
        for (j=0;j<26;j++){
            if (!t[i].t[j]){
                u=t[i].f;
                while(!t[u].t[j]&&u)u=t[u].f;
                u=t[u].t[j];
            }else u=t[i].t[j];
            a.c[i][u]++;
        }
        num++;
        ma[num]=1;
        for (i=0;i<=num;i++) a.c[i][num]=1;
        o=mi(a,m);
        for (i=0;i<=num;i++)
        if (ma[i])
        ans-=o.c[0][i];
        for (i=0;i<=num;i++)
        for (j=0;j<=num;j++)
        a.c[i][j]=0;
        printf("%llu
",ans);
    }
}

View Code