Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- string s;
- int k, N;
- int dp[1<<10][1001];
- int solve(int mask, int Mod) {
- int &ret = dp[mask][Mod];
- if(ret!=-1) return ret;
- ret = 0;
- if(mask==(1<<N)-1) {
- return ret = (Mod == 0);
- }
- for(int i=0; i<N; ++i) if(~mask >> i & 1) {
- int next_Mod = (10 * Mod + (s[i]-'0')) % k;
- ret += solve(mask | (1<<i), next_Mod);
- }
- return ret;
- }
- int fact(int n) {
- if(n < 2) return 1;
- return n * fact(n-1);
- }
- void PlayGround() {
- cin >> s >> k;
- N = s.size();
- for(int i=0; i<(1<<N); ++i) {
- for(int j=0; j<k; ++j) {
- dp[i][j] = -1;
- }
- }
- int ans = solve(0, 0);
- vector<int>freq(10);
- for(char c : s) freq[c-'0']++;
- for(auto it : freq) ans /= fact(it);
- cout << ans << '\n';
- // cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
- }
- int main() {
- int T; cin >> T;
- for(int i=1; i<=T; ++i) {
- cout << "Case " << i << ": ";
- PlayGround();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
