Saleh127

UVA 10616 / DP

Nov 29th, 2021
737
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-29-14.00.19
  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);
  43.     cout.tie(0);
  44.  
  45.     ll q,ca=0;
  46.  
  47.     while(cin>>n>>q && (n+q))
  48.     {
  49.         ll i,j,k,l;
  50.  
  51.         for(i=0; i<n; i++) cin>>a[i];
  52.  
  53.         cout<<"SET "<<++ca<<":"<<nl;
  54.  
  55.         for(i=1;i<=q;i++)
  56.         {
  57.             cin>>d>>m;
  58.  
  59.             memset(dp,-1,sizeof dp);
  60.  
  61.             cout<<"QUERY "<<i<<": ";
  62.             cout<<solve(0ll,0ll,0ll)<<nl;
  63.         }
  64.     }
  65.  
  66.  
  67.     get_lost_idiot;
  68. }
  69.  
RAW Paste Data