数位dp练习

hdu3555 Bomb

题面：求1~n中有多少个数包含子串"49"，n在int64范围内。

分析：直接统计含子串49的数不方便，考虑统计不含49的数的个数cnt，那么n-cnt即为所求。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL dp[20][10];
void init() {
    dp[0][0] = 1;
    for (int i = 1; i < 20; i++)
    for (int j = 0; j < 10; j++)
    for (int k = 0; k < 10; k++)
        if (!(j == 4 && k == 9))
            dp[i][j] += dp[i-1][k];
}
LL go(LL n) { // range: 0 ~ n-1
    LL d[20] = {0}, l = 1, ans = 0;
    for (LL t = n; t; t /= 10)
        d[l++] = t % 10;
    for (int i = l-1; i > 0; i--) {
        for (int j = 0; j < d[i]; j++)
            if (!(j == 9 && d[i] == 4))
                ans += dp[i][j];
        if (d[i] == 9 && d[i+1] == 4)
            break;
    }
    return ans;
}
LL solve(LL n) { // range: 1 ~ n
    return go(n+1) - go(1);
}
int main() {
    init();
    LL T, n, cnt;
    cin >> T;
    while (T--) {
        cin >> n;
        cout << n - solve(n) << endl;
    }
    return 0;
}

hdu2089 不要62

题面：如果数字x的10进制表示中存在数字4或者子串62，则称x是不吉利的数字，现给定区间[l,r]，问区间中有多少个吉利数字。(0<l<=r<1e6)

#include <bits/stdc++.h>
using namespace std;
int dp[10][10];
void init() {
    dp[0][0] = 1;
    for (int i = 1; i < 10; i++)
    for (int j = 0; j < 10; j++)
    for (int k = 0; k < 10; k++)
        if (!(j == 4 || (j == 6 && k == 2)))
            dp[i][j] += dp[i-1][k];
}
int go(int n) {
    int d[10] = {0}, l = 1, ans = 0;
    for (int t = n; t; t /= 10)
        d[l++] = t % 10;
    for (int i = l-1; i > 0; i--) {
        for (int j = 0; j < d[i]; j++)
            if (!(j == 2 && d[i+1] == 6))
                ans += dp[i][j];
        if (d[i] == 4 || (d[i] == 2 && d[i+1] == 6))
            break;
    }
    return ans;
}
int main() {
    init();
    int n, m;
    while (cin >> n >> m, n || m)
        cout << go(m+1) - go(n) << endl;
    return 0;
}

51nod1042 数字0-9的数量

题面：给出一段区间[a,b]，统计这个区间内数字0-9出现的次数。(1<=a<=b<=1e18)

分析：设f(x)表示区间1~x的答案，那么区间的答案可表示f(b)-f(a-1)，这样就只需要关注如何统计1~n就可以了。做法大致是按位统计，由于不允许有前导0，0的统计要单独处理。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL x[10], y[10];
void go(LL n, LL cnt[]) {
    LL a, b, c, f = 1;
    while (n >= f) {
        a = n / f / 10;
        b = n / f % 10;
        c = n % f;
        if (b == 0)
            cnt[0] += (a-1) * f + c + 1;
        else
            cnt[0] += a * f;
        for (int i = 1; i < 10; i++) {
            if (i < b)  cnt[i] += (a+1) * f;
            if (i > b)  cnt[i] += a * f;
            if (i == b) cnt[i] += a * f + c + 1;
        }
        f *= 10;
    }
}
int main() {
    LL a, b;
    cin >> a >> b;
    go(a-1, x); go(b, y);
    for (int i = 0; i < 10; i++)
        cout << y[i] - x[i] << endl;
    return 0;
}

51nod1043 幸运号码

题面：对于长度为2n的号码（无前导0），如果其左边n位数的和与右边n位数的和相等，则称该号码为幸运号码。已知n，求长度为2n的幸运号码的数量对1e9+7取模的结果。

分析：设dp[i][j]表示长度为i、各位数之和为j的数字串（可以有前导0），那么dp[i+1][j]=sum(dp[i][j-k]), k=0,1,2..9。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n, dp[1005][10005], m = 1e9+7, ans;
int main() {
    cin >> n;
    dp[0][0] = 1;
    for (int j = 0; j <= 9; j++)
        dp[1][j] = 1;
    for (int i = 2; i <= n; i++)
    for (int j = 0; j <= 9*i; j++)
    for (int k = 0; k <= 9 && k <= j; k++) {
        dp[i][j] += dp[i-1][j-k];
        if (dp[i][j] >= m) dp[i][j] -= m;
    }
    for (int j = 0; j <= 9*n; j++)
        ans = (ans + (dp[n][j] - dp[n-1][j]) * dp[n][j]) % m;
    cout << ans << endl;
    return 0;
}