Codeforces 401D Roman and Numbers

矫情吗；* 2021-09-29 10:20 269阅读 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); }

转载于:https://www.cnblogs.com/ZeonfaiHo/p/7136382.html