1021 - Painful Bases PDF (English) Statistics ForumTime Limit: 2 second(s) Memory Limit: 32 MBAs you know that sometimes base conversion is a painful task. But still there are interesting facts in bases.
For convenience let's assume that we are dealing with the bases from 2 to 16. The valid symbols are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E and F. And you can assume that all the numbers given in this problem are valid. For example 67AB is not a valid number of base 11, since the allowed digits for base 11 are 0 to A.
Now in this problem you are given a base, an integer K and a valid number in the base which contains distinct digits. You have to find the number of permutations of the given number which are divisible by K. K is given in decimal.
For this problem, you can assume that numbers with leading zeroes are allowed. So, 096 is a valid integer.
InputInput starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a blank line. After that there will be two integers, base (2 ≤ base ≤ 16) and K (1 ≤ K ≤ 20). The next line contains a valid integer in that base which contains distinct digits, that means in that number no digit occurs more than once.
OutputFor each case, print the case number and the desired result.
Sample InputOutput for Sample Input32 21010 2568116 1ABCDEF0123456789Case 1: 1Case 2: 12Case 3: 20922789888000
解题思路: 状压dp+数位dp
dp[i][j] , i 的二进制上为1的表示这个把对应位置的数取了，这种方法相对于暴力全排列来说，他可以同时取多个数，所以可以节省很多时间。
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; ll dp[1<<17][25]; int main(){ int T,n,limit,k,len,num[20]; char str[20]; scanf("%d",&T); for(int t=1;t<=T;t++){ memset(dp,0,sizeof(dp)); scanf("%d%d",&n,&k); scanf("%s",str); len = strlen(str); for(int i=0;i<len;i++){ // 转化成正常数字 if(str[i]<='9'&&str[i]>='0') num[i] = str[i] - '0'; else num[i] = str[i]-'A'+10; } dp[0][0] = 1; limit = (1<<len)-1; for(int i=0;i<=limit;i++) //决定当前所选的数 例如0001 就相当于选了个位的数 for(int kk = 0;kk<k;kk++) //枚举当前可能出现的余数情况。 if(dp[i][kk]) // 如果dp[i][kk] = 0，加了也没什么用，所以剪枝 for(int j=0;j<len;j++) // 枚举可以添加进去的数 if(!(i&(1<<j))) //如果i&(1<<j)!=0 就表明j所选的数，i里面已经存在了，所以不符合全排列情况 dp[i|(1<<j)][(kk*n+num[j])%k] += dp[i][kk]; // 将先前的情况添加到后续情况 kk是num[j]前面的数 所以要*n; printf("Case %d: %lld\n",t,dp[limit][0]); } return 0; }
转载于:https://www.cnblogs.com/yuanshixingdan/p/5543719.html
相关资源：JAVA上百实例源码以及开源项目