BZOJ 1072: [SCOI2007]排列perm
正文索引 [隐藏]
Description
给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除（可以有前导0）。例如123434有90种排列能被2整除，其中末位为2的有30种，末位为4的有60种。
Input
输入第一行是一个整数T，表示测试数据的个数，以下每行一组s和d，中间用空格隔开。s保证只包含数字0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
Output
每个数据仅一行，表示能被d整除的排列的个数。
Sample Input
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
题解
这道题目状态压缩状态表示为f[i][j]，i表示10个数的使用状态，j表示除以d的余数，f[i][j]表示如此方案数。
P.S.一开始在想错了表示方法Orz、、、、、
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include<cstdio> #include<cstring> using namespace std; int T; int D; char s[15]; int d[10]; int cnt[10]; int ds; int f[3005][1005]; inline void solve(){ scanf("%s",&s); scanf("%d",&D); ds=0; while(ds<strlen(s)){d[ds]=s[ds]-'0';ds++;} memset(f,0,sizeof(f)); f[0][0]=1; for (int i=0;i<(1<<ds);i++){ for (int j=0;j<D;j++){ if (f[i][j]) for (int k=0;k<ds;k++){ if (!(i&(1<<k))){ f[i|(1<<k)][(j*10+d[k])%D]+=f[i][j]; } } } } int ans=f[(1<<ds)-1][0]; memset(cnt,0,sizeof(cnt)); for (int i=0;i<ds;i++) cnt[d[i]]++; for (int i=0;i<=9;i++) for (int j=2;j<=cnt[i];j++) ans/=j; printf("%d\n",ans); } int main(){ scanf("%d",&T); for (;T--;){ solve(); } return 0; } |
原文链接：BZOJ 1072: [SCOI2007]排列perm
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!