题意：给出一个数字num和m，问通过重新排列num中的各位数字中有多少个数(mod m)=0,直接枚举全排列肯定不行，可以用状压dp来搞..
dp[S][k]表示选了num中的S且(mod m)=k的方案种数,初始条件dp[0][0]=1,转移方为dp[i|1<<j[(10*k+num[j])%m]+=dp[i}[k];,注意到是多重排列，所以还需要除去重复的。代码如
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define maxn (1 << 18) + 5 #define LL long long LL m,f[maxn][105]; char ch[20]; bool vis[20]; int main() { scanf("%s%lld", &ch, &m); int n = strlen(ch); f[0][0] = 1; int e = (1 << n); for(int i = 0 ; i < e ; i ++) { for(int j = 0 ; j < m ; j ++) { memset(vis, 0, sizeof vis); for(int k = 0 ; k < n ; k ++) { int x = ch[k] - ‘0‘; if(i & (1 << k)) continue; if(i == 0 && x == 0) continue; if(vis[x]) continue; vis[x] = 1; f[i|(1<<k)][(j*10+x)%m] += f[i][j]; } } } cout<<f[e-1][0]<<endl; return 0; }
CodeForces-Round235D
原文：https://www.cnblogs.com/songorz/p/9387532.html
