题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=25887
题目大意：给定的一个某进制下的排列，问它的全排列有多少个能够整除给定的十进制下的数字k。
思路：记忆化搜索，dp[state][r]表示在某状态下被k除余数为r有多少个。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 #define FILL(a,b) memset(a,b,sizeof(a)) 8 typedef long long ll; 9 10 int base,k,len,num[17]; 11 ll dp[1<<17][21]; 12 char str[21]; 13 14 ll dfs(int state,int mod) 15 { 16 if(state==(1<<len)-1){ 17 return mod==0; 18 } 19 if(dp[state][mod]!=-1)return dp[state][mod]; 20 ll ans=0; 21 for(int i=len-1;i>=0;i--){ 22 if(!(state&(1<<i))){ 23 ans+=dfs(state|(1<<i),(mod*base+num[i])%k); 24 } 25 } 26 return dp[state][mod]=ans; 27 } 28 29 int main() 30 { 31 int _case,t=1; 32 scanf("%d",&_case); 33 while(_case--){ 34 scanf("%d%d",&base,&k); 35 scanf("%s",str); 36 len=strlen(str); 37 for(int i=0;i<len;i++){ 38 if(str[i]>='0'&&str[i]<='9')num[i]=str[i]-'0'; 39 else num[i]=str[i]-'A'+10; 40 } 41 FILL(dp,-1); 42 printf("Case %d: %lld ",t++,dfs(0,0)); 43 } 44 return 0; 45 }