Description:
约翰要带 N 只牛去参加集会里的展示活动,这些牛可以是牡牛,也可以是牝牛。
牛们要站成一排,但是牡牛是好斗的,为了避免牡牛闹出乱子,约翰决定任意两只牡牛之间至少要有 K 只牝牛。
请计算一共有多少种排队的方法,所有牡牛可以看成是相同的,所有牝牛也一样,答案对 5000011 取模。
Solution:
首先,我这种方法时间复杂度仍然是O(n),可是常数比其他大佬的要大许多(所以不够优秀
直接i从0到n枚举牝牛的数量
可以得到杜牛的数量是n-i
要先用(n-i-1)*k条牝牛把杜牛隔开
还剩i-(n-i-1)*k条
这些牝牛需要分到杜牛隔开的n-i+1段中,由隔板法得其方案数是C(i-(n-i-1)*k+n-i,n-i),统计到答案里就可以了
由于n的极限范围是10^5,所以要事先预处理然后每次求组合数就是O(1)了
代码如下
Code:
#include <iostream>
#include <cstdio>
using namespace std;
const int N=2e5+10,mod=5e6+11;
int inf[N],infact[N],fact[N];
int C(int n,int m){
if(n<0||m<0||n<m)return 0;
return 1ll*fact[n]*infact[m]%mod*infact[n-m]%mod;
}
int n,k;
int main(){
scanf("%d%d",&n,&k);
for(int i=0;i<2;i++)
inf[i]=infact[i]=fact[i]=1;
for(int i=2;i<=n+k;i++){
inf[i]=1ll*(mod-mod/i)*inf[mod%i]%mod;
infact[i]=1ll*infact[i-1]*inf[i]%mod;
fact[i]=1ll*fact[i-1]*i%mod;
}
int ans=0,res;
for(int i=0;i<=n;i++){
ans=(ans+C(i-(n-i-1)*k+n-i,n-i))%mod;
}
printf("%d\n",ans);
return 0;
}
看不懂组合数怎么求出来的
我思路也是这个,用隔板法,但是不知道怎么用代码实现
由隔板法得那里看不懂啊,能不能具体一点(/(ㄒoㄒ)/~~)
好像是根据隔板法的原理公式等价转换的,可能需要搜索一下隔板法
膜拜大佬%%%%
点个支持撒
在哪里点支持啊?
我点了那个星星
那个箭头,朝上的
星星是收藏
got it