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
4.9 KiB
一、题目描述
约翰要带 N
只牛去参加集会里的展示活动,这些牛可以是牡牛,也可以是牝牛。
牛们要站成一排,但是牡牛是好斗的,为了避免牡牛闹出乱子,约翰决定 任意两只牡牛之间至少要有 K
只牝牛。
请计算一共有多少种排队的方法,所有牡牛可以看成是相同的,所有牝牛也一样,答案对 5000011
取模。
输入格式
一行,输入两个整数 N
和 K
。
输出格式 一个整数,表示排队的方法数。
数据范围
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
头牛,牛分为两种:1
和0
两种种类。
题目要求1
与1
之间至少要间隔K
个0
求出满足上述要求的方案数
闫氏DP
分析法:
f[i]
集合:考虑前i
头牛,且第i
头牛是1
的方案
f[i]
属性:方案数

状态计算:f[i] = f[i - k - 1] + f[i - k - 2] + ··· + f[0]
(↑集合划分的依据是题目的要求,即当前1
与上一个1
之间至少要间隔k
个0
)
此处设置一个边界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;
}