Description
给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除（可以有前导0）。例如123434有90种排列能被2整除，其中末位为2的有30种，末位为4的有60种。
输入第一行是一个整数T，表示测试数据的个数，以下每行一组s和d，中间用空格隔开。s保证只包含数字0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
Output
每个数据仅一行，表示能被d整除的排列的个数。
7 000 1 001 1 1234567890 1 123434 2 1234 7 12345 17 12345678 29
Sample Output
1 3 3628800 90 3 6 1398
HINT
在前三个例子中，排列分别有1, 3, 3628800种，它们都是1的倍数。 【限制】100%的数据满足：s的长度不超过10, 1<=d<=1000,1<=T<=15
题解
一、状压DP
f[i][j] 表示达到这个状态的方案数。其中i 的二进制表示当前已经使用了原数串中的某些位 (在 i 中为 1 的位) ，j 表示当前的数字 mod d 的值。
那么状态转移就是 : f[i || (1 << k)][(j*10+a[k])%d] += f[i][j]——-(i & (1 << k))==0
由于原排列中的数字可能有重复的，所以我们计算了很多重复的方案数。
如果某个数字 i 在排列中出现了 cnt[i] 次，那么最后的答案 ans 应该 ans /= (cnt[i])! （排列数）。
代码
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int t,d,l,ans;int a[15],cnt[15],f[1024+5][1010];char str[15];int main(){ scanf("%d",&t); while(t--) { scanf("%s%d",str,&d); l = strlen(str); memset(cnt,0,sizeof(cnt)); for(int i = 0;i < l;i++) { a[i] = str[i] - '0'; ++cnt[a[i]]; } memset(f,0,sizeof(f)); f[0][0] = 1; for(int i = 0;i < (1 << l);i++) for(int j = 0;j < d;j++) for(int k = 0;k < l;k++) if((i & (1 << k)) == 0) f[i|(1 << k)][(j*10+a[k])%d] += f[i][j]; ans = f[(1 << l) - 1][0]; for(int i = 0;i <= 9;i++) for(int j = 1;j <= cnt[i];j++) ans /= j; PRintf("%d/n",ans); } return 0;}二、C++的STL
听说STL中的 next_permutation就可以AC，虽然很慢。
代码
#include<cstdio>#include<cstring>#include<algorithm>#include<set>#include<cmath>#include<cstdlib>using namespace std;typedef long long ll;int t,d,l,ans;int a[15];char str[15];set<ll> s;int main(){ scanf("%d",&t); while(t--) { scanf("%s%d",str,&d); ans = 0; s.clear(); l = strlen(str); for(int i = 0;i < l;i++) a[i] = str[i] - '0'; sort(a,a+l); while(true) { ll num = 0; for(int j = 0;j < l;j++) num = num * 10 + a[j]; if(s.count(num) == 0 && num % d == 0) { ++ans; s.insert(num); } if(!next_permutation(a,a+l)) break; } printf("%d/n",ans); } return 0;}
