自动搬运

查看原文

来自洛谷，原作者为

	houzhiyuan 花谢花飞花满天，红消香断有谁怜？

搬运于2025-08-24 22:18:24，当前版本为作者最后更新于2020-03-12 16:57:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P6191 【[USACO09FEB]Bulls And Cows S】

题目传送门

管理员大大，这只是个更新，审核求过

1.递推做法（速度较快，适合初学者）

这题是一个十分恶心的递推。

怎么推递推式呢，先看各种错误方法的分析：

1.由于两头公牛之间至少有k头奶牛，那么直接加上前i-k头奶牛的可能性，得到以下代码：

f[i]=f[i-1];//放奶牛
if(i>k+1)f[i]+=f[i-k-1];//放公牛

然而，听取WA声一片。为什么呢？因为可以在i的地方放公牛的方案i-k没有全部包括进去，考虑将公牛和奶牛分开。

2.用两个数组储存最后一个放奶牛和公牛的方案数，得到以下代码：

fn[i]=fn[i-1]+fg[i-1];//前面一个无论是什么，都可以放奶牛
if(i>k+1)fg[i]=fg[i-k-1];//放公牛

然而还是错的。因为当i-k-1位置就算放奶牛，第i个位置仍然可以放公牛，并且当i<=k+1时，可以直接放一头公牛。

得到正确的递推式：

fn[i]=fn[i-1]+fg[i-1];
if(i>k+1)fg[i]=fg[i-k-1]+fn[i-k-1];
else fg[i]=1;

附上完整代码：

#include<bits/stdc++.h>
using namespace std;
int fn[100001],fg[100001],n,k;
int main(){
	cin>>n>>k;
	fn[1]=1;//先赋初值
	fg[1]=1;
	for(int i=2;i<=n;i++){
		fn[i]=(fn[i-1]+fg[i-1])%5000011;
		if(i>k+1){//上面的递推式
			fg[i]=(fg[i-k-1]+fn[i-k-1])%5000011;
		}
		else{
			fg[i]=1;	
		}
	}
	cout<<(fg[n]+fn[n])%5000011<<endl;
	return 0;
}

2.组合做法（速度较慢，对于大佬来说较为简单）

（下面是初学组合者教学，大佬勿喷）

从 n 个不同元素中，任取 m $( m\leq n )$ 个元素组成一个集合，叫做从 n 个不同元素中取出 m 个元素的一个组合；，叫做从 n 个不同元素中取出 m 个元素的组合数。用符号 $\mathrm C_n^m$ 来表示。

即$\mathrm C_n^m = \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n - m)!}$

求组合数可以用乘法逆元，详情见乘法逆元

那么我们枚举放的公牛数，每放一头公牛，可以放公牛的位置就会$-k$，在这些位置中随意拿出$i$个位置来放公牛就是方案数，即

$$\sum_{i=0}^{n/(k+1)} \mathrm C_{n-k*i}^i$$

由于处理$i$循环上线的问题，将原式变成：

$$(\sum_{i=0}^{(n-1)/(k+1)} \mathrm C_{n-k*i}^{i+1})+1 $$

问题得以解决。