fork(2) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define F(i, a, b) for (int i = a; i <= b; i++)
  6. int M = 1000000007;
  7.  
  8. int val[1001][1001];
  9. int n,k;
  10. int dp(int cur,int rem)
  11. {
  12.     if(cur<1 || cur>k || rem<0 || rem>n)return 0;
  13.     if(cur==1 || rem==0)return 1;
  14.  
  15.     if(val[cur][rem]==-1)
  16.     {
  17.         int ans=0;
  18.         ans+=dp(cur,rem-1);
  19.         ans%=M;
  20.         ans+=dp(cur-1,n-rem);
  21.         ans%=M;
  22.         val[cur][rem]=ans;
  23.     }
  24.  
  25.     return val[cur][rem];
  26.  
  27. }
  28.  
  29. void solve()
  30. {
  31.     cin>>n>>k;
  32.  
  33.     F(i,0,k)F(j,0,n)val[i][j]=-1;
  34.  
  35.     cout<<dp(k,n);
  36.     cout<<"\n";
  37. }
  38.  
  39. signed main()
  40. {
  41.     ios_base::sync_with_stdio(false);
  42.     cin.tie(nullptr);
  43.     cout.tie(nullptr);
  44.  
  45.     int _t=1;
  46.     cin>>_t;
  47.     for (int i=1;i<=_t;i++)
  48.     {
  49.         solve();
  50.     }
  51.     return 0;
  52. }
Success #stdin #stdout 0.06s 58252KB
comments (?)
stdin 
1
1000 1000
stdout 
211715064
https://ideone.com/Bh0vGe
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!