来源：1307. 牡牛和牝牛

#include <iostream>

using namespace std;

const int N = 1e5 + 7, mod = 5000011;

int f[N];

int main() {
    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= k + 1; i ++) {
        f[i] = i + 1;
    }

    for (int i = k + 2; i <= n; i ++) {
        f[i] = (f[i - 1] + f[i - k - 1]) % mod;
    }

    cout << f[n] << endl;

    return 0;
}

DP 三部曲

状态表示：f[i]表示符合题目要求的 i 头牛的排列方式
状态计算：根据第 i 头牛是”0”还是”1”去划分
边界设置：设置f[0] = 1后，f[1]~f[n]都能被计算出

#include <iostream>

using namespace std;

const int N = 1e5 + 7, mod = 5000011;

int f[N];

int main() {
    int n, k;
    cin >> n >> k;

    f[0] = 1;
    for (int i = 1; i <= n; i ++) {
        f[i] += f[i - 1];
        if (i >= k + 1) f[i] += f[i - k - 1];
        else f[i] += 1;
        f[i] = f[i] % mod;
    }


    cout << f[n] << endl;

    return 0;
}