牡牛和牝牛

LibreOJ-10230-牡牛和牝牛

实现

#include <iostream>
using namespace std;

const int N = 100010, M = 5000011;
int n, k;
int f[N], sum[N]; // f[i] 记录长度为 i 的以 1 结尾的满足题意的字符串数量

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

    f[0] = sum[0] = 1;
    for (int i = 1; i <= n; ++ i) {
        f[i] = sum[max(0, i - k - 1)];
        sum[i] = (sum[i - 1] + f[i]) % M;
    }
    cout << sum[n] << endl;
    return 0;
}