「BZOJ1072」[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
000 1
001 1
1234567890 1
123434 2
1234 7
12345 17
12345678 29
Sample Output
1
3
3628800
90
3
6
1398
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余数j的方案。。
然后用排列组合去重就好
|
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 43 44 45 46 47 48 49 50 51 52 53 54 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #define inf 1000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int bin[20]; int T,d,len; int a[15],v[15],tot[15],f[1025][1005]; char ch[15]; void dp() { for(int i=0;i<bin[len];i++) for(int k=0;k<d;k++) f[i][k]=0; f[0][0]=1; for(int i=0;i<bin[len];i++) for(int k=0;k<d;k++) if(f[i][k]) for(int x=1;x<=len;x++) if((bin[x-1]&i)==0) f[i|bin[x-1]][(a[x]+k*10)%d]+=f[i][k]; } int main() { bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1; T=read(); while(T--) { scanf("%s",ch+1);d=read(); len=strlen(ch+1); for(int i=0;i<=9;i++)v[i]=1,tot[i]=0; for(int i=1;i<=len;i++) { a[i]=ch[i]-'0'; tot[a[i]]++; v[a[i]]*=tot[a[i]]; } dp(); for(int i=0;i<=9;i++)f[bin[len]-1][0]/=v[i]; printf("%d\n",f[bin[len]-1][0]); } return 0; } |
Subscribe
计数器 9792969
OI 课件=>
OI 课件=>