You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

4.9 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##AcWing 1307. 牡牛和牝牛

一、题目描述

约翰要带 N 只牛去参加集会里的展示活动,这些牛可以是牡牛,也可以是牝牛。

牛们要站成一排,但是牡牛是好斗的,为了避免牡牛闹出乱子,约翰决定 任意两只牡牛之间至少要有 K 只牝牛

请计算一共有多少种排队的方法,所有牡牛可以看成是相同的,所有牝牛也一样,答案对 5000011 取模。

输入格式 一行,输入两个整数 NK

输出格式 一个整数,表示排队的方法数。

数据范围 1≤N≤10^5,0≤K<N

输入样例

4 2

输出样例

6

样例解释 6 种方法分别是:牝牝牝牝,牡牝牝牝,牝牡牝牝,牝牝牡牝,牝牝牝牡,牡牝牝牡。

二、隔板法+组合数公式+费马小定理求逆元

黄海理解

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int MOD = 5000011; // 质数,可以使用费马小定理求逆元
const int N = 1e5 + 10;
int fact[N]; // 阶乘数组
// 快速幂
int qmi(int a, int b, int p) {
    int res = 1;
    a %= p;
    while (b) {
        if (b & 1) res = res * a % p;
        b >>= 1;
        a = a * a % p;
    }
    return res;
}
// 利用组合数定义式求C(m,n),用到快速幂求逆元
int C(int m, int n) {
    if (m < n) return 0;
    return fact[m] * qmi(fact[n], MOD - 2, MOD) % MOD * qmi(fact[m - n], MOD - 2, MOD) % MOD;
}

int n, k; // n只牛,两只牡牛之间最少需要k只牝牛
signed main() {
    // 预处理范围内数字的阶乘
    fact[0] = 1;
    for (int i = 1; i < N; i++) fact[i] = (fact[i - 1] * i) % MOD;

    cin >> n >> k;
    int res = 0;
    for (int i = 1; i <= (n + k) / (k + 1); i++)   // 枚举牡牛的所有可能数量
        res = (res + C(n - (i - 1) * k, i)) % MOD; // 累计组合数

    // 如果0只牡牛,还应该增加一种方案,就是全都是牝牛
    cout << res + 1 << endl;
}

三、动态规划法

设牡(公牛)为1,牝(母牛)为0,就是:

0 0 0 0
0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 0
1 0 0 1

题目大意是一共要求携带n头牛,牛分为两种:10两种种类。

题目要求11之间至少要间隔K0

求出满足上述要求的方案数

闫氏DP分析法 f[i]集合:考虑前i头牛,且第i头牛是1的方案 f[i]属性:方案数

状态计算:f[i] = f[i - k - 1] + f[i - k - 2] + ··· + f[0]

(↑集合划分的依据是题目的要求,即当前1与上一个1之间至少要间隔k0)

此处设置一个边界f[0]表示只有0没有1的边界情况

如何计算最终答案 根据上述集合的含义 我们最终的答案就是把所有的f[i](包括f[0],表示该方案全是0,没有1)累加起来即可。

res = f[0] + f[1] + ··· + f[n]

无论是状态计算,还是答案求和,都要用到求区间和的部分

因此本题还可以采用前缀和数组,优化掉上述的计算

朴素版本

#include <bits/stdc++.h>
using namespace std;

const int N = 100010, mod = 5000011;

int n, k;
int f[N];

// PASS 8/12 其它的TLE
int main() {
    cin >> n >> k;
    f[0] = 1; // 此处设置一个边界f[0]表示只有0没有1的边界情况

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

    int res = 0;
    for (int i = 0; i <= n; i++) res = (res + f[i]) % mod;

    printf("%d\n", res);
    return 0;
}

前缀和优化

#include <bits/stdc++.h>
using namespace std;

const int N = 100010, mod = 5000011;

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

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

    f[0] = s[0] = 1;
    for (int i = 1; i <= n; i++) {
        if (i - k - 1 > 0)
            f[i] = s[i - k - 1]; // 利用前缀和优化
        else
            f[i] = f[0];

        s[i] = (s[i - 1] + f[i]) % mod; // 维护前缀和
    }
    printf("%d\n", s[n]);
    return 0;
}