Codeforces 401D Roman and Numbers-蒲公英云

Codeforces 401D Roman and Numbers

矫情吗；* 2021-09-29 10:20 349阅读 0赞

题目大意

Description

给定一个数 N(N<1018) , 求有多少个经过 N 重组的数是 M(M≤100) 的倍数.
注意: ①重组不能有前导零;　②重组的数相同, 则只能算一个数.

Input

第一行两个数 N , M .

Output

输出满足要求的数的个数.

Sample Input

223 4

Sample Output

题解

状压DP.
\(f[i][j]\)中, \(i\)是状态, 表示原数中哪些位已经被新数占用. 因此, 一个Naive的想法就是对于新数的每一位, 进行一次DP, 时间复杂度: \(2^{18} \times 18 \times 18\), 显然会TLE.
我们注意到, 每当我们进行一次转移, 也就是在新数中填入一位的时候, 状态\(i\)都只会变小, 因此我们从\(2^{18} - 1\)往下直接进行一次DP即可. 时间复杂度: \(2^{18} * 18\), 尚可接受.

#include <cstdio> #include <cstring> const int LEN = 18, M = 100; int main() { #ifndef ONLINE_JUDGE freopen("CF401D.in", "r", stdin); #endif static long long pw[LEN]; pw[0] = 1; for(int i = 1; i < LEN; ++ i) pw[i] = pw[i - 1] * 10; long long n, m; scanf("%lld%lld\n", &n, &m); int len = 0; long long tmp = n; static int cnt[10]; for(; tmp; tmp /= 10, ++ len) ++ cnt[tmp % 10]; static long long fac[10]; for(int i = 0; i < 10; ++ i) { fac[i] = 1; for(int j = 1; j <= cnt[i]; ++ j) fac[i] *= j; } static long long f[1 << LEN][M]; memset(f, 0, sizeof(f)); f[(1 << len) - 1][0] = 1; /* for(int l = len - 1; ~ l; -- l) for(long long i = 0; i < 1 << len; ++ i) for(int j = 0; j < m; ++ j) if(f[i][j]) { for(int k = 0; k < len; ++ k) { if(n / pw[k] % 10 == 0 && l == len - 1) continue; if(i >> k & 1) f[i ^ (1 << k)][(j + n / pw[k] % 10 * pw[l]) % m] += f[i][j]; } f[i][j] = 0; } */ for(int i = (1 << len) - 1; ~ i; -- i) for(int j = 0; j < len; ++ j) if(i >> j & 1 && (i ^ (1 << len) - 1 || n / pw[j] % 10 % 10)) for(int k = 0; k < m; ++ k) f[i ^ (1 << j)][(k * 10 + n / pw[j] % 10) % m] += f[i][k]; long long ans = f[0][0]; for(int i = 0; i < 10; ++ i) ans /= fac[i]; printf("%lld\n", ans); }