题解 AT4540 【Digit Sum】

Doqin07 · 2020-12-08 16:26:57 · 题解

题意

求 {1,2,3,...,k}中有多少数字的各位之和是d的倍数。

解题思路

我们有一个很显然的暴力，枚举1-k中每一个数，计算数位之和，判断是否能被d整除。代码也很好写。但是k<=10^10000,会tle。

那么接一下来，分析题目，“数字之和”此类的字眼，不免让人想到数位dp。

这类题目的基本框架就是求某一个范围[l, r]内有多少个数满足XXX性质。由于[l, r]=[0, r]−[0, l−1]，我们通常转化为只有上界，而下界为0的两个独立情况分别计算。于是以下只考虑[0, r]的计算方法。

数位dp：

这题我们运用01背包的思想：在考虑第i件物品的时候，只关心之前选择的总重量以及总价值，而不需要知道具体的方案是什么——即合并等价状态。

回到本题，我们枚举第 i 位的时候，只有这些信息是重要的：

• 1.之前的数位和。
• 2.是否已经小于上界r，如果是的话，那么可以枚举[0-9]，否则只可以枚举到r[i]——因为我们只考虑小于等于r的数。

那么我们可以设dp[i][j][k=0/1]表示在考虑第i位之前的数位和(模d)等于j，以及是否已经小于上界的方案数。转移也很简单，对于状态dp[i][j][k]，只需要枚举第i位的值x[i]，那么转移到的状态为dp[i+1][(j+x[i])%d][k or x[i]<r[i]]。最后一个值的意思是，小于上界的条件是之前已经小于上界或者当前位小于上界对应位。

思路已经很清楚了，接下来看一下核心Code:

dp[0][0][0] = 1;
for (int i = 0; i < n; ++i){
    for (int j = 0; j < d; ++j){
        for (int k = 0; k < 2; ++k){
            for (int cur = 0; cur <= 9; ++cur){
                if (k == 0 and cur > r[i])
                    break;
                dp[i + 1][(j + cur) % d][k or cur < r[i]] += dp[i][j][k];
            }
        }
    }
}
//小于上界+不小于上界（即等于上界）- 0的情况（因为题目里不包含0
ans = dp[n][0][0] + dp[n][0][1] - 1; 

求过啊^_^