基础数学算法-牡牛和牝牛

题目-牡牛和牝牛(组合计数)

问题分析

大意就是一共$n$只牛, 牛分为$1$型牛, 和$0$型牛, 要求在每两个$1$之间至少有$k$个$0$型牛, 问方案数

$dp$方式解决组合计数问题, 定义状态表示$f(i)$考虑前$i$头牛, 并且$i$位置是$1$型牛的方案数量

$$f(i)=f(i-k-1)+f(i-k-2)+...+f(0)$$

边界情况, 当$f(0)$相当于没有$1$型牛只有$0$型牛的情况, 也就是说$f(0)=1$
如果直接计算, 状态数量是$O(n)$, 算法时间复杂度是$O(n^2)$, 需要进行优化

因为每次计算都是区间和, 可以使用前缀和优化

算法步骤

• 初始化$f(0)$
• 假设前缀和函数是$s$, $f(i)=s_{i-k-1}$
• 对前缀和进行累加, $s_i=s_{i-1}+f(i)$
• 对答案进行化整为零的过程, 假设答案的集合是$S$, 可以按照最后一个$1$的位置对集合进行划分, 也就是说$ans=f(0)+f(1)+...+f(n)=s_n$, 因此答案就是$s_n$

优化后的时间复杂度是$O(n)$

代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, MOD = 5000011;

int n, k;
int f[N], s[N];

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

    cin >> n >> k;
    f[0] = 1;
    s[0] = 1;
    for (int i = 1; i <= n; ++i) {
   
        f[i] = s[max(i - k - 1, 0)];
        s[i] = (s[i - 1] + f[i]) % MOD;
    }
    
    cout << s[n] << '\n';
    return 0;
}