数位dp

例题

CF1811ECF535B牛客62880L洛谷P2602ABC317F

求第 \(k\) 个数位不包含 \(4\) 的正整数。

二分答案，使用数位dp统计 \([1,mid]\) 包含的个数即可。

代码

C++
#include <bits/stdc++.h>
using namespace std;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
long long dp[20];
int num[20];
long long dfs(int x, bool lim) {
    if (x == -1) return 1LL;
    if (lim == false && dp[x] != -1) {
        return dp[x];
    }
    int mx = lim ? num[x] : 9;
    long long res = 0;
    for (int i = 0 ; i <= mx ; i++) {
        if (i == 4) continue; // 含有 4
        res += dfs(x - 1, lim && i == mx);
    }
    if (lim == false) dp[x] = res;
    return res;
}
long long get(long long x) {
    int cnt = 0;
    while (x) {
        dp[cnt] = -1;
        num[cnt++] = x % 10;
        x /= 10;
    }
    return dfs(cnt - 1, true);
}
void solve() {
    long long x;
    cin >> x;
    long long L = 1, R = 1e18;
    while (L < R) {
        long long mid = L + R >> 1;
        if (get(mid) >= x + 1) {
            R = mid;
        } else {
            L = mid + 1;
        }
    }
    cout << L << "\n";
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

Problem - B - Codeforces

给出一个只包含4和7的数字，问它是第几个只包含4和7的正整数。

代码

C++
#include <bits/stdc++.h>
using namespace std;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
long long dp[20];
int num[20];
long long dfs(int x, bool lim) {
    if (x == -1) return 1LL;
    if (lim == false && dp[x] != -1) {
        return dp[x];
    }
    int mx = lim ? num[x] : 9;
    long long res = 0;
    for (int i = 0 ; i <= mx ; i++) {
        if (!(lim && i == 0) && i != 4 && i != 7) continue; // 不是 4 或 7 或者不是前导 0
        res += dfs(x - 1, lim && i == mx);
    }
    if (lim == false) dp[x] = res;
    return res;
}
long long get(long long x) {
    int cnt = 0;
    while (x) {
        dp[cnt] = -1;
        num[cnt++] = x % 10;
        x /= 10;
    }
    return dfs(cnt - 1, true);
}
int main() {
    long long n;
    cin >> n;
    cout << get(n) - 1;
    return 0;
}

L-7是大奖？_2023河南萌新联赛第（四）场：河南大学

问 \([L,R]\) 数位中每存在一个 \(7\)，贡献 \(3\)，数位中每存在一个 \(5\)，贡献 \(1\)，存在连续的 \(7\) 个 \(7\)，贡献 \(300\)。

代码

C++
#include <bits/stdc++.h>
using namespace std;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
long long dp[20][2][20][20][20];
int num[20];
long long dfs(int x, bool has, int len7, int cnt5, int cnt7, bool lim) {
    has |= len7 >= 7;
    if (x == -1) return cnt5 + cnt7 * 3 + 300 * has;
    if (lim == false && dp[x][has][len7][cnt5][cnt7] != -1) {
        return dp[x][has][len7][cnt5][cnt7];
    }
    int mx = lim ? num[x] : 9;
    long long res = 0;
    for (int i = 0 ; i <= mx ; i++) {
        res += dfs(
            x - 1, 
            has, 
            i == 7 ? len7 + 1 : 0, 
            cnt5 + (i == 5), 
            cnt7 + (i == 7),
            lim && i == mx
        );
    }
    if (lim == false) dp[x][has][len7][cnt5][cnt7] = res;
    return res;
}
long long get(long long x) {
    int cnt = 0;
    while (x) {
        num[cnt++] = x % 10;
        x /= 10;
    }
    return dfs(cnt - 1, false, 0, 0, 0, true);
}
void solve() {
    long long L, R;
    cin >> L >> R;
    cout << get(R) - get(L - 1) << "\n";
}
int main() {
    memset(dp, -1, sizeof dp);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

P2602 [ZJOI2010] 数字计数 - 洛谷

对每个数字进行 \(2\) 次数位dp即可。\(0\) 要特判。

代码

C++
#include <bits/stdc++.h>
using namespace std;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
long long dp[20][20][2];
int num[20];
int d;
long long dfs(int x, int cnt, bool lead0, bool lim) {
    if (x == -1) return cnt;
    if (lead0 == false && lim == false && dp[x][cnt][d != 0] != -1) {
        return dp[x][cnt][d != 0];
    }
    int mx = lim ? num[x] : 9;
    long long res = 0;
    for (int i = 0 ; i <= mx ; i++) {
        int temp = cnt + (i == d);
        if (lead0 && d == 0 && i == 0) { // 统计数字为 0, 含有前导 0 没有贡献。
            temp = 0;
        }
        res += dfs(x - 1, temp, lead0 && i == 0, lim && i == mx);
    }
    if (lead0 == false && lim == false) dp[x][cnt][d != 0] = res;
    return res;
}
long long get(long long x) {
    int cnt = 0;
    while (x) {
        num[cnt++] = x % 10;
        x /= 10;
    }
    return dfs(cnt - 1, 0, true, true);
}
int main() {
    long long L, R;
    cin >> L >> R;
    for (int i = 0 ; i < 10 ; i++) {
        memset(dp, -1, sizeof dp);
        d = i;
        cout << get(R) - get(L - 1) << " ";
    }
    return 0;
}

F - Nim

给定四个正整数 \(N,A_1,A_2,A_3\)，试求满足以下条件的三元组 \((X_1,X_2,X_3)\) 的对数，对 \(998244353\) 取模。

\(1\leq X_i\leq N\)

\(X_i \% A_i = 0\)

\((X_1\oplus X_2)\oplus x_3=0\)

代码

C++
#include <bits/stdc++.h>
using namespace std;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int A1, A2, A3;
long long dp[63][10][10][10][2][2][2][2][2][2];
int num[63];
const long long mod = 998244353;
long long dfs(int x, int p1, int p2, int p3, bool lim1, bool lim2, bool lim3, bool x1, bool x2, bool x3) {
    if (x == -1) {
        return (!p1) && (!p2) && (!p3) && x1 && x2 && x3;
    }
    if (dp[x][p1][p2][p3][lim1][lim2][lim3][x1][x2][x3] != -1) {
        return dp[x][p1][p2][p3][lim1][lim2][lim3][x1][x2][x3];
    }
    int mx1 = lim1 ? num[x] : 1;
    int mx2 = lim2 ? num[x] : 1;
    int mx3 = lim3 ? num[x] : 1;
    long long res = 0;
    for (int i = 0 ; i <= mx1 ; i++) {
        for (int j = 0 ; j <= mx2 ; j++) {
            if ((i ^ j) <= mx3) {
                int k = i ^ j;
                res = (res + dfs(
                    x - 1,
                    (p1 * 2 + i) % A1,
                    (p2 * 2 + j) % A2,
                    (p3 * 2 + k) % A3,
                    lim1 && i == num[x],
                    lim2 && j == num[x],
                    lim3 && k == num[x],
                    x1 | i,
                    x2 | j,
                    x3 | k
                )) % mod;
            }
        }
    }
    return dp[x][p1][p2][p3][lim1][lim2][lim3][x1][x2][x3] = res;
}
long long get(long long x) {
    int cnt = 0;
    while (x) {
        num[cnt++] = x % 2;
        x /= 2;
    }
    return dfs(cnt - 1, 0, 0, 0, true, true, true, false, false, false);
}
int main() {
    memset(dp, -1, sizeof dp);
    long long n;
    cin >> n >> A1 >> A2 >> A3;
    cout << get(n);
    return 0;
}

习题

洛谷P8766CF104053M

P8766 [蓝桥杯 2021 国 AB] 异或三角 - 洛谷

因为 \(a\oplus b\oplus c=0\)，所以 \(a=b\oplus c\)。

因为要构成三角形，令 \(a\) 为最大的边，则有 \(a< b+c\)，即 \(b\oplus c< b+c\)

易知对于任意 \(b,c\) 有 \(b\oplus c< b+c\)。

如果想要 \(b\oplus c< b+c\)，则 \(b,c\) 二进制某一位一定都是 \(1\)。

所以数位dp即可。

代码

C++
#include <bits/stdc++.h>
using namespace std;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
long long dp[31][2][2][2][2];
int num[31];
long long dfs(int x, bool lim1, bool lim2, bool lim3, bool flag) {
    if (x == -1) {
        return flag;
    }
    if (dp[x][lim1][lim2][lim3][flag] != -1) {
        return dp[x][lim1][lim2][lim3][flag];
    }
    int mx1 = lim1 ? num[x] : 1;
    long long res = 0;
    for (int i = 0 ; i <= mx1 ; i++) {
        int mx2 = lim2 ? i : 1;
        int mx3 = lim3 ? i : 1;
        for (int j = 0 ; j <= mx2 ; j++) {
            int k = (i ^ j);
            if (k <= mx3) {
                res += dfs(
                    x - 1, 
                    lim1 && i == num[x], 
                    lim2 && j == i, 
                    lim3 && k == i,
                    flag || (j + k == 2)
                );
            }
        }
    }
    dp[x][lim1][lim2][lim3][flag] = res;
    return res;
}
long long get(int x) {
    int cnt = 0;
    while (x) {
        num[cnt++] = x % 2;
        x /= 2;
    }
    return dfs(cnt - 1, true, true, true, false) * 3;
}
void solve() {
    memset(dp, -1, sizeof dp);
    int n;
    cin >> n;
    cout << get(n) << "\n";
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

Problem - M - Codeforces

数位dp枚举二进制的01, 存s为有多少位是lim, 存sum表示对数列两两之间的异或和。

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();//
const i64 P = 1000000007;
i64 c[62][62];
i64 C(int n, int m) {
    if (n < m && m < 0) return 0;
    return c[n][m];
}
i64 n, m;
int k;
int num[62];
map<i64, i64> dp[62][62];
i64 dfs(int x, int s = k, i64 sum = 0) {
    if (sum > n) return 0LL;
    if (x == -1) {
        return sum == n;
    }
    int k1 = k / 2, k2 = k - k1;
    if (sum + ((1LL << x + 1) - 1) * k1 * k2 < n) {
        return 0LL;
    }
    if (dp[x][s].count(sum)) {
        return dp[x][s][sum];
    }
    i64 res = 0;
    if (num[x] == 1) {
        for (int i = 0 ; i <= s ; i++) {
            for (int j = 0 ; j <= k - s ; j++) {
                res = (res + C(s, i) * C(k - s, j) % P * dfs(x - 1, i, sum + (1LL << x) * (k - i - j) * (i + j)) % P) % P;
            }
        }
    } else {
        for (int i = 0 ; i <= k - s ; i++) {
            res = (res + C(k - s, i) * dfs(x - 1, s, sum + (1LL << x) * (k - i) * i) % P) % P;
        }
    }
    dp[x][s][sum] = res;
    return res;
}
i64 get(i64 x) {
    int cnt = 0;
    do {
        num[cnt++] = x % 2;
        x /= 2;
    } while (x);
    return dfs(cnt - 1);
}
int main() {
    c[0][0] = 1;
    for (int i = 1 ; i < 62 ; i++) {
        c[i][0] = 1;
        for (int j = 1 ; j <= i ; j++) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P;
        }
    }
    cin >> n >> m >> k;
    cout << get(m);
    return 0;
}