AtCoder Beginner Contest 336 E - Digit Sum Divisible

这篇具有很好参考价值的文章主要介绍了AtCoder Beginner Contest 336 E - Digit Sum Divisible。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

E - Digit Sum Divisible

atcoder contest 336,AtCoder,算法,c++,笔记,动态规划

题意

定义一个正整数 x x x g o o d good good 当且仅当: x x x 能被它的数位和 整除

统计小于等于 N N N g o o d good good 正整数数量

思路

这道题关键是要观察到在 N ≤ 1 0 14 N \leq 10^{14} N1014 的限制下,数位和种类是有限的:最多只有 9 × log ⁡ 10 1 0 14 = 9 × 14 = 126 9 \times \log_{10}10^{14} = 9 \times 14 = 126 9×log101014=9×14=126 种。那么我们可以枚举每一种数位和为 m o d mod mod,看看有多少正整数 x x x 可以被它整除,也就是 x x x % m o d = 0 mod = 0 mod=0

很明显这些涉及到数位统计并且还要计数的问题,我们可以使用 数位 D P DP DP 来计算。关键是怎么定义 D P DP DP 状态,还有高位如何利用低位的计算结果。

很显然,对于一个固定的数位和 m o d mod mod ,我们 D P DP DP状态限制有:
p o s (低 p o s 位是全变化位) pos(低pos位是全变化位) pos(低pos位是全变化位)
s u m (高位的已经确定的数位的和) sum(高位的已经确定的数位的和) sum(高位的已经确定的数位的和)
r (高位的已经确定的数位单独构成一个数字时模除 m o d 的余数) r(高位的已经确定的数位单独构成一个数字时模除 mod 的余数) r(高位的已经确定的数位单独构成一个数字时模除mod的余数)

例如: p o s = 2 , s u m = 6 , r = 3 , m o d = 20 pos = 2, sum = 6, r = 3, mod = 20 pos=2,sum=6,r=3,mod=20 时,代表的是 12 3 ′ 0 0 ′ → 12 3 ′ 9 9 ′ 123 '00' \rightarrow 123 '99' 1230012399 这些数字。因为这些数字的低 p o s = 2 pos = 2 pos=2 位是全变化位,也就是从 0 0 0 ~ 9 9 9 任意取的位;更高的位的数位和为 1 + 2 + 3 = 6 = s u m 1 + 2 + 3 = 6 = sum 1+2+3=6=sum;高位已经确定的位单独构成数字 123 123 123 时,模除 m o d = 20 mod = 20 mod=20 的余数是 r = 3 r = 3 r=3。(当然,这里只是举一个例子,在上述限制条件下,可能还有别的数字符合条件但没有列举出来)

有了限制条件,现在我们考虑如何转移
根据上述限制我们有定义: d p [ p o s ] [ s u m ] [ r ] dp[pos][sum][r] dp[pos][sum][r] 为限制条件下 g o o d good good 的正整数数量。如果 N N N 的长度为 l e n len len,那么我们当前的状态下: p l e n p l e n − 1 p l e n − 2 . . . p p o s + 1 p p o s p p o s − 1 . . . p 2 p 1 p_{len}p_{len-1}p_{len-2} ...p_{pos+1}p_{pos}p_{pos-1}...p_2p_1 plenplen1plen2...ppos+1pposppos1...p2p1,有:

  • s u m = p l e n + p l e n − 1 + . . . + p p o s + 1 sum = p_{len} + p_{len-1} + ... + p_{pos+1} sum=plen+plen1+...+ppos+1
  • r = ( 1 0 l e n − 1 ⋅ p l e n + 1 0 l e n − 2 ⋅ p l e n − 1 + . . . + 1 0 p o s ⋅ p p o s + 1 ) r = (10^{len-1} \cdot p_{len} + 10^{len-2} \cdot p_{len-1} + ... + 10^{pos} \cdot p_{pos+1}) r=(10len1plen+10len2plen1+...+10posppos+1) % m o d mod mod

那么如果我们枚举当前第 p o s pos pos 位为 i i i 的话,新的状态:
s u m ′ = s u m + i sum\prime= sum + i sum=sum+i
r ′ = ( 10 × r + i ) r\prime = (10 \times r + i) r=(10×r+i) % m o d mod mod

这里关键是观察到 r ′ r\prime r 的变化,通过前面更高位左移(整体 × 10 \times 10 ×10 )得到。

这样我们就完成了状态转移,记忆化搜索到最底层的时候,判断 s u m = m o d sum = mod sum=mod 并且 r = 0 r = 0 r=0 时才返回 1 1 1

时间复杂度:共有 D = 9 × 14 = 126 D = 9 \times 14 = 126 D=9×14=126 种数位和,范围 N N N 长度为 l e n len len ,每种数位和要搜索的范围可以通过 D P DP DP 数组得出,大约为 l e n × D × m o d len \times D \times mod len×D×mod
故最终复杂度 O ( D 3 ⋅ l e n ) O(D^3 \cdot len) O(D3len)文章来源地址https://www.toymoban.com/news/detail-824349.html

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;

const int INF=0x3f3f3f3e;
const long long INFLL=1e18;

typedef long long ll;

ll dp[17][150][150]; //dp[pos][sum][r] 表示低pos位为全变化位,前面高位已经确定的数位和为sum,高位模mod为r的数量
int num[17];
int mod;

ll dfs(int pos, int sum, int r, bool limit){
    if(!pos) return !r && sum == mod; //最底层,这时候数位和一定要是mod,并且sum % mod 要为 0
    if(!limit && ~dp[pos][sum][r]) return dp[pos][sum][r];
    ll res = 0;
    int up = (limit ? num[pos] : 9);
    fore(i, 0, up + 1){
        res += dfs(pos - 1, sum + i, (r * 10 + i) % mod, limit && i == up);
    }
    if(!limit) dp[pos][sum][r] = res;
    return res;
}

ll solve(ll x){
    int len = 0;
    while(x){
        num[++len] = x % 10;
        x /= 10;
    }
    ll ans = 0;
    for(mod = 1; mod < 130; ++mod){ // 枚举整个数位和
        memset(dp, -1, sizeof(dp));
        ans += dfs(len, 0, 0, true);
    }
    return ans;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    ll n;
    std::cin >> n;
    std::cout<< solve(n);
    return 0;
}

到了这里,关于AtCoder Beginner Contest 336 E - Digit Sum Divisible的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • AtCoder Beginner Contest 310

    感觉F又双叒叕写复杂了 点杯咖啡,要 (p) 元,但可以用一个优惠券,使得咖啡只要 (q) 元,但你需要额外购买 (n) 个商品中(价格为 (a_i) )的一个。 问点杯咖啡的最小价格。 考虑直接买还是使用优惠券,使用优惠券的话就选 (n) 个商品中价格最小的。 两种情况取最小

    2024年02月16日
    浏览(28)
  • AtCoder Beginner Contest 320

    给定 (a,b) ,输出 (a^b + b^a) 。 因为数不超过 (10) ,可以直接用 pow 计算然后转成 (int) 。不会有精度损失。 神奇的代码 给定一个字符串 (s) ,求长度最长的回文串。 因为长度只有 (100) ,可以直接枚举子串,然后暴力判断是不是回文串(翻转后是否和自身相同),复杂

    2024年02月08日
    浏览(38)
  • AtCoder Beginner Contest 348

    给定 (n) ,输出 (ooxooxoox...) ,长度为 (n) 。 按题意模拟即可。 神奇的代码 给定 (n) 个点,对每个点,求出与其距离最远的点的下标。 (n) 只有 (100) ,对于每个点,花 (O(n)) 遍历每个点最大化距离,时间复杂度为 (O(n^2)) 。 神奇的代码 (n) 个豌豆,每个豌豆有美味值

    2024年04月08日
    浏览(42)
  • AtCoder Beginner Contest 314

    怎么好多陌生单词 审核怎么这么逆天,半小时还没审完 给定 (pi) 的值以及数 (n) ,要求保留 (n) 位小数输出,不四舍五入。 字符串形式储存然后截取末尾即可。 神奇的代码 (n) 个人玩轮盘赌游戏,简单说就是一个转盘有 (37) 个数字以及一个箭头,箭头会等概率停在某

    2024年02月13日
    浏览(40)
  • AtCoder Beginner Contest 335

    给定一个字符串,将最后一位改成 4 。 模拟即可。 神奇的代码 给定 (n) ,按字典序输出非负整数 (i,j,k) ,使得 (i+j+kleq n) (n) 只有 (21) ,直接 (O(n^3)) 枚举判断即可。 神奇的代码 二维网格,贪吃蛇,移动,进行 (q) 次操作,分两种 指定贪吃蛇下一步移动的方向 指定

    2024年01月19日
    浏览(32)
  • AtCoder Beginner Contest 322

    给定一个字符串,找到最先出现 ABC 的位置。 直接查找判断即可。 神奇的代码 给定字符串 s 和 t ,问 s 是不是 t 的前缀和后缀。 根据前后缀定义判断即可。这里试了下 python 神奇的代码 (n) 天,有 (m) 天会放烟花。 问每一天,距离未来最近的放烟花的天数。 两个双指针一

    2024年02月08日
    浏览(33)
  • AtCoder Beginner Contest 301

    给定一个字符串表示高桥和青木每局的获胜情况。 如果高桥获胜局数多,或者两个胜局相等,但高桥率先取得那么多胜场,则高桥获胜,否则青木获胜。 问谁获胜。 按照题意,统计两者的获胜局数比较即可。 如果两者局数相等,可以看最后一局谁胜,青木胜则意味着高桥率

    2024年02月04日
    浏览(55)
  • AtCoder Beginner Contest 303

    给定两个字符串,问这两个字符串是否相似。 两个字符串相似,需要每个字母,要么完全相同,要么一个是 1 一个是 l ,要么一个是 0 一个是 o 按照题意模拟即可。 可以将全部 1 换成 l ,全部 0 换成 o ,再判断相等。 神奇的代码 给定 m 个 n 的排列,问有多少对 ((i, j),i j

    2024年02月07日
    浏览(35)
  • AtCoder Beginner Contest 330

    给定 (n) 个学生的分数,以及及格分 (x) ,问多少人及格了。 依次判断即可。 神奇的代码 回答 (n) 个问题,每个问题给定 (a,l,r) ,问函数 (f(x) = |x - a|) 在 ([l,r]) 的最小值。 全定义域下,最小值显然在 (x=a) 取得。绝对值函数图像是 (V) 型。 现在限定在 ([l,r]) ,则

    2024年02月05日
    浏览(116)
  • AtCoder Beginner Contest 318

    咕咕咕,总力战还没打,凹不过卷狗,躺了.jpg 给定 (n, m, p) ,问有多少个 (i) 满足 (0 m+pi leq n) 减去初始的 (m) ,剩下的就是看 (p) 的倍数个数。 神奇的代码 一个二维空间,有 (n) 个矩形覆盖。 问有多大的空间被覆盖了。重复覆盖算一次。 空间大小只有 (100) ,矩形

    2024年02月10日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包