CF 434C Tachibana Kanade's Tofu[数位dp+AC自动机]

• Solution

//本代码压掉后两维

#include<cstdio>

#define max(a,b) (a<b?b:a)

using namespace std;

inline void read(int &x){

    register char ch=getchar();x=;

    while(ch<''||ch>'') ch=getchar();

    while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

}

const int N=,M=;

const int mod=1e9+;

int n,m,K,cnt=,a[N],b[N];int bfs[N];

int v[N],fail[N],next[N][],trans[N][];

int f[N][N][M];

inline void insert(int l){

    int x,now=;

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

        read(x);

        if(!next[now][x]) next[now][x]=++cnt;

        now=next[now][x];

    }

    read(x);v[now]+=x;

}

inline void build_AC(){

    int l=,r=,x,y;

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

        if(next[][i]){

            x=next[][i];

            fail[x]=;

            trans[][i]=x;

            bfs[++r]=x;

        }

        else{

            trans[][i]=;

        }

    }

    while(l!=r){

        x=bfs[++l];

        v[x]+=v[fail[x]];

        for(int i=,p;i<m;i++){

            if(next[x][i]){

                y=next[x][i];

                for(p=fail[x];p&&!next[p][i];p=fail[p]);

                if(p) fail[y]=next[p][i];

                else fail[y]=;

                trans[x][i]=y;

                bfs[++r]=y;

            }

            else{

                for(p=fail[x];p&&!next[p][i];p=fail[p]);

                if(p) trans[x][i]=next[p][i];

                else trans[x][i]=;

            }

        }

    }

}

inline void Plus(int &x,int y){

    x+=y;

    if(x>=mod) x-=mod;

}

inline void prep(int bit){//无任何限制预处理

    for(int i=;i<=cnt;i++) f[][i][]=;

    for(int i=;i<=bit;i++){

        for(int j=;j<=cnt;j++){

            for(int p=,x;p<m;p++){

                x=trans[j][p];

                for(int k=v[x];k<=K;k++){

                    Plus(f[i][j][k],f[i-][x][k-v[x]]);

                }

            }

        }

    }

}

inline int work(int *a,bool flag){

    int x,y,w,ans=;

    //取出最高位后，保证无前导零后，无限制

    for(int i=;i<a[];i++){

        for(int j=;j<m;j++){

            y=trans[][j];

            w=v[y];

            for(int k=w;k<=K;k++){

                Plus(ans,f[i-][y][k-w]);

            }

        }

    }

    //走一遍上界，要保证无前导零

    x=;w=;

    for(int i=;i<=a[];i++){

        for(int j=(i==);j<a[i];j++){

            y=trans[x][j];

            for(int k=;k<=K-(w+v[y]);k++){

                Plus(ans,f[a[]-i][y][k]);

            }

        }

        x=trans[x][a[i]];

        w+=v[x];

    }

    if(flag){//上界有否取

        if(w<=K) Plus(ans,);

    }

    return ans;

}

int main(){

    read(n);read(m);read(K);

    read(a[]);for(int i=;i<=a[];i++) read(a[i]);

    read(b[]);for(int i=;i<=b[];i++) read(b[i]);

    for(int i=,l;i<=n;i++) read(l),insert(l);

    build_AC();prep(max(a[],b[]));

    printf("%d\n",(work(b,)-work(a,)+mod)%mod);

    return ;

}