BZOJ_3398_[Usaco2009 Feb]Bullcow 牡牛和牝牛_组合数学
2024-10-18 22:36:39
BZOJ_3398_[Usaco2009 Feb]Bullcow 牡牛和牝牛_组合数学
Description
约翰要带N(1≤N≤100000)只牛去参加集会里的展示活动,这些牛可以是牡牛,也可以是牝牛.牛们要站成一排.但是牡牛是好斗的,为了避免牡牛闹出乱子,约翰决定任意两只牡牛之间至少要有K(O≤K<N)只牝牛.
请计算一共有多少种排队的方法.所有牡牛可以看成是相同的,所有牝牛也一样.答案对5000011取模
Input
一行,输入两个整数N和K.
Output
一个整数,表示排队的方法数.
Sample Input
4 2
Sample Output
6
枚举一个A牛的个数x,每两头A牛中间至少有K头B牛。
于是把这些必须放的减掉,就是一个挡板问题。
对答案的贡献是C[n-(x-1)*k][x]。
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define mod 5000011
typedef long long ll;
#define N 100050
ll qp(ll x,ll y) {
ll re=1; for(;y;y>>=1ll,x=x*x%mod) if(y&1ll) re=re*x%mod; return re;
}
ll fac[N],inv[N];
int n,K;
void init() {
int i=0;
for(fac[0]=1,i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
inv[n]=qp(fac[n],mod-2);
for(i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
ll C(int x,int y) {
if(x<y) return 0;
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main() {
scanf("%d%d",&n,&K);
init();
int i;
ll ans=0;
for(i=1;n-(i-1)*K>=i;i++) {
(ans+=C(n-(i-1)*K,i))%=mod;
}
printf("%lld\n",(ans+1)%mod);
}
最新文章
- Java虚拟机8:虚拟机性能监控与故障处理工具
- javascript高级程序设计---Event对象二
- 申请UAC权限Manifest文件
- FRM-92101解决办法
- Oracle Names - Oracle_SID /db_name instance_name service_names / service_name / sid / sid_name
- timus 1022 Genealogical Tree(拓扑排序)
- C# mvc--EF引用程序集 和EDMX中相关的文件说明
- C++中的多态
- 高并发的常见策略--大型web项目
- [C#] 常用工具类——系统日志类
- cglib根据数据动态生成对象
- Word Count作业
- python辅助sql手工注入猜解数据库案例分析
- Atitti mybatis的单元测试attilax总结
- JS DOM节点
- JS以及CSS对页面的阻塞
- java 每一个对象都是根据hashCode区别的 每次返回不同的内存地址
- Word操作(基于word2013)【非编程类】
- [转发]SPRING MVC3.2案例讲解--SPRING MVC3的@ResponseBody和ResponseEntity
- 本地如何将svn和git管理的代码做关联