AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 问答
    • 吐槽
  • App
  • 登录/注册

AcWing 311. 月之谜

作者: 作者的头像   炽热的 ,  2023-03-16 19:31:47 ,  所有人可见 ,  阅读 30


1


#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int len;
int nums[20], f[20][100][100];

int dfs(int pos, int mod, int val, int p, int limit) {
    if (val < 0) return 0;
    if (!pos) return !mod && !val;
    if (!limit && ~f[pos][mod][val]) return f[pos][mod][val];
    int up = limit ? nums[pos] : 9, res = 0;
    for (int i = 0; i <= up; i ++ ) 
        res += dfs(pos - 1, (mod * 10 + i) % p, val - i, p, limit && i == up);
    return limit ? res : f[pos][mod][val] = res;
}

int calc(int x, int p) {
    len = 0;
    memset(f, -1, sizeof f);
    while (x) nums[ ++ len] = x % 10, x /= 10;
    return dfs(len, 0, p, p, 1);
}

int main() {
    int l, r; cin >> l >> r;
    int res = 0;
    for (int i = 1; i <= 81; i ++ ) 
        res += calc(r, i) - calc(l - 1, i);
    cout << res;
    return 0;
}

0 评论

你确定删除吗?

© 2018-2023 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息