fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define mod 1000000007
  4. #define max 100001
  5. typedef long long ll;
  6.  
  7. ll rec(ll n, ll m, map<ll,ll>dp){
  8.     if(n<0 || m<0)
  9.         return 0;
  10.     if(n==0)
  11.         return 1;
  12.     if(dp.find(n)!=dp.end()){
  13.     	return dp[n];
  14.     }
  15.     else{
  16.         ll a = rec(n-1,m, dp)%mod;
  17.         ll b = 0;
  18.         if(m<=n)
  19.             b = rec(n-m, m, dp)%mod;
  20.         dp[n] = (a+b)%mod;
  21.         return dp[n];
  22.     }
  23. }
  24.  
  25. int main() {
  26. 	ios_base::sync_with_stdio(false);
  27. 	cin.tie(NULL);
  28. 	cout.tie(NULL);
  29. 	int t;
  30. 	cin>>t;
  31. 	while(t--){
  32. 	    ll n,m;
  33.         cin>>n>>m;
  34.         map<ll,ll>dp;
  35.         ll ans = rec(n,m,dp);
  36.         cout<<ans<<endl;
  37. 	}
  38. 	return 0;
  39. }
Success #stdin #stdout 0s 4248KB
comments (?)
stdin
copy 
3
5 5 
5 6
6 5
stdout
copy 
2
1
3
https://ideone.com/MpyS1Y
language:
C++14 (gcc 8.3)
created:
4 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!