P3715 [BJOI2017]魔法咒语

用基本词汇组成$L$长度的单词，其中不能包含禁忌词汇

用禁忌词汇建强大的$tire$图

解决：

分类讨论，$L<=100$用普通dp暴力在$tire$图上用基本词汇跑，不能包含禁忌词汇

显然，$L<=10^8$肯定会超时的，注意到基本词汇的长度$<=2$，矩阵优化一下

构造矩阵是一个难点，左边的矩阵两部分，我们要把$dp_{i-2}与dp_{i-1}$矩乘后达到$dp_{i-1}与dp_{i}$

右边的矩阵四部分

$(1)空 (2)len=2$

$(3)单位矩阵(4)len=1 $

构造到此为止直接快速幂就好了

My complete code

#include<bits/stdc++.h>

#include<queue>

using namespace std;

typedef long long LL;

const LL maxn=1010;

const LL MOD=1e9+7;

LL n,m,L,nod=1,ans;

LL son[maxn][30],end[maxn],fail[maxn],len[maxn],dp[maxn][maxn];

char ji[maxn][maxn];

inline void Insert(char *s){

    LL l=strlen(s),now=1;

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

        LL c=s[i]-'a';

        if(!son[now][c])

            son[now][c]=++nod;

        now=son[now][c];

    }

    end[now]=true;

}

inline void Fbuild(){

    queue<LL> que;

    for(LL i=0;i<26;++i)

        if(son[1][i]){

            que.push(son[1][i]);

            fail[son[1][i]]=1;

        }else

            son[1][i]=1;

    while(que.size()){

        LL u=que.front(); que.pop();

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

            LL v=son[u][i];

            if(v){

                fail[v]=son[fail[u]][i];

                que.push(v);

                end[v]|=end[fail[v]];

            }else

                son[u][i]=son[fail[u]][i];

        }

    }

}

struct mat{

    LL m[300][300];

}a,b,r;

inline LL Go(LL now,LL c){

    return (end[son[now][c]])?-1:son[now][c];

}

inline mat Mul(const mat &x,const mat &y){

    mat res;

    memset(res.m,0,sizeof(res.m));

    for(LL i=1;i<=2*nod;++i)

        for(LL j=1;j<=2*nod;++j)

            for(LL k=1;k<=2*nod;++k)

                res.m[i][j]=(res.m[i][j]+x.m[i][k]*y.m[k][j]%MOD)%MOD;

    return res;

}

inline void Pow(LL mi){

    while(mi){

        if(mi&1)

            r=Mul(r,b);

        b=Mul(b,b);

        mi>>=1;

    }

}

int main(){

    scanf("%lld%lld%lld",&n,&m,&L);

    for(LL i=1;i<=n;++i){

        scanf(" %s",ji[i]);

        len[i]=strlen(ji[i]);

    }

    for(LL i=1;i<=m;++i){

        char s[maxn];

        scanf(" %s",s);

        Insert(s);

    }

    Fbuild();

    if(L<=100){

        dp[0][1]=1;

        for(LL i=0;i<L;++i)

            for(LL j=1;j<=nod;++j){

            	if(!dp[i][j])

            	    continue;

            	for(LL k=1;k<=n;++k){//沿着基本串走

            	    if(i+len[k]>L)

            	        continue;

            	    LL now=j;

            	    for(LL q=0;q<len[k]&&now!=-1;++q)

                        now=Go(now,ji[k][q]-'a');

            	    if(now!=-1)

            	        dp[i+len[k]][now]=(dp[i+len[k]][now]+dp[i][j])%MOD;

                }

            }

        for(LL i=1;i<=nod;++i)

            ans=(ans+dp[L][i])%MOD;

        printf("%lld",ans);

        return 0;

    }

    a.m[1][1+nod]=1;

    for(LL i=1;i<=nod;++i)

        b.m[i+nod][i]=1;

    for(LL i=1;i<=nod;++i)

        for(LL j=1;j<=n;++j){

        	if(len[j]!=1)

        	    continue;

        	LL now=i;

        	if(end[now])

        	    continue;

        	now=Go(now,ji[j][0]-'a');

        	if(now!=-1)

        	    ++b.m[nod+i][nod+now];

        }

    for(LL i=1;i<=nod;++i)

        for(LL j=1;j<=n;++j){

        	if(len[j]!=2)

        	    continue;

        	LL now=i;

        	if(end[now])

        	    continue;

        	now=Go(now,ji[j][0]-'a');

        	if(now==-1)

        	    continue;

        	now=Go(now,ji[j][1]-'a');

        	if(now!=-1)

        	    ++b.m[i][nod+now];

        }

    for(LL i=1;i<=2*nod;++i)

        r.m[i][i]=1;

    Pow(L);

    a=Mul(a,r);

    for(LL i=1;i<=nod;++i)

        ans=(ans+a.m[1][nod+i])%MOD;

    printf("%lld",ans);

    return 0;

}

巴特西

P3715 [BJOI2017]魔法咒语

My complete code

最新文章

热门文章