「一本通 6.6 练习 1」牡牛和牝牛

题目描述

$N$ 只牛（牡牛/牝牛相同）排队，任意两只牡牛之间至少 $K$ 只牝牛，求合法方案数对 $5000011$ 取模（ $1 \le N \le 10^5$ ， $0 \le K < N$ ）。

思路

设 $s_i$ 为长度 $i$ 的方案数：末位放牝牛贡献 $s_{i-1}$ ，放牡牛时若 $i \le K$ 贡献 1、否则贡献 $s_{i-K-1}$ ，两者相加取模，答案为 $s_N$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18"""排队方案数：任意两只牡牛之间至少 K 只牝牛。O(N) DP,取模 5000011。"""
import sys

def main() -> None:
    n, k = map(int, sys.stdin.read().split())
    MOD = 5000011
    # b[i]: 长 i 且以牡牛结尾的方案数; c[i]: 以牝牛结尾; s[i]: 总方案数
    b = [0] * (n + 1)
    c = [0] * (n + 1)
    s = [0] * (n + 1)
    s[0] = 1
    for i in range(1, n + 1):
        b[i] = s[i - k - 1] if i > k else 1   # 结尾放牡牛: 上一头牡牛最远到 i-k-1,否则它是第一头
        c[i] = s[i - 1]                       # 结尾放牝牛: 任意合法前缀延长
        s[i] = (b[i] + c[i]) % MOD
    print(s[n] % MOD)

main()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 01:39
 * update_at: 2026-10-06 01:39
 */
#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

const ll MOD = 5000011;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll n, k;
    cin >> n >> k;

    // s[i] 表示长度 i 的合法方案总数
    vector<ll> s(n + 1);
    s[0] = 1; // 空前缀

    for (ll i = 1; i <= n; i++) {
        ll c = s[i - 1]; // 以牝牛结尾：前 i-1 位任意合法方案
        ll b;
        if (i <= k) {
            b = 1; // 以牡牛结尾且它是第一头牡牛
        } else {
            b = s[i - k - 1]; // 上一头牡牛至少在前 i-k-1 位
        }
        s[i] = (b + c) % MOD;
    }

    cout << s[n] << "\n";
    return 0;
}

「一本通 6.6 练习 1」牡牛和牝牛

目录

题目描述

思路

参考代码