Codeforces Round 235 D. Roman and Numbers

Problem - D - Codeforces

思路

这道题目要求重现排列n的数字让其模上m等于0且新得到的数没有前导零。

观察到数字最多只会有18位，所以我们又能想到状压。但是排列怎么状压呢？

其实排列就是组合在最后一位加入一个数。在知道了这一点了之后，我们就能将选择哪些位的数状态压缩，在转移时，我们将当前状态的数去掉一位并将该为数放在去掉一位的状态的末尾转移至当前状态。

这里我们还需要一个vis数组避免重复。

正解

#include<bits/stdc++.h> using namespace std; typedef long long LL; LL n; int m; int w[19], cnt; LL dp[1<<19][100]; bool vis[10]; int main() { cin>>n>>m; while(n) { w[cnt++] = n % 10; n /= 10; } dp[0][0] = 1; for(int S = 1; S < (1 << cnt); S ++) { memset(vis, false, sizeof vis); for(int k = 0; k < cnt; k ++) { if(S == (1 << k) && w[k] == 0) break; if(!(S & (1 << k)) || vis[w[k]]) continue; vis[w[k]] = true; for(int j = 0; j < m; j++) dp[S][(j * 10 + w[k]) % m] += dp[S ^ (1 << k)][j]; } } cout<<dp[(1 << cnt) - 1][0]; return 0; }