Codeforces Round 235 D. Roman and Numbers

Problem - D - Codeforces思路这道题目要求重现排列n的数字让其模上m等于0且新得到的数没有前导零。观察到数字最多只会有18位所以我们又能想到状压。但是排列怎么状压呢其实排列就是组合在最后一位加入一个数。在知道了这一点了之后我们就能将选择哪些位的数状态压缩在转移时我们将当前状态的数去掉一位并将该为数放在去掉一位的状态的末尾转移至当前状态。这里我们还需要一个vis数组避免重复。正解#includebits/stdc.h using namespace std; typedef long long LL; LL n; int m; int w[19], cnt; LL dp[119][100]; bool vis[10]; int main() { cinnm; 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]; } } coutdp[(1 cnt) - 1][0]; return 0; }