Educational Codeforces Round 8 D. Magic Numbers（数位dp）

题意:

给定两个长度≤2000的数字a,b,保证a≤b,参数m≤2000,d∈[0,9]

magic number:=从左到右,奇数位不含d,偶数只能是d,且被m整除的数字

求区间[a,b]有多少个magic number

分析:

裸数位dp,f[i][mod]:=从高到低i位,且模m余mod的magic number数

转移就按照题目转移就好,然后特判一下a是不是

代码:

//
//  Created by TaoSama on 2016-02-21
//  Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N =  + , INF = , MOD =  + ;

int n, m, d;
char a[N], b[N], *p;

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

int f[N][N];

int dfs(int i, int mod, int e) {
    if(i == n + ) return !mod;
    if(!e && ~f[i][mod]) return f[i][mod];
    int ret = , to = e ? p[i] : ;
    for(int x = ; x <= to; ++x) {
        if(i & ) {
            if(x == d) continue;
            add(ret, dfs(i + , (mod *  + x) % m, e && x == to));
        } else {
            if(x != d) continue;
            add(ret, dfs(i + , (mod *  + x) % m, e && x == to));
        }
    }
    return e ? ret : f[i][mod] = ret;
}

bool test() {
    int mod = ;
    for(int i = ; i <= n; ++i) {
        mod = (mod *  + a[i]) % m;
        if(i & ) {
            if(a[i] == d) return false;
        } else {
            if(a[i] != d) return false;
        }
    }
    return !mod;
}

int calc(char *a) {
    p = a;
    return dfs(, , );
}

int main() {
#ifdef LOCAL
    freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
//  freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio();

    while(scanf("%d%d%s%s", &m, &d, a + , b + ) == ) {
        memset(f, -, sizeof f);
        n = strlen(a + );
        for(int i = ; a[i]; ++i) a[i] -= '0';
        for(int i = ; b[i]; ++i) b[i] -= '0';
        int ans = calc(b);
        add(ans, MOD - calc(a) + test());
//      printf("%d %d\n", calc(a), calc(b));
        printf("%d\n", ans);
    }
    return ;
}