Kattis Terraced fields （数位DP）

spirit

2021 年 06 月 12 日

1649 次浏览

暂无评论

1767字数

VJ训练赛数位DP

# Kattis Terraced fields （数位DP）

[题目链接](https://vjudge.net/problem/Kattis-terracedfields)

## 题意

给一个数字 $n$ ，要求统计所有满足  $ i \% 8 = 0$ 或 $i = n$ （$1 \leq i \leq n$ ）的数字中 $6$ 和 $8$ 出现的次数，比如 $666888$ 中 $6$ 出现了 $3$ 次， $8$ 出现了 $3$ 次，对总次数的贡献为 $6$ 。

**input** 共 $t$ 组，每组一个 $n$ （ $1 \leq n \leq 1e18$ ）。

```
4
9
32
56
18
```

**output** 如题目描述

```
1
2
4
3
```

## 思路

看题面很容易想到数位DP，但是满足条件的数字是 $8 \quad 16 \quad 24 ...$ 这样不连续的区间，因此需要转化。可以发现 $1000$ 是被 $8$ 整除的，所有 $1000$ 的倍数显然也被 $8$ 整除，可以将要求的数字分为以下三部分：

1. $ n - n \%1000 \leq i \leq n$ ，这部分的数字不超过 $1000$ 个，暴力即可。
2. $i < n - n \% 1000$ 中，所有数字的后三位上出现的 $6$ 和 $8$ 。我们把后三位以外的部分记为 $m$ ，由于只要 $i$ 的后三位被 $8$ 整除，$i$ 就被 $8$ 整除，在 $m$ 取一个定值的时候，后三位上的 $6$ 和 $8$ 对答案的贡献和 $[1, 999]$ 这部分数字对答案的贡献是相同的。暴力统计小于 $1000$ 的数字对答案的贡献，然后乘 $m$ 有多少种取值情况就可以了（其实就是 $[0, n / 1000]$ 这 $n / 1000$ 种） 。
3. $i < n - n\%1000$ 中，后三位以外的部分出现的 $6$ 和 $8$ ，因为数字 $i$ 能否被 $8$ 整除只和它的后三位有关，因此我们只需要先求出 $m$ 的取值区间 $[0, n / 1000 - 1]$ （这里是因为 $m = n / 1000$ 在第一种被统计过了）中 $6$ 和 $8$ 出现的次数，再乘上后三位中能被 $8$ 整除的数字的数量（即 $125$）就可以了，这一步需要用数位DP统计。

## 代码

```cpp
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 25, INF = 0x3f3f3f3f;
LL dp[N], power[N], suc[N];
int d[N], cnt;
//暴力统计数字n中的6和8
int get(LL n) {
    int num = 0;
    while (n) {
        if (n % 10 == 6 || n % 10 == 8) num++;
        n /= 10;
    }
    return num;
}
//预处理后缀取值情况
void init_suc(int m) {
    suc[0] = d[0];
    for (int i = 1; i < m; i++) 
        suc[i] = d[i] * power[i] + suc[i - 1];
}
LL dfs(int u, bool limit) {
    if (u < 0) return 0;
    //如果不是临界情况且已经求过，直接返回
    if (!limit && dp[u] != -1) return dp[u];
    LL res = 0;
    //当前一位最多能枚举到多少
    int ma = limit ? d[u] : 9;
    //枚举当前位
    for (int i = 0; i <= ma; i++) {
        //这一位之后的数量
        res += dfs(u - 1, limit && i == d[u]);
        if (i == 6 || i == 8) {
            //如果当前位之后的取值是受限制的，求一下后面有多少种取值可能
            if (limit && i == ma) res += suc[u - 1] + 1;
            //不受限制后面取值就是10的幂次
            else res += power[u];
        }
    }
    //记忆化
    if (!limit) dp[u] = res;
    return res;
}
LL solve(LL n) {
    //将数位DP的限制数字每一位拆开
    cnt = 0;
    while (n) {
        d[cnt++] = n % 10;
        n /= 10;
    }
    //预处理后缀取值情况
    init_suc(cnt);
    return dfs(cnt - 1, true);
}
int main() {
    memset(dp, -1, sizeof dp);
    int t, num = 0;
    //预处理[1,999]的6和8个数
    for (int i = 1; i <= 999; i++)
        if (i % 8 == 0) num += get(i);
    //预处理10的幂
    power[0] = 1;
    for (int i = 1; i <= 18; i++) power[i] = power[i - 1] * 10;
    LL n, res;
    cin >> t;
    while (t --) {
        scanf("%lld", &n);
        //第二部分
        res = n / 1000 * num;
        //第一部分
        for (LL i = n - n % 1000; i <= n; i++) 
            if (i % 8 == 0 || i == n) res += get(i);
        //第三部分
        res += 125 * solve(n / 1000 - 1);
        printf("%lld\n", res);
    }
    return 0;
}
```

最后修改：2021 年 06 月 15 日