Advertisement
Saleh127

UVA 12063 / DP

Nov 20th, 2021
873
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-20-22.37.09
  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.  
  12. ll dp[72][70][110];
  13. ll n,k;
  14.  
  15. ll solve(ll one,ll zero,ll r)
  16. {
  17.     if((one+zero)==n)
  18.     {
  19.         if(one==zero && r==0) return 1;
  20.         return 0;
  21.     }
  22.    
  23.     if(dp[one][zero][r]!=-1) return dp[one][zero][r];
  24.  
  25.     return dp[one][zero][r]=solve(one+1,zero,((r*2)+1)%k)+solve(one,zero+1,(r*2)%k);
  26. }
  27.  
  28. int main()
  29. {
  30.     ios_base::sync_with_stdio(0);
  31.     cin.tie(0);
  32.     cout.tie(0);
  33.  
  34.  
  35.  
  36.     test
  37.     {
  38.         ll i,j,l;
  39.  
  40.         cin>>n>>k;
  41.  
  42.         cout<<"Case "<<cs<<": ";
  43.  
  44.         if(n%2==1 || k==0)
  45.         {
  46.             cout<<0<<nl;
  47.         }
  48.         else
  49.         {
  50.             memset(dp,-1,sizeof dp);
  51.  
  52.             cout<<solve(1,0,1%k)<<nl;
  53.         }
  54.     }
  55.  
  56.     get_lost_idiot;
  57. }
  58.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement