Advertisement
Saleh127

Light OJ 1158 / Bitmask DP

Jan 26th, 2022
1,101
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2022-01-26-15.34.45
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11. map<char,ll>x;
  12. ll dp[(1<<10)+1][1002],m,n;
  13. string a;
  14. ll f[12];
  15.  
  16. ll Set(ll N,ll pos){return N=N |(1<<pos);}
  17. ll reset(ll N,ll pos){return N= N & ~(1<<pos);}
  18. bool check(ll N,ll pos){return (bool)(N & (1<<pos));}
  19.  
  20. ll solve(ll rem,ll mask)
  21. {
  22.      if(mask==(1<<n)-1) return rem==0;
  23.  
  24.      if(dp[mask][rem]!=-1) return dp[mask][rem];
  25.  
  26.      ll ans=0;
  27.  
  28.      for(ll i=0;i<n;i++)
  29.      {
  30.           if(check(mask,i)==0)
  31.           {
  32.                ans+=solve((rem*10+x[a[i]])%m,Set(mask,i));
  33.           }
  34.      }
  35.  
  36.      return dp[mask][rem]=ans;
  37. }
  38.  
  39. int main()
  40. {
  41.    ios_base::sync_with_stdio(0);
  42.    cin.tie(0);cout.tie(0);
  43.  
  44.    for(char c='0';c<='9';c++) x[c]=c-'0';
  45.    f[0]=1;
  46.    for(ll i=1;i<=12;i++) f[i]=f[i-1]*i;
  47.  
  48.    test
  49.    {
  50.         cin>>a>>m;
  51.  
  52.         n=a.size();
  53.  
  54.         memset(dp,-1,sizeof dp);
  55.  
  56.         ll ans=solve(0,0);
  57.  
  58.         map<char,ll>y;
  59.  
  60.         for(ll i=0;i<n;i++)
  61.         {
  62.              y[a[i]]++;
  63.         }
  64.  
  65.         for(char c='0';c<='9';c++)
  66.         {
  67.              ans/=f[y[c]];
  68.         }
  69.  
  70.         cout<<"Case "<<cs<<": "<<ans<<endl;
  71.    }
  72.  
  73.    get_lost_idiot;
  74. }
  75.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement