20分数位DP求条,玄一贯
查看原帖
20分数位DP求条,玄一贯
945845
Chernobog_Belobog楼主2024/7/22 12:29
#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll l , r , a[17] , b[17] , n1 , n2 , dp[5][17] , k[17] = {1};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> l >> r; l--;
    while (l) {
        a[++n1] = l % 10;
        l /= 10;
    } while (r) {
        b[++n2] = r % 10;
        r /= 10;
    } for (int i = 1 ; i <= 13 ; i++) k[i] = k[i - 1] * 10;
    for (int i = 1 ; i + i <= n1 ; i++) swap(a[i] , a[n1 - i + 1]);
    for (int i = 1 ; i + i <= n2 ; i++) swap(b[i] , b[n2 - i + 1]);
    for (int i = 1 ; i <= n1 ; i++) {
        for (int j = 1 ; j < i ; j++) dp[1][a[j]] += a[i] * k[n1 - i];
        for (int j = 1 ; j < a[i] ; j++) dp[1][j] += k[n1 - i];
        if (i != 1 && a[i] > 0) dp[1][0] += k[n1 - i];
        if (i != n1) {
            for (int j = 1 ; j <= 9 ; j++) dp[1][j] += a[i] * k[n1 - i - 1] * (n1 - i);
            if (i != 1) dp[1][0] += a[i] * k[n1 - i - 1] * (n1 - i);
        }
        if (i == 1) {
            if (n1 >= 2) dp[1][0] += k[n1 - 2] * (a[1] - 1);
            for (int j = 2 ; j < n1 ; j++) dp[1][0] += (n1 - j) * k[n1 - j - 1];
        }
    }
    for (int i = 1 ; i <= n1 ; i++) dp[1][a[i]]++;
    for (int i = 1 ; i <= n2 ; i++) {
        for (int j = 1 ; j < i ; j++) dp[2][b[j]] += b[i] * k[n2 - i];
        for (int j = 1 ; j < b[i] ; j++) dp[2][j] += k[n2 - i];
        if (i != 1 && b[i] > 0) dp[2][0] += k[n2 - i];
        if (i != n2) {
            for (int j = 1 ; j <= 9 ; j++) dp[2][j] += b[i] * k[n2 - i - 1] * (n2 - i);
            if (i != 1) dp[2][0] += b[i] * k[n2 - i - 1] * (n2 - i);
        }
        if (i == 1) {
            if (n2 >= 2) dp[2][0] += k[n2 - 2] * (b[1] - 1);
            for (int j = 2 ; j < n2 ; j++) dp[2][0] += (n2 - j) * k[n2 - j - 1];
        }
    }
    for (int i = 1 ; i <= n2 ; i++) dp[2][b[i]]++;
    for (int i = 0 ; i <= 9 ; i++) cout << dp[2][i] - dp[1][i] << " ";
    return 0;
}
2024/7/22 12:29
加载中...