【BZOJ1030】【JSOI2007】文本生成器

伦boy好像要出这样的题？

这题好像和GT考试有点像

换成AC自动机然后暴力dp

如果总单词数再大一点就得用矩阵快速幂了

// <1030.cpp> - 06/26/16 10:41:26
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=100001;
const int INF=1e9;
const int MOD=10007;
int tot=1,s[MAXN][26],fail[MAXN];
bool key[MAXN];
void get(){
    static char ch[120];
    scanf("%s",ch);
    int l=strlen(ch),now=1;
    for(int i=0;i<l;i++){
        if(!s[now][ch[i]-'A'])s[now][ch[i]-'A']=++tot;
        now=s[now][ch[i]-'A'];
        if(key[now])break;
    }
    key[now]=1;
}
queue <int> q;
lol mat[MAXN][26];
lol dp[101][MAXN];
int main(){
    int n=gi(),m=gi();
    for(int i=0;i<26;i++)s[0][i]=1;
    while(n--)get();
    q.push(1);
    while(!q.empty()){
        int now=q.front();q.pop();
        for(int i=0;i<26;i++){
            if(!s[now][i])continue;
            int f=fail[now];
            while(!s[f][i])f=fail[f];
            fail[s[now][i]]=s[f][i];
            if(key[s[f][i]])key[s[now][i]]=1;
            q.push(s[now][i]);
        }
    }
    for(int i=1;i<=tot;i++)
        for(int j=0;j<26;j++){
            if(key[i]){mat[i][j]=i;continue;}
            int now=i;
            while(!s[now][j])now=fail[now];
            mat[i][j]=s[now][j];
        }
    dp[0][1]=1;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=tot;j++)
            for(int k=0;k<26;k++)dp[i][mat[j][k]]=(dp[i][mat[j][k]]+dp[i-1][j])%MOD;
    lol ans=0;
    for(int i=2;i<=tot;i++)if(key[i])ans=(ans+dp[m][i])%MOD;
    printf("%lld",ans);
    return 0;
}

// <1030.cpp> - 06/26/16 10:41:26

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=100001;

const int INF=1e9;

const int MOD=10007;

int tot=1,s[MAXN][26],fail[MAXN];

bool key[MAXN];

void get(){

static char ch[120];

scanf("%s",ch);

int l=strlen(ch),now=1;

for(int i=0;i<l;i++){

if(!s[now][ch[i]-'A'])s[now][ch[i]-'A']=++tot;

now=s[now][ch[i]-'A'];

if(key[now])break;

}

key[now]=1;

}

queue <int> q;

lol mat[MAXN][26];

lol dp[101][MAXN];

int main(){

int n=gi(),m=gi();

for(int i=0;i<26;i++)s[0][i]=1;

while(n--)get();

q.push(1);

while(!q.empty()){

int now=q.front();q.pop();

for(int i=0;i<26;i++){

if(!s[now][i])continue;

int f=fail[now];

while(!s[f][i])f=fail[f];

fail[s[now][i]]=s[f][i];

if(key[s[f][i]])key[s[now][i]]=1;

q.push(s[now][i]);

}

for(int i=1;i<=tot;i++)

for(int j=0;j<26;j++){

if(key[i]){mat[i][j]=i;continue;}

int now=i;

while(!s[now][j])now=fail[now];

mat[i][j]=s[now][j];

}

dp[0][1]=1;

for(int i=1;i<=m;i++)

for(int j=1;j<=tot;j++)

for(int k=0;k<26;k++)dp[i][mat[j][k]]=(dp[i][mat[j][k]]+dp[i-1][j])%MOD;

lol ans=0;

for(int i=2;i<=tot;i++)if(key[i])ans=(ans+dp[m][i])%MOD;

printf("%lld",ans);

return 0;

}