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)
  9. //         return 0;
  10. //     if(n==0)
  11. //         return 1;
  12. //     // else if(n==m)
  13. //     //     return 2;
  14. //     if(dp.find(n)!=dp.end()){
  15. //     	return dp[n];
  16. //     }
  17. //     else{
  18. //         ll a = rec(n-1,m, dp)%mod;
  19. //         ll 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 dp[n+1]={0};
  36.         dp[0]=1;
  37.         dp[1]=1;
  38.         for(ll i=2; i<=n; i++){
  39.             dp[i] = (dp[i]%mod + dp[i-1]%mod)%mod;
  40.             if(i>=m)
  41.                 dp[i] = (dp[i]%mod + dp[i-m]%mod)%mod;
  42.         }
  43.         cout<<dp[n]<<endl;
  44. 	}
  45. 	return 0;
  46. }
Time limit exceeded #stdin #stdout 5s 4396KB
comments (?)
stdin
copy 
5
5 5
5 10
10 5
5 100
100 5
stdout
copy 
2
1
8
1
https://ideone.com/itj49D
language:
C++14 (gcc 8.3)
created:
5 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!