牡牛和牝

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 771 字

N只牛排成一排，每只为牡牛或牝牛，要求任意两

一本通
练习

正文

/*
原题：T1652「一本通 6.6 练习 1」牡牛和牝
题意：N 只牛排成一排，每只为牡牛或牝牛，要求任意两只牡牛之间至少有 K 只牝牛，
求排队方法数对 5000011 取模的结果。
思路：设 f[i] 为长度 i 的合法方案数。末位放牝牛有 f[i-1] 种；
末位放牡牛时，它前面 K 位必须都是牝牛，于是前 i-K-1 位可以是任意合法串。
若 i≤K 则不存在更早的牡牛，只有「全是牝牛加末尾一头牡牛」这 1 种。
复杂度：时间 O(N)，空间 O(N)
易错点：1) i≤K 时这一项取 1 而不是 f[i-K-1]（下标为负）；
2) 空串也算一种（f[0]=1），它对应「只有一头牡牛」的情形；
3) 每步取模，防止结果溢出。
*/
#include <bits/stdc++.h>
using namespace std;
const long long MOD=5000011;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long N;
    int K;
    cin>>N>>K;
    vector<long long> f(N+1,0);
    f[0]=1;
    for(long long i=1;i<=N;i++){
        long long add;
        if(i>=K+1){
            add=f[i-K-1];
        }else{
            add=1;
        }
        f[i]=(f[i-1]+add)%MOD;
    }
    cout<<f[N]<<"\n";
    return 0;
}

牡牛和牝

正文

一本通·提高篇的其它内容