Advertisement
Saleh127

POJ 2229 / DP

Oct 20th, 2021
589
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-10-20-21.19.38
  3. ***/
  4. #include <iostream>
  5. #include<vector>
  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. ll dp[1000002];
  11. int main()
  12. {
  13.    ios_base::sync_with_stdio(0);
  14.    cin.tie(0);cout.tie(0);
  15.  
  16.  
  17.    ll n,m,i,j,k,l=1e9;
  18.  
  19.    vector<ll>x;
  20.  
  21.    k=1;
  22.  
  23.    x.push_back(1);
  24.  
  25.    cin>>n;
  26.  
  27.    for(i=0;;i++)
  28.    {
  29.         if(k*2>n) break;
  30.  
  31.         k*=2;
  32.  
  33.         x.push_back(k);
  34.    }
  35.  
  36.  
  37.    dp[0]=1;
  38.  
  39.    k=x.size();
  40.  
  41.    for(i=0;i<k;i++)
  42.    {
  43.         for(j=1;j<=n;j++)
  44.         {
  45.              if(j>=x[i])
  46.              {
  47.                   dp[j]+=dp[j-x[i]];
  48.                   if(dp[j]>l)
  49.                   {
  50.                        dp[j]-=l;
  51.                   }
  52.              }
  53.         }
  54.    }
  55.  
  56.    cout<<dp[n]<<endl;
  57.  
  58.    get_lost_idiot;
  59. }
  60.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement