lightoj 1158 - Anagram Division

本文主要是介绍lightoj 1158 - Anagram Division，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Given a string s and a positive integer d you have to determine how many permutations of s are divisible by d.

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case contains a string s (1 ≤ s_length ≤ 10) and an integer d (1 ≤ d ≤ 1001). s will only contain decimal digits.

Output

For each case, print the case number and the number of permutations of s that are divisible by d.

Sample Input	Output for Sample Input
3 000 1 1234567890 1 123434 2	Case 1: 1 Case 2: 3628800 Case 3: 90

给你一个字符串，问你用这些数字能排列出多少种不同的数字能被d整除。

直接状压求出所有能被d整除的排列，然后再除以每个数字出现次数的阶乘，就是答案了。

DP的时候优化一点，就不会超时了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 1e9
#define endl '\n'
#define mod 100000007
#define LL long longusing namespace std;int dp[1100][1100];int main(void)
{int T,n,d,i,j,k;scanf("%d",&T);char s[15];int f[15],a[15],num[15];int cas =  1;f[0] = 1;for(i=1;i<=10;i++)f[i] = f[i-1]*i;while(T--){scanf("%s%d",s,&d);n = strlen(s);memset(num,0,sizeof(num));memset(dp,0,sizeof(dp));for(i=0;i<n;i++){a[i] = s[i] - '0';num[a[i]]++;}dp[0][0] = 1;for(i=0;i<(1<<n);i++){for(j=0;j<n;j++){if(i&(1<<j))continue;for(k=0;k<d;k++){if(dp[i][k]==0)continue;dp[i|(1<<j)][(k*10+a[j])%d]+=dp[i][k];}}}int ans = dp[(1<<n)-1][0];for(i=0;i<10;i++)ans /= f[num[i]];printf("Case %d: %d\n",cas++,ans);}return 0;
}

这篇关于lightoj 1158 - Anagram Division的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---