【bzoj1030】[JSOI2007]文本生成器

2015.04.15 09:16 Wed | 1次阅读 | 旧日oi | 固定链接 | 源码

Description

JSOI交给队员ZYX一个任务,编制一个称之为“文本生成器”的电脑软件:该软件的使用者是一些低幼人群,他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文章—— 也就是说,生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词,那么我们说这篇文章是可读的(我们称文章a包含单词b,当且仅当单词b是文章a的子串)。但是,即使按照这样的标准,使用者现在使用的GW文本生成器v6版所生成的文章也是几乎完全不可读的。 ZYX需要指出GW文本生成器 v6生成的所有文本中可读文本的数量,以便能够成功获得v7更新版。你能帮助他吗?

Input

输入文件的第一行包含两个正整数,分别是使用者了解的单词总数N (<= 60),GW文本生成器 v6生成的文本固定长度M;以下N行,每一行包含一个使用者了解的单词。 这里所有单词及文本的长度不会超过100,并且只可能包含英文大写字母A..Z  。

Output

一个整数,表示可能的文章总数。只需要知道结果模10007的值。

Sample Input

2 2
A
B

Sample Output

100

题解

昨天写完了GT考试的题解之后,今天再看这道题真是变的简单多了,又按自己的方法写了一遍,很快就过了。
然后我又改成矩阵乘法的形式,自己拍小数据都过了,结果因为节点过多,光荣的编译失败了,但是bz上竟然显示tle,时间是0ms……
非矩阵版

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 100010
#define ll long long
#define mod 10007
#define inf 0x3f3f3f3f
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
ll qpow(ll x,int k)
{
    ll ret=1;
    while(k)
    {
        if(k&1) ret=ret*x%mod;
        k>>=1;
        x=x*x%mod;
    }
    return ret;
}
struct ACM{
    char s[105];
    int son[6005][26],tot;
    int fail[6005];
    bool mark[6005];
    void insert()
    {
        scanf("%s",s);
        int l=strlen(s),x=0;
        for(int i=0;i<l;i++) 
        {
            if(!son[x][s[i]-'A']) son[x][s[i]-'A']=++tot;
            x=son[x][s[i]-'A'];
        }
        mark[x]=1;
    }
    queue<int> q;
    void build()
    {
        for(int i=0;i<26;i++)
        if(son[0][i]) q.push(son[0][i]);
        while(!q.empty())
        {
            int u=q.front(),v,k;q.pop();
            for(int i=0;i<26;i++)
            if(k=son[u][i])
            {
                for(v=fail[u];v&&!son[v][i];v=fail[v]);
                fail[k]=v=son[v][i];
                mark[k]=(mark[k]||mark[v]);
                q.push(k);
            }
        }
    }
    ll f[105][6005];
    void DP()
    {
        f[0][0]=1;
        for(int i=0;i<m;i++)
        for(int j=0;j<=tot;j++)
        if(f[i][j])
        {
            for(int k=0;k<26;k++)
            {
                int tmp=j;
                for(;tmp&&!son[tmp][k];tmp=fail[tmp]);
                tmp=son[tmp][k];
                if(!mark[tmp]) f[i+1][tmp]=(f[i+1][tmp]+f[i][j])%mod;
            }
        }
        ll ans=0;
        for(int i=0;i<=tot;i++) ans=(ans+f[m][i])%mod;
        printf("%lld\n",(qpow(26,m)-ans+mod)%mod);
    }
}acm;
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++) acm.insert();
    acm.build();
    acm.DP();
}
矩阵版(矩阵的数组开小点就能运行了)
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 100010
#define ll long long
#define mod 10007
#define inf 0x3f3f3f3f
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,tot;
ll qpow(ll x,int k)
{
    ll ret=1;
    while(k)
    {
        if(k&1) ret=ret*x%mod;
        k>>=1;
        x=x*x%mod;
    }
    return ret;
}
struct Matrix{
    int m[6005][6005];
}ans,f,ret,c;
Matrix operator *(Matrix a,Matrix b)
{
    memset(&c,0,sizeof(c));
    for(int i=0;i<=tot;i++)
    for(int j=0;j<=tot;j++)
    for(int k=0;k<=tot;k++)
    c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
    return c;
}
Matrix mpow(Matrix x,int k)
{
    for(int i=0;i<=tot;i++) ret.m[i][i]=1;
    while(k)
    {
        if(k&1) ret=ret*x;
        k>>=1;
        x=x*x;
    }
    return ret;
}
struct ACM{
    char s[105];
    int son[6005][26];
    int fail[6005];
    bool mark[6005];
    void insert()
    {
        scanf("%s",s);
        int l=strlen(s),x=0;
        for(int i=0;i<l;i++) 
        {
            if(!son[x][s[i]-'A']) son[x][s[i]-'A']=++tot;
            x=son[x][s[i]-'A'];
        }
        mark[x]=1;
    }
    queue<int> q;
    void build()
    {
        for(int i=0;i<26;i++)
        if(son[0][i]) q.push(son[0][i]);
        while(!q.empty())
        {
            int u=q.front(),v,k;q.pop();
            for(int i=0;i<26;i++)
            if(k=son[u][i])
            {
                for(v=fail[u];v&&!son[v][i];v=fail[v]);
                fail[k]=v=son[v][i];
                mark[k]=(mark[k]||mark[v]);
                q.push(k);
            }
        }
    }
    void DP()
    {
        for(int j=0;j<=tot;j++)
        for(int k=0;k<26;k++)
        if(!mark[j])
        {
            int tmp=j;
            for(;tmp&&!son[tmp][k];tmp=fail[tmp]);
            tmp=son[tmp][k];
            if(!mark[tmp]) f.m[j][tmp]=(f.m[j][tmp]+1)%mod;
        }
        ans=mpow(f,m);int ret=0;
        for(int i=0;i<=tot;i++) ret=(ret+ans.m[0][i])%mod;
        printf("%lld\n",(qpow(26,m)-ret+mod)%mod);
    }
}acm;
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++) acm.insert();
    acm.build();
    acm.DP();
}```