M_sea

洛谷3311 [SDOI2014]数数
LuoguBZOJ分析好像和GT考试那题差不多。设$f[i][j][0/1]$表示前$i$位,在AC自动机上匹配到...
扫描右侧二维码阅读全文
09
2019/01

洛谷3311 [SDOI2014]数数

Luogu

BZOJ

分析

好像和GT考试那题差不多。

设$f[i][j][0/1]$表示前$i$位,在AC自动机上匹配到了第$j$个节点,是否到了$n$的上界的方案数。

然后分情况转移。

  • 若前一位和这一位都没有到上界:$\large f[i-1][p][0]\to f[i][ch[p][0\sim9]][0]$
  • 若前一位到了上界,这一位没有到上界:$\large f[i-1][p][1]\to f[i][ch[p][0\sim upper_i-1][0]$
  • 若前一位和这一位都到了上界:$\large f[i-1][p][1]\to f[i][ch[p][upper_i][1]$

设AC自动机上有$tot$个节点,答案为$\large\sum\limits_{i=1}^{tot}(f[len][tot][0]+f[len][tot][1])$。

另外,还可以滚动$f$数组优化空间。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=1500+10;
const int MOD=1e9+7;

struct node {
    int ch[10],fail,lt;
} a[MAXN];
int cnt=0;

inline void build(char* s,int l) {
    int now=0;
    for (re int i=0;i<l;++i) {
        if (!a[now].ch[s[i]-'0']) a[now].ch[s[i]-'0']=++cnt;
        now=a[now].ch[s[i]-'0'];
    }
    a[now].lt=1;
}

inline void getFail() {
    queue<int> Q; Q.push(0);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        a[u].lt|=a[a[u].fail].lt;
        for (re int i=0;i<=9;++i) {
            if (a[u].ch[i]) {
                if (u) a[a[u].ch[i]].fail=a[a[u].fail].ch[i];
                Q.push(a[u].ch[i]);
            }
            else a[u].ch[i]=a[a[u].fail].ch[i];
        }
    }
}

char tmp[MAXN];
int n[MAXN];
int f[2][MAXN][2]; //f[i][j][0/1]表示前i位,在j号节点,是否到了上界的答案

inline void pls(int& x,int y) { x+=y; if (x>=MOD) x-=MOD; }

int main() {
    scanf("%s",tmp+1); int l=strlen(tmp+1);
    for (re int i=1;i<=l;++i) n[i]=tmp[i]-'0';
    int m=read();
    for (re int i=1;i<=m;++i) {
        scanf("%s",tmp+1);
        build(tmp+1,strlen(tmp+1));
    }
    getFail();
    for (re int i=1;i<n[1];++i) pls(f[1][a[0].ch[i]][0],1);
    pls(f[1][a[0].ch[n[1]]][1],1);
    for (re int i=2;i<=l;++i) {
        int now=i&1,pre=now^1;
        memset(f[now],0,sizeof(f[now]));
        for (re int j=1;j<=9;++j) pls(f[now][a[0].ch[j]][0],1);
        for (re int p=0;p<=cnt;++p) {
            if (a[p].lt) continue;
            if (f[pre][p][0])
                for (re int j=0;j<=9;++j)
                    if (!a[a[p].ch[j]].lt)
                        pls(f[now][a[p].ch[j]][0],f[pre][p][0]);
            if (f[pre][p][1])
                for (re int j=0;j<n[i];++j)
                    if (!a[a[p].ch[j]].lt)
                        pls(f[now][a[p].ch[j]][0],f[pre][p][1]);
            if (!a[a[p].ch[n[i]]].lt)
                pls(f[now][a[p].ch[n[i]]][1],f[pre][p][1]);
        }
    }
    int ans=0;
    for (re int i=0;i<=cnt;++i)
        if (!a[i].lt) pls(ans,f[l&1][i][0]),pls(ans,f[l&1][i][1]);
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 05 月 26 日 05 : 49 PM

发表评论