Advertisement
Saleh127

Light OJ 1021 / Bitmask Dp

Jan 24th, 2022
1,208
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2022-01-24-23.17.46
  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 Set(ll N,ll pos){return N=N |(1<<pos);}
  13. ll reset(ll N,ll pos){return N= N & ~(1<<pos);}
  14. bool check(ll N,ll pos){return (bool)(N & (1<<pos));}
  15.  
  16.  
  17. void val()
  18. {
  19.     for(char c='0';c<='9';c++)
  20.     {
  21.          x[c]=c-'0';
  22.     }
  23.     for(char c='A';c<='F';c++)
  24.     {
  25.          x[c]=c-'A'+10;
  26.     }
  27. }
  28.  
  29. ll dp[(1<<16)+4][21];
  30. ll b,k,n;
  31. string a;
  32.  
  33. ll solve(ll mask,ll rem)
  34. {
  35.       if(mask==(1<<n)-1) return rem==0ll;
  36.  
  37.       if(dp[mask][rem]!=-1) return dp[mask][rem];
  38.  
  39.       ll ans=0ll;
  40.  
  41.       for(ll i=0;i<n;i++)
  42.       {
  43.            if(check(mask,i)==0)
  44.            {
  45.                 ans+=solve(Set(mask,i),(rem*b+x[a[i]])%k);
  46.            }
  47.       }
  48.       return dp[mask][rem]=ans;
  49. }
  50.  
  51. int main()
  52. {
  53.    ios_base::sync_with_stdio(0);
  54.    cin.tie(0);cout.tie(0);
  55.  
  56.    val();
  57.  
  58.    test
  59.    {
  60.         cin>>b>>k;
  61.         cin>>a;
  62.         n=a.size();
  63.         memset(dp,-1,sizeof dp);
  64.  
  65.         cout<<"Case "<<cs<<": "<<solve(0,0)<<nl;
  66.    }
  67.  
  68.  
  69.    get_lost_idiot;
  70. }
  71.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement