题解 P6191 【[USACO09FEB]Bulls And Cows S】

· · 题解

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

问题得以解决。