「Codeforces 628D」Magic Numbers - 数位 DP

我们认为一个数是 d-magic 的，当且仅当数字 出现在这个数字的十进制表示的所有偶数位上，而不会出现在其它位上。

例如， 是 7-magic 的，但 不是 7-magic 的。

找出能被 m 整除的 d-magic 的数字在区间 内的数量。

链接

Codeforces 628D

题解

数位 DP，设

表示数字的最后 位，最高位最大为 ，模 的余数为 的数量。

对于 的限制，我们通常定义函数 表示 中的数量，求出 ，但这道题目中 是高精度数，不方便做减法，可以先求出 ，然后特判 是否有效。

代码

// #pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <cstring>
#include <algorithm>

const int MAXN = 2000;
const int MAXM = 2000;
const int MAXD = 9;
const int MOD = 1e9 + 7;
const int LIMIT_UNLIMITED = 10;

int a[MAXN];
int mem[MAXN + 1][11][MAXM + 1];
bool calced[MAXN + 1][11][MAXM + 1];

int pow10[MAXN + 1];

int n, d, m;
bool isEven[MAXN];

inline void prepare() {
    pow10[0] = 1;
    for (int i = 1; i <= MAXN; i++)  {
        pow10[i] = static_cast<long long>(pow10[i - 1]) * 10 % m;
    }
}

inline int modm(const int r) {
    return ((r % m) + m) % m;
}

inline int mul(const int x, const int n) {
    return static_cast<long long>(pow10[n]) * x % m;
}

inline int dec(const int r, const int x) {
    return modm(r - x);
}

// int A[MAXN];
inline int dp(const int n, const int limit, const int r) {
    int &ans = mem[n][limit][r];
    if (calced[n][limit][r]) return ans;
    calced[n][limit][r] = true;

    if (n == 0) {
        if (r == 0) ans = 1;
        else ans = 0;
        // if (ans == 1) {
        //     for (int i = 0; i < ::n; i++) putchar('0' + A[i]);
        //     putchar('\n');
        // }
    } else {
        int next;
        if (n != 1) next = a[::n - n + 1];
        else next = LIMIT_UNLIMITED;

        int _l, _r;
        if (isEven[n]) _l = d, _r = std::min(limit, d);
        else _l = 0, _r = std::min(limit, 9);

        for (int i = _l; i <= _r; i++) {
            // A[::n - n] = i;

            if (!isEven[n] && i == d) continue;
            // if (isEven[n] && i != d) continue;

            int t;
            if (i < limit || limit == LIMIT_UNLIMITED) {
                t = LIMIT_UNLIMITED;
            } else {
                t = next;
            }

            ans = (ans + dp(
                    n - 1,
                    t,
                    dec(r, mul(i, n - 1))
            )) % MOD;
        }
    }

    // if (r == 178) printf("f[%d][%d][%s][%d] = %d\n", n, limit, isEven ? "true" : "false", r, ans);
    return ans;
}

inline int solve(const char *s) {
    memset(mem, 0, sizeof(mem));
    memset(calced, 0, sizeof(calced));

    for (int i = 0; i < n; i++) a[i] = s[i] - '0';

    int ans = 0, &limit = a[0];
    for (int i = 1; i <= std::min(limit, 9); i++) {
        if (i == d) continue;

        int t;
        if (i < limit || n == 1) {
            t = LIMIT_UNLIMITED;
        } else {
            t = a[1];
        }

        // A[0] = i;
        ans = (ans + dp(n - 1, t, dec(0, mul(i, n - 1)))) % MOD;
    }

    // printf("solve(%s) = %d\n", s, ans);
    return ans;
}

inline int judge(const char *s) {
    int r = 0;
    bool isEven = false;
    for (int i = 0; i < n; i++) {
        if (!isEven && s[i] - '0' == d) return 0;
        if (isEven && s[i] - '0' != d) return 0;

        r = modm(r - mul(s[i] - '0', n - i - 1));
        isEven ^= 1;
    }
    return r == 0 ? 1 : 0;
}

int main() {
    // int size = 16 << 20;
    // char *p = (char *)malloc(size) + size;
    // __asm__("movq %0, %%rsp\n" :: "r"(p));
    // __asm__("movl %0, %%esp\n" :: "r"(p));

    static char s1[MAXN + 1], s2[MAXN + 1];
    scanf("%d %d\n%s\n%s", &m, &d, s1, s2);

    prepare();
    n = strlen(s1);

    isEven[n - 1] = true;
    for (int i = n - 2; i >= 0; i--) isEven[i] = !isEven[i + 1];

    int ans = (solve(s2) - solve(s1) + judge(s1)) % MOD;
    printf("%d\n", (ans + MOD) % MOD);

    // exit(0);
    return 0;
}