Advertisement
Saleh127

Light OJ 1125 / DP

Nov 11th, 2021
578
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-11-16.18.12
  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[204][25][25];
  13.  
  14. ll a[555],d,m,n;
  15.  
  16. ll solve(ll in, ll tk,ll mod)
  17. {
  18.      if(mod<0) mod+=d;
  19.  
  20.      if(in>n) return 0;
  21.  
  22.      if(in==n || tk==m)
  23.      {
  24.           if(mod==0 && tk==m) return 1ll;
  25.           return 0;
  26.      }
  27.  
  28.      if(dp[in][mod][tk]!=-1) return dp[in][mod][tk];
  29.  
  30.      ll ans=0;
  31.  
  32.      ans= solve(in+1,tk+1,(mod+a[in])%d) + solve(in+1,tk,mod);
  33.  
  34.      dp[in][mod][tk]=ans;
  35.  
  36.      return ans;
  37. }
  38.  
  39. int main()
  40. {
  41.    ios_base::sync_with_stdio(0);
  42.    cin.tie(0);cout.tie(0);
  43.  
  44.  
  45.    test
  46.    {
  47.         ll i,j,k,l,q;
  48.  
  49.         cin>>n>>q;
  50.  
  51.         for(i=0;i<n;i++) cin>>a[i];
  52.  
  53.         cout<<"Case "<<cs<<":"<<nl;
  54.  
  55.         while(q--)
  56.         {
  57.              cin>>d>>m;
  58.  
  59.              memset(dp,-1,sizeof dp);
  60.  
  61.              cout<<solve(0ll,0ll,0ll)<<nl;
  62.         }
  63.    }
  64.  
  65.    get_lost_idiot;
  66. }
  67.  
  68.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement