题解 | #困难的数学题#

c题题解

思路

状态表示：f[i] => 组成正整数i的方案数 （组成i：若干个正整数相加得到的和为i）
由题意知：相加序列中的每个数都大于或者等于k

所以可进行集合划分如下：
case 1：相加序列中的最后一个数为k.因为减去k之后和为i-k，所以此时的方案数为 f[i-k]
case 2：相加序列中的最后一个数大于k，最后一个数减去1之和和为i-1，所以此时的方案数为f[i-1]

综上 Code如下.

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#define mod 1000000007

using namespace std;

typedef long long ll;

const int N=1e6+10;

ll f[N]; // f[i]：组成正整数i的方案数
int n,k;

int main(){   
    scanf("%d %d",&n,&k);

    f[k]=1;  //f[i],i从k开始有效
    for(int i=k;i<=n;i++)  f[i]=(f[i]+f[i-k]+f[i-1])%mod;

    cout<<f[n]<<endl;

    return 0;
}