记录编号	406912	评测结果	AAAAA
题目名称	[SCOI 2007]排列	最终得分	100
用户昵称	Gilgamesh	是否通过	通过
代码语言	C++	运行时间	0.173 s
提交时间	2017-05-20 09:54:02	内存使用	15.55 MiB

#include<cstdio>
#include<string>
#include<cstring>
//#include<iostream>
#include<algorithm>
using namespace std;
inline int read()
{
   int s=0;
   int f=1;
   char ch=getchar();
   while(ch<'0'||ch>'9')
    {
       if(ch=='-')
        f=-1;
       ch=getchar();                    
    }       
   while(ch>='0'&&ch<='9')
    {
       s=s*10+ch-'0';
       ch=getchar();                      
    }
   return s*f;
}
int tot[110];
int num[110];
int cnt[110];
int dp[2000][2000];
inline void init()
{
     memset(num,0,sizeof(num));
     memset(dp,0,sizeof(dp));
     memset(cnt,0,sizeof(cnt));
     memset(tot,0,sizeof(tot));
     dp[0][0]=1;
     for(int i=0;i<=10;i++)
      cnt[i]=1;      
}
inline int work()
{
       freopen("wulipailie.in","r",stdin);
       freopen("wulipailie.out","w",stdout);
       int T=read();
       while(T--)
        {
           init();
           char s[20]; 
           scanf("%s",s);
           int d=read();
           int n=strlen(s);
//for(int i=0;i<n;i++)
//cout<<s[i];while(1);
//cout<<n;while(1);
//for(int i=1;i<=n;i++)
             
//for(int i=1;i<=n;i++)
// cout<<num[i];
//memset(cnt,1,sizeof(cnt));
//cout<<cnt[1];while(1);
           for(int i=1;i<=n;i++)
            {
               num[i]=s[i-1]-'0';
               tot[num[i]]++;
               cnt[num[i]]*=tot[num[i]];
            } 
//for(int i=1;i<=n;i++)
// cout<<num[i];
//while(1);
           for(int i=0;i<(1<<n)-1;i++)
		    for(int j=0;j<d;j++)
			 if(dp[i][j])
              for(int k=1;k<=n;k++)
               if(((1<<(k-1))&i)==0)
			    dp[i|(1<<(k-1))][(num[k]+j*10)%d]+=dp[i][j];
/*
for(int i=0;i<=(1<<n)-1;i++)	
for(int j=0;j<d;j++)
if(dp[i][j])
for(int k=1;k<=n;k++)
if(((1<<(j-1))&i)==0)
 dp[i|(1<<(k-1))][(num[k]+j*10)%d]+=dp[i][j];
*/
           for(int i=0;i<=9;i++)
            dp[(1<<n)-1][0]/=cnt[i]; 
//printf("ANS:::::");
           printf("%d\n",dp[(1<<n)-1][0]);
//for(int i=1;i<=n;i++)
//cout<<cnt[i]<<endl;
//while(1);
        }
       //while(1);
}
int QAQ=work();
int main(void){;}
/*
7
000
1
001
1
1234567890
1
123434
2
1234
7
12345
17
12345678
29
*/

/*ans
1
3
3628800
90
3
6
1398
*/