【AT4540】Dight Sum

$\rm{Description}$

求区间 $[1, k]$ 中有多少个整数满足:其十进制表示的数字和为 $D$ 的倍数。答案对 $1e9+7$ 取模。

$\rm{Solution}$

观察数据范围:$1\leq k\leq 10^{10000}$.

再看题面,形如”求在数位限制下有多少满足条件的数“,想到数位 $\rm{DP}$.

如果你没有学过数位 $\rm{DP}$,那么可以参考这篇博客,我就是照着这篇博客学懂的。

如果你学过数位 $\rm{DP}$,那么现在考虑状态如何设置。

状态设置:

首先可以看出,这道题不需要前导零标记。

第二步需要思考 $\rm{DP}$ 中需要存储什么前缀状态。通过题目描述可以比较容易的看出,我们只需要存储前缀数字和对 $D$ 取模的余数即可,将其记为 $\rm{pre}$,

那么能对答案作出贡献的条件就是:前缀数字和 $\bmod D =0$,也就是 $pre = 0$.

至此,根据数位 $\rm{DP}$ 的套路,我们可以设置如下状态:

$\rm{DP}[pos][pre][sta]$ 表示还有 $pos$ 位需要处理;

当前状态的前缀数字和 $\bmod D$ 是 $pre$;

前缀的最大值状态是 $sta$,若前 $len-pos$ 位与题目给出的 $k$ 相同,则 $sta=0$,反之亦然。

状态转移:

于是可以使用记忆化搜索来实现数位 $\rm{DP}$,详见代码注释。

个人觉得注释还比较清晰,认真多看几遍是能看懂的。

int dfs(int pos, int res, int sta) {
	if(pos == 0) return res == 0; //能对答案作出贡献的条件:前缀数字和 mod D == 0
	if(dp[pos][res][sta] != -1) return dp[pos][res][sta]; //记忆化搜索
	int ret = 0, maxx = 9; //ret是函数返回值,maxx是当前位可选的最大值
    if(sta) maxx = num[pos]; //如果当前前缀与k的前缀相同,那么这一位最大值就是num[pos]
	for(int i = 0; i <= maxx; i++) { //之后遍历这一位可选的数字
		ret += dfs(pos - 1, (res + i) % d, sta && (i == maxx));
        //pos - 1: 继续看下一位
        //(res + i) % d: 把前缀数字和加上新选的这一位
        //sta && (i == maxx): 前缀and当前这一位, 都与k的前缀相同,那么新的前缀还是最大值状态 
	}
	dp[pos][res][sta] = ret;//记忆化
	return ret;
}

由于加上取模之后不美观,上面的代码没有给 $ret$ 加取模,需要加上。(下面的代码中是有取模的)

$\rm{Code}$

放出完整代码,可以再重点看一下 solve() 函数里面的初始化。

关键部分的注释已经在上面了。

如果没有看懂,建议再读几遍这篇博客,或者自行百度学习数位 $\rm{DP}$.

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXLEN = 10008;
const int MAXD = 108;
const int mod = 1e9 + 7;
int d, num[MAXLEN];
string s;
int dp[MAXLEN][MAXD][2];
int dfs(int pos, int res, int sta) {
	if(pos == 0) return (res == 0);
	if(dp[pos][res][sta] != -1) return dp[pos][res][sta];
	int ret = 0, maxx = 9;
	if(sta) maxx = num[pos];
	for(int i = 0; i <= maxx; i++) {
		ret = (ret + dfs(pos - 1, (res + i) % d, sta && (i == maxx))) % mod;
	}
	dp[pos][res][sta] = ret;
	return ret;
}
int solve() {
	memset(dp, -1, sizeof(dp));
	for(int i = 0; i < s.length(); i++) {
		num[i + 1] = s[s.length() - i - 1] - '0';
	}
	return dfs(s.length(), 0, 1);
}
signed main() {
	cin >> s;
	scanf("%lld", &d);
	printf("%lld\n", ((solve() - 1) % mod + mod) % mod);
	return 0;
}
内容原创,转载请著名本文URL:https://www.tonyyin.top/2020/12/at4540/
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇