BCD Code

Time limit:5000ms Memory limit:65536kB

链接

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3494

题意

给出n个01串,求出从a到b区间内有多少个数的二进制形式不包含这n个串中的任意一个。

思路

首先对于这n个串可以构造字典树,被标记的节点在构造字典树的时候向后传递,接着搞一个状态转移函数(字典树上的节点在增加0到9这10个数后转移到的节点,对于标记节点特殊处理在数位DP中终止函数时使用),这个状态转移函数在数位DP的状态转移的时候使用。然后是数位DP,从根节点开始进行转移,求结果即可。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
using namespace std;

typedef long long ll;

const ll mod = 1e9+9;
const int maxn = 2005;
const int kind = 2;

int root, cnt;
int nxt[maxn][kind];
int fail[maxn];
int mrk[maxn];

int newnode ()
{
    ++cnt;
    for (int i = 0; i < kind; ++i) {
        nxt[cnt][i] = -1;
    }
    mrk[cnt] = 0;
    return cnt;
}

void init ()
{
    cnt = -1;
    root = newnode();
}

void word_insert (char str[])
{
    int len = strlen(str);
    int now = root;
    for (int i = 0; i < len; ++i) {
        if (nxt[now][str[i]-'0'] == -1) {
            nxt[now][str[i]-'0'] = newnode();
        }
        now = nxt[now][str[i]-'0'];
    }
    mrk[now] = 1;
}

void build ()
{
    queue<int> q;
    fail[root] = root;
    for (int i = 0; i < kind; ++i) {
        if (nxt[root][i] == -1) {
            nxt[root][i] = root;
        }
        else {
            fail[nxt[root][i]] = root;
            q.push(nxt[root][i]);
        }
    }
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        mrk[now] |= mrk[fail[now]];
        for (int i = 0; i < kind; ++i) {
            if (nxt[now][i] == -1) {
                nxt[now][i] = nxt[fail[now]][i];
            }
            else {
                fail[nxt[now][i]] = nxt[fail[now]][i];
                q.push(nxt[now][i]);
            }
        }
    }
}

char keyword[25];
char ar[maxn];
char br[maxn];
int BCD[maxn][10];

int add (int pos, int k)
{
    int cur = pos;
    while (cur != root) {
        if (mrk[cur] != 0) {
            return -1;
        }
        cur = fail[cur];
    }
    for (int i = 3; i >= 0; --i) {
        pos = nxt[pos][(k>>i)&1];
        int cur = pos;
        if (mrk[cur]) {
            return -1;
        }
    }
    return pos;
}

void get_BCD ()
{
    for (int i = 0; i <= cnt; ++i) {
        for (int j = 0; j < 10; ++j) {
            BCD[i][j] = add(i, j);
        }
    }
}

ll dp[205][maxn];
int dit[205];

ll dfs (int pos, int state, bool lead, bool limit)
{
    if (pos == -1) {
        return 1;
    }
    if (!limit && !lead && dp[pos][state] != -1) {
        return dp[pos][state];
    }
    int nd = limit?dit[pos]:9;
    ll ans = 0;
    for (int i = 0; i <= nd; ++i) {
        if (lead && i == 0) {
            ans += dfs(pos-1, state, lead, limit&&(i==nd));
        }
        else {
            if (BCD[state][i] != -1) {
                ans += dfs(pos-1, BCD[state][i], 0, limit&&(i==nd));
            }
        }
        ans %= mod;
    }
    if (!limit && !lead) {
        dp[pos][state] = ans;
    }
    return ans;
}

ll solve (char str[])
{
    int pos = strlen(str);
    for (int i = 0; i < pos; ++i) {
        dit[i] = str[pos-i-1]-'0';
    }
    return dfs(pos-1, 0, 1, 1);
}

int main ()
{
    int t, n;
    scanf("%d", &t);
    while (t--) {
        init();
        scanf("%d", &n);
        memset(dp, -1, sizeof(dp));
        for (int i = 0; i < n; ++i) {
            scanf("%s", keyword);
            word_insert(keyword);
        }
        build();
        get_BCD();
        scanf("%s %s", ar, br);
        int len = strlen(ar);
        for (int i = len-1; i >= 0; --i) {
            if (ar[i] > '0') {
                --ar[i];
                break;
            }
            else {
                ar[i] = '9';
            }
        }
        ll res = solve(br)-solve(ar);
        res = (res%mod+mod)%mod;
        cout << res << '\n';
    }
    return 0;
}

发表评论