#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9+7;
unordered_map<long long,long long>mp;
long long n,m;
long long dp(long long n){
if(n<0)
return 0;
if(n<m)
return 1;
if(mp.find(n)!=mp.end())//已经存在过mp[n]的话返回就完事了
return mp[n];
long long mid=n/2;//二分
long long tot=dp(mid)*dp(n-mid)%mod;//一半的每种情况都可以对应另一半的任意一种情况所以可以分解为两半相乘
for(long long i=1;i<m;i++)//dp[n]=dp[n-1]+dp[n-m],状态转移的灵感来源
tot=(tot+dp(mid-i)*dp(n-m-(mid-i))%mod)%mod;//n-m到n这一段的组合情况
mp[n]=tot;//更新
return mp[n];
}
int main(){
scanf("%lld%lld",&n,&m);
mp[0]=0;
mp[1]=1;
printf("%lld",dp(n));
return 0;
}
相关文章
- Educational Codeforces Round 65 (Rated for Div. 2) D. Bicolored RBS
- Educational Codeforces Round 42 (Rated for Div. 2) D. Merge Equals
- Educational Codeforces Round 69 (Rated for Div. 2)D(DP,思维)
- Educational Codeforces Round 142 (Rated for Div. 2) A-D
- Educational Codeforces Round 46 (Rated for Div. 2) D. Yet Another Problem On a Subsequence
- Educational Codeforces Round 60 (Rated for Div. 2) - D. Magic Gems(动态规划+矩阵快速幂)
- Educational Codeforces Round 89 (Rated for Div. 2)D. Two Divisors 线性筛质因子
- C. Magic Ship Educational Codeforces Round 60 (Rated for Div. 2)
- Educational Codeforces Round 63 (Rated for Div. 2) D. Beautiful Array (简单DP)
- Educational Codeforces Round 34 (Rated for Div. 2) D - Almost Difference(高精度)