2408. [SCOI2007]排列
★★ 输入文件：wulipailie.in 输出文件：
wulipailie.out
简单对比
时间限制：1 s 内存限制：256 MB
【题目描述】
给一个数字串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.
输出：
每个数据仅一行，表示能被d整除的排列的个数。
【样例输入】
7
000
1
001
1
1234567890
1
123434
2
1234
7
12345
17
12345678
29
【样例输出】
1
3
3628800
90
3
6
1398
【提示】
数据范围：
20%的数据满足：s的长度不超过5, 1<=T<=5
50%的数据满足：s的长度不超过8
100%的数据满足：s的长度不超过10, 1<=d<=1000, 1<=T<=15
暴力
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#define V 10500
#define INF 1115006
#define S 1<<10+1
typedef long long LL;
using namespace std;
char s[15];
int mod,g[15];
int t;
LL ans;
int len;
LL getn()
{LL o=1,u=0;for(int i=len-1;i>=0;i--){u+=o*(s[i]-'0');o*=10; } return u;}
int main()
{//freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);freopen("wulipailie.in","r",stdin);freopen("wulipailie.out","w",stdout);scanf("%d",&t);int p;while(t--){ans=0;cin>>s;cin>>mod;len=strlen(s);sort(s,s+len);int js=0;do{LL num=getn();if(num%mod==0)ans++; }while(next_permutation(s+0,s+len));cout<<ans<<endl;}return 0;
}
正解：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#define V 10500
#define INF 1115006
#define S 1<<10+1
typedef long long LL;
using namespace std;
char s[15];
int mod,g[15],ss[15];
int t;
LL f[2050][1005];
LL ans;
int main()
{//freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);freopen("wulipailie.in","r",stdin);freopen("wulipailie.out","w",stdout);scanf("%d",&t);int p;while(t--){memset(f,0,sizeof(f));memset(ss,0,sizeof(ss));scanf("%s%d",s,&mod);//cout<<s<<endl;p=strlen(s);for(int i=0;i<p;i++){g[i]=s[i]-'0';ss[g[i]]++; } f[0][0]=1;for(int i=0;i<(1<<p);i++) for(int j=0;j<mod;j++)for(int k=0;k<p;k++)if(!(i&(1<<k)))f[i|(1<<k)][(j*10+g[k])%mod]+=f[i][j];ans=f[(1<<p)-1][0];for(int i=0;i<=9;i++)for(int j=2;j<=ss[i];j++)ans/=j;cout<<ans<<endl; }return 0;
}