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);
    }
}
  
Copy The Code & Try With Live Editor

Input

x
+
cmd
3
000 1
1234567890 1
123434 2

Output

x
+
cmd
1
3628800
90
Advertisements

Demonstration


UVA Online Judge solution - 11084-Anagram Division - UVA Online Judge solution in C,C++,java

Previous
UVA Online Judge solution - 11080-Place the Guards - UVA Online Judge solution in C,C++,java
Next
UVA Online Judge solution - 11085-Back to the 8-Queens - UVA Online Judge solution in C,C++,java