咕咕（数位dp+AC自动机）

时间：2021-02-08 15:27:19

咕咕（数位dp+AC自动机）

若一个字符串的字符集合是0~m-1，那么称它为m进制字符串。给出n个m进制字符串\(s_i\)，每个字符串的权值为\(v_i\)。对于另一个m进制字符串\(S\)，设\(s_i\)在S中的出现次数是\(cnt_i\)，那么\(s_i\)对\(S\)的价值的贡献就是\(v_i*cnt_i\)。因此，\(V_S=\Sigma_{i=1}^kcnt_i\times v_i\)。求在区间\([l, r]\)中，有多少字符串的价值不超过k。\(\Sigma_{i=1}^n|s_i|<=200\)，\(|S|<=200\)。

这道题一看就是个数位dp。可是怎么dp呢？通常，数位dp的状态是\(dp[i][j]..[0/1]\)，i表示dp到第几位，j及之后的维度表示状态的一些特征，1或0表示状态是否触顶。但是这道题，需要能从状态中判断出某个模式串是否在当前位上结束，这样才能转移。因此，没法用普通的数位dp方法解决这道题。

再来看看，如果\(l=r=S\)怎么做。我们发现，这就是上篇博客讲的多模式串匹配问题。一个模式串每匹配一次，答案就加上权值\(v_i\)。因此，可以用AC自动机来解决\(l=r\)的问题。

那么这道题怎么办呢？聪明的读者（哦不，上帝，我要用靴子狠狠地踢自己的屁股！）可能已经猜到了解法就是在AC自动机上数位dp。对于所有\(s_i\)，把它们建成一个AC自动机。用\(dp[i][j][v][0/1]\)，表示dp到原串的第i位，AC自动机上的结点为j，当前权值为v，触顶/不触顶时，有多少个数字是符合条件的。这样就能愉快的转移辣！

注意，\(s_i\)是可能有前导零的，但是\([l,r]\)中的前导零不能算。因此设置初始条件的时候一定要小心。

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long LL;

const LL maxl=205, maxm=22, maxnode=205, mod=1e9+7, maxk=505;

LL n, m, k, nl, nr, l[maxl], r[maxl];

LL cnode, son[maxnode][maxm], p[maxnode], fail[maxnode];

void ins(LL n){

    LL now=0, t;

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

        scanf("%lld", &t);

        if (!son[now][t]) son[now][t]=++cnode;

        now=son[now][t];

    }

    scanf("%lld", &t); p[now]+=t;

}

LL q[maxnode], hd, tl;

void build(){

    hd=tl=0; LL now;

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

        if (son[0][i]) q[tl++]=son[0][i];

    while (hd<tl){

        now=q[hd++];

        p[now]+=p[fail[now]];

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

        if (son[now][i])

            fail[son[now][i]]=son[fail[now]][i], q[tl++]=son[now][i];

        else son[now][i]=son[fail[now]][i];

    }

}

void up(int &x, LL v){ LL t=x+v; t%=mod; x=t; }

void up(LL &x, LL v){ x+=v; x%=mod; }

int dp[maxl][maxnode][maxk][2];

LL solve(LL *a, LL n){

    if (!n) return 0;

    memset(dp, 0, sizeof(dp));

    //下面要设置dp的初始条件

    for (LL i=1; i<a[0]; ++i)  //初始条件：第一位

        if (p[son[0][i]]<=k) up(dp[0][son[0][i]][p[son[0][i]]][0], 1);

    if (p[son[0][a[0]]]<=k) up(dp[0][son[0][a[0]]][p[son[0][a[0]]]][1], 1);

    for (LL i=1; i<n; ++i)  //枚举开头位（避免把原串的前导零计算进去）

        for (LL j=1; j<m; ++j)

            if (p[son[0][j]]<=k) up(dp[i][son[0][j]][p[son[0][j]]][0], 1);

    for (LL i=0; i<n-1; ++i)

        for (LL j=0; j<=cnode; ++j)

            for (LL t=0; t<=k; ++t)  //权值和

                if (dp[i][j][t][0]||dp[i][j][t][1])  //加速

                for (LL q=0; q<m; ++q){  //枚举下一位数字

                    LL s=son[j][q];

                    if (t+p[s]>k) continue;

                    up(dp[i+1][s][t+p[s]][0], dp[i][j][t][0]);

                    if (q<a[i+1]) up(dp[i+1][s][t+p[s]][0], dp[i][j][t][1]);

                    if (q==a[i+1]) up(dp[i+1][s][t+p[s]][1], dp[i][j][t][1]);

                }

    LL ans=0;

    for (LL j=0; j<=cnode; ++j)

        for (LL t=0; t<=k; ++t)

            up(ans, dp[n-1][j][t][0]+dp[n-1][j][t][1]);

    return ans;

}

int main(){

    scanf("%lld%lld%lld", &n, &m, &k);  //m进制，权值限制为k

    scanf("%lld", &nl);

    for (LL i=0; i<nl; ++i) scanf("%lld", &l[i]); --l[nl-1];

    for (LL i=nl-1; i>=0; --i)

        if (l[i]<0) l[i]+=m, --l[i-1]; else break;

    if (!l[0]){ for (LL i=0; i<nl-2; ++i) l[i]=l[i+1]; --nl; }

    scanf("%lld", &nr); LL t;

    for (LL i=0; i<nr; ++i) scanf("%lld", &r[i]);

    for (LL i=0; i<n; ++i) scanf("%lld", &t), ins(t);  //根据n个模式串建立ac自动机

    build();

    printf("%lld\n", (solve(r, nr)-solve(l, nl)+mod)%mod);

    return 0;

}

相关文章