题解：P9092 [PA 2020] Liczba Potyczkowa

· · 题解

很愤怒的一道题。

Solution

首先讲一个简单的解法。考虑当 y\ |\ z 时，有 x \bmod y = (x \bmod z) \bmod y，然后就考虑取 1 \sim 9 的最小公倍数 2520 为初始模数，最后判一下能不能整除包含的数即可（因为没想到这一点而愤怒）。

那就直接状态压缩数位 dp，考虑设 f_{i, 0/1, S, k} 表示，前 i 高位，是否卡着限制，所用数的集合为 S，且当前数 \text{}\bmod 2520 为 k 的方案数。

转移是显然的。

:::success[AC Code]

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(Tx, Ty) make_pair(Tx, Ty)
#define For(Ti, Ta, Tb) for(auto Ti = (Ta); Ti <= (Tb); Ti++)
#define Dec(Ti, Ta, Tb) for(auto Ti = (Ta); Ti >= (Tb); Ti--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
const int N = 20, M = 2520;
const long long INF = 1e18;
long long L, R;
long long f[2][2][(1 << 9)][2525];
long long work(long long x) {
    if (x == 0) return 0;
    vector<int> num;
    while (x) num.push_back(x % 10), x /= 10;
    reverse(range(num));
    int sz = num.size();
    int flag = 0;
    memset(f, 0, sizeof(f));
    f[0][1][0][0] = 1;
    For(i, 0, sz - 1) {
        memset(f[flag ^ 1], 0, sizeof(f[flag ^ 1]));
        f[flag ^ 1][0][0][0] = 1;
        For(op, 0, 1) {
            For(S, 0, (1 << 9) - 1) {
                For(k, 0, M - 1) {
                    if (!f[flag][op][S][k]) continue;
                    int lim = (op == 0 ? 9 : num[i] - 1);
                    long long val = f[flag][op][S][k];
                    For(x, 1, lim) {
                        f[flag ^ 1][0][S | (1 << x - 1)][(k * 10 + x) % M] += val;
                    }
                    if (op && num[i]) {
                        int x = num[i];
                        f[flag ^ 1][1][S | (1 << x - 1)][(k * 10 + x) % M] += val;
                    }
                }
            }
        }
        flag ^= 1;
    }
    long long ans = 0;
    For(S, 1, (1 << 9) - 1) {
        For(k, 0, M - 1) {
            //if (f[flag][0][S][k]) cout << f[flag][0][S][k] << ' ';
            bool g = 1;
            For(j, 1, 9) {
                if (S >> (j - 1) & 1) {
                    if (k % j) {
                        g = 0;
                        break;
                    }
                }
            }
            if (g) ans += f[flag][0][S][k] + f[flag][1][S][k];
        }
    }
    return ans;
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> L >> R;
    if (L == INF) L--;
    if (R == INF) R--;
    long long ans = work(R);
    if (L > 1) ans -= work(L - 1);
    cout << ans;
    return 0;
}

:::