题目链接：点击打开链接
题意：给你一个数n，要求将n的各个位上的数重新排列（不能有前导0），使得形成的数对m取模为0， 问有多少个这种数。
思路：因为n太大了，枚举全排列复杂度高达n！。 因为n最大有18位， 所以可以用状态压缩每一位，表示当前的答案中选了哪些数了。
那么不难想到状态d[i][j]表示当前已经把哪些位上的数用了（用集合i表示），且此时余数为j的答案数。 这样递推到所有数都用了，并且余数为0，就是答案。
细心的读者已经发现了， 这其实就已经暗含着顺序问题了。 另外需要注意，由于各个位上的数字可以重复，所以为了避免重复的情况出现（例如1231，两个1交换的情况），用一个数组去重。
细节参见代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 100;
int cnt,digt[30],vis[(1<<18)+10][105],kase=7;
ll n,m,d[(1<<18)+10][105];
ll dp(int S, int mod) {
ll& ans = d[S][mod];
if(S == (1<<cnt)-1) {
if(mod == 0) return 1;
else return 0;
}
if(vis[S][mod] == kase) return ans;
vis[S][mod] = kase;
ans = 0;
bool flage[11] = {0};
for(int i=0;i<cnt;i++) {
if(flage[digt[i]]) continue;
if(S & (1<<i)) continue;
if(S == 0 && digt[i] == 0) continue;
ans += dp(S | (1<<i),(mod * 10 + digt[i]) % m);
flage[digt[i]] = true;
}
return ans;
}
int main() {
scanf("%I64d%I64d",&n,&m);
ll cur = n;
cnt = 0;
while(cur > 0) {
digt[cnt++] = cur % 10;
cur /= 10;
}
printf("%I64d\n",dp(0, 0));
return 0;
}
Codeforces Round #235 (Div. 2) D. Roman and Numbers（状态压缩DP）
原文：http://blog.csdn.net/weizhuwyzc000/article/details/50583595