AcWing 311 .月之谜
2021-03-17 17:26
阅读：874
标签：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
评论
亲，登录后才可以留言！