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; 二、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;}
