萌新刚学数位 dp,全 WA 求助
查看原帖
萌新刚学数位 dp,全 WA 求助
610557
shinzanmonoszm 妹妹楼主2023/5/1 18:29
#include<iostream>
#include<algorithm>
int f[14][10][10];
using ll = long long;
ll solve(ll n, int dig) {
    int digit[14], lpp = 0;
    ll ans = 0;
    while (n) 
        digit[++lpp] = n % 10, n /= 10;
    for (int i = 1; i < lpp; i++) 
        for (int j = 1; j < 10; j++)
            ans += f[i][j][dig];
    for (int i = 1; i < digit[lpp]; i++) ans += f[lpp][i][dig];
    ll c = 1;
    for (int i = lpp - 1; i; i--) {
        for (int j = 0; j < digit[i]; j++) ans += f[i][j][dig];
        for (int j = lpp; j > i; j--) 
            if (digit[j] == dig) ans += digit[i] * c;
        c *= 10;
    }
    return ans;
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    ll a, b, c = 1;
    std::cin >> a >> b;
    for (int i = 0; i < 10; i++) f[1][i][i] = 1;
    for (int i = 2; i <= 13; i++) {
        for (int j = 0; j < 10; j++) {
            for (int l = 0; l < 10; l++)
                for (int k = 0; k < 10; k++)
                    f[i][j][l] += f[i - 1][k][l];
            f[i][j][j] += c;
        }
        c *= 10;
    }
    for (int i = 0; i < 10; i++) 
        std::cout << solve(b, i) - solve(a - 1, i) << " ";
    return 0;
}
2023/5/1 18:29
加载中...