数位DP WA 求调!
查看原帖
数位DP WA 求调!
365585
Cyril想想楼主2023/11/17 01:52
#include <stdio.h>
const int N = 15, M = 10;
int f[N][M][M];
inline void init(const int &n = 12) {
    for (int i = 0; i < 10; i++)
        f[1][i][i] = 1;
    for (int l = 2; l <= n; l++) {  // 第l位
        for (int k = 0; k < 10; k++)  // l位数中k数码的个数
            for (int i = 0; i < 10; i++)  // 当前位是i的
                for (int j = 0; j < 10; j++) {  // 上一位是j
                    if (i ^ k) f[l][i][k] += f[l-1][j][k];
                    else {
                        for (int m = 0; m < 10; m++)
                            f[l][i][k] += f[l-1][j][m];
                    }
                }
    }
}
inline long long pow(const int &x, int n) {
    register long long ans = 1;
    while (n--) ans *= x;
    return ans;
}
inline long long query(long long x, const int &n) {
    static int a[15];
    a[a[0]=1] = x % 10;
    while (x /= 10) a[++a[0]] = x % 10;
    register long long ans = !n; // 一位数中可以有"0"
    for (int k = 1; k < a[0]; k++)
        for (int i = 1; i < 10; i++)
            ans += f[k][i][n];
    for (int i = 1; i < a[a[0]]; i++)
        ans += f[a[0]][i][n];
    for (int k = a[0]-1; k > 0; k--) {
        for (int i = 0; i < a[k]; i++)
            ans += f[k][i][n];
        for (int i = a[0]; i > k; i--)
            if (a[i] == n) ans += a[k] * pow(10, k-1);
    }
    return ans;
}
int main() {
    init();
    long long a, b;
    scanf("%lld %lld", &a, &b);
    for (int i = 0; i < 10; i++)
        printf("%lld ", query(b+1, i) - query(a, i) + (i>0));
    putchar('\n');
    return 0;
}
2023/11/17 01:52
加载中...