AcWing 311 .月之谜

2021-03-17 17:26

阅读：732

标签：cstring res build name com ble problem namespace mem

大型补档补了一年

题目链接

考虑枚举月之数的数列和，然后展开dp预处理

设当前模数为 \(P\)
\(f[i][j][k]\) 表示一共有 i 位数字，数位和为 j，数值和 % P 的值为 K

\(f[1][i][i \% P]++\) 初始化（\(0 ）

枚举下一位数字 \(c\)
\(f[i + 1][j + c][(k + c * Pow[i]) % P] += f[i][j][k]\)

时间复杂度 \(O(N^2 * S * 10)\)

然后进行典型的数位 \(dp\)。
总复杂度上限是 \(O(N ^ 3 * S * 10)\) 大约是 \(5e7\) 的总量级，可以跑过~

#include 
#include 
#include 
using namespace std;
const int N = 83, S = 10;
int L, R, Pow[S] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
int f[S][N][N], d[N], n;
void build(int P) {
    memset(f, 0, sizeof f);
    f[0][0][0] = 1;
    for (int i = 0; i = 0) res += f[i - 1][P - t - j][mod(P - q - Pow[i - 1] * j, P)];
        t += d[i]; (q += d[i] * Pow[i - 1]) %= P;
        if (i == 1 && q == 0 && t == P) res++;
    }
    return res;
}

int main() {
    scanf("%d%d", &L, &R);
    int ans = 0;
    for (int i = 1; i

AcWing 311 .月之谜

标签：cstring res build name com ble problem namespace mem

原文地址：https://www.cnblogs.com/dmoransky/p/12380612.html

上一篇：NX二次开发-NXOPEN C#项目如何设断点调试代码

下一篇：AcWing 329. 围栏障碍训练场

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 311 .月之谜
文章链接：http://soscw.com/index.php/essay/65407.html

亲，登录后才可以留言！

AcWing 311 .月之谜

评论

热门文章

推荐文章

最新文章

置顶文章