Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=2025
Given a string s and a positive integer d you have to determine how many permutations of s are divisible by d. Input First line of the input contains one integer T the number of test cases. Each of the test cases is one line containing s and d separated by a single space. Output For each test case output contains an integer the number of permutations of s that are divisible by d. Constraints • s contains only digits. • The length of s is between 1 and 10 inclusive. • d is a positive integer between 1 and 10000.
Sample Input 3 000 1 1234567890 1 123434 2
Sample Output 1 3628800 90
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int tc,d,ok;
string in;
vector<int> factorial;
vector<int> digits;
vector<int> cnt_digit;
int memo[1<<10][10001];
int solve(int bitmask, int mod){
if(bitmask == ok) return mod==0;
if(memo[bitmask][mod] != -1) return memo[bitmask][mod];
int res = 0;
for(int i=0;i<digits.size();i++)
if((bitmask &(1<<i))==0)
res += solve(bitmask | (1<<i), (mod*10+digits[i])%d);
return memo[bitmask][mod] = res;
}
int main() {
factorial.push_back(1);
while(factorial.size()!=10)
factorial.push_back(factorial.size()*factorial.back());
scanf("%d",&tc);
while(tc--){
cnt_digit.assign(10,0);
digits.clear();
memset(memo, -1, sizeof memo);
cin >> in;
scanf("%d",&d);
for(char c : in) {
int v = c-'0';
digits.push_back(v);
cnt_digit[v]++;
}
ok = (1<<digits.size())-1;
int total_cnt = solve(0,0);
for(int i=0;i<10;i++) total_cnt /= factorial[cnt_digit[i]];
printf("%d\n",total_cnt);
}
}
Input
000 1
1234567890 1
123434 2
Output
3628800
90
Demonstration
UVA Online Judge solution - 11084-Anagram Division - UVA Online Judge solution in C,C++,java