## Algorithm

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 res = 0;
for(int i=0;i<digits.size();i++)
res += solve(bitmask | (1<<i), (mod*10+digits[i])%d);
}

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);
}
}

Copy The Code &

Input

cmd
3
000 1
1234567890 1
123434 2

Output

cmd
1
3628800
90