401D - Roman and Numbers - CodeForces Solution

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;
long long dp[101][262144];

long long ankit(string&s,int pbit,int m,int rem){
    
    if( pbit==(1<<s.size())-1 ) return   rem == 0 ;
    if( dp[rem+1][pbit]!=-1 ) return dp[rem+1][pbit];
    // cout<<pbit<<" "<<rem<<" "<<endl;
    long long ans=0,taken=0;
    
    if(rem==-1){
        for(int i=0;i<s.size();i++){
            if( taken&(1<<(s[i]-'0')) ) continue;
            
            if( (pbit&(1<<i))==0 && s[i]!='0' ){
                ans += ankit(s,pbit|(1<<i),m, (s[i]-'0'+m)%m );
                taken = taken|(1<<(s[i]-'0')); 
            }
        }
    }
    else{
        for(int i=0;i<s.size();i++){
            
            if( taken&(1<<(s[i]-'0')) ) continue;
            
            if( (pbit&(1<<i))==0 ){
                ans += ankit(s,pbit|(1<<i),m, (rem *10 + (s[i]-'0'))%m );
                taken = taken|(1<<(s[i]-'0')); 
            }
        }
    }
    
    return dp[rem+1][pbit] = ans;
}

int main() {
    
    ios_base::sync_with_stdio(false); 
	cin.tie(NULL);                    
	cout.tie(NULL);
    
    long long n,m,ms=1;
    cin>>n>>m;
    string str = to_string(n);
    // cout<<str;
    memset(dp,-1,sizeof(dp));
    // map<char,int> mp;
    
    // for(int i=0;i<str.size();i++){
    //     mp[str[i]]++;
    //     ms *= mp[str[i]];
    // }
    // for(auto e:mp) ms *= e.second;
    // cout<<ms<<endl;
    
    cout << ankit(str,0,m,-1);
    
    // cout<<ans;

    return 0;
}