组合计数/乘法逆元
排列组合求总方案数
这个可以用一个一维的动态规划解决：
f[i][0]表示第i头牛是牝牛的方案数
f[i][1]表示第i头牛是牡牛的方案数
则转移为：f[i][0]=f[i-1][0]+f[i-1][1];
f[i][1]=f[i-K-1][0]+f[i-K-1][1];
常数优化：将取模运算改为if判断语句……可从20ms降为16ms
/**************************************************************
Problem: 3398
User: Tunix
Language: C++
Result: Accepted
Time:16 ms
Memory:1588 kb
****************************************************************/ //BZOJ 3398
#include<cstdio>
#define F(i,j,n) for(int i=j;i<=n;++i)
int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>'') {if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<='') {v=v*+ch-''; ch=getchar();}
return v*=sign;
}
const int N=,P=;
int f[N][],n,K;
int main(){
n=getint(); K=getint();
f[][]=f[][]=;
F(i,,n){
if(i-K->) f[i][]=f[i-K-][]+f[i-K-][];
else f[i][]=;
f[i][]=f[i-][]+f[i-][];
if(f[i][]>=P) f[i][]-=P;
if(f[i][]>=P) f[i][]-=P;
}
printf("%d\n",(f[n][]+f[n][])%P);
return ;
}
2015年2月6日 15:38:06
UPD: 本题也可用排列组合的方式计算
枚举牝牛的数量a，那么一定至少有(a-1)*k头牡牛，那么除掉这(a-1)*k头牡牛，还剩下b=n-(a-1)*k-a头牡牛。
这a头牝牛和b头牡牛是随便排的……也就是求一个多重全排列 即 (a+b)! / a!*b!
这里的除法需用逆元来算
逆元的计算方法是：已知a、p，求x满足 a*x≡1 (mod p) 那么根据费马小定理（或欧拉定理）可知x= pow(a,p-2)
ps：由于我的方法是O(n)预处理出来所有的阶乘，所以时间复杂度上甚至不如上面那种DP的方法……求大神指导本题0msAC的正确姿势TAT
/**************************************************************
Problem: 3398
User: Tunix
Language: C++
Result: Accepted
Time:24 ms
Memory:2052 kb
****************************************************************/ //BZOJ 3398
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
int getint(){
int v=,sign=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') sign=-; ch=getchar();}
while(isdigit(ch)) {v=v*+ch-''; ch=getchar();}
return v*sign;
}
/*******************template********************/
typedef long long LL;
const int P=;
LL pow(LL a,LL b,LL P){
LL r=,base=a%P;
while(b){
if (b&) r=r*base%P;
base=base*base%P;
b>>=;
}
return r;
}
LL p[];
int main(){
LL n=getint(),k=getint();
p[]=p[]=;
F(i,,n) p[i]=p[i-]*i%P;
LL ans=+n;// 当a=0 ans=1,a=1,ans=n
F(i,,n){
LL a=i,b=n-(i-)*k-i;
if (b<) break;
ans=(ans+p[a+b]*( pow(p[a]*p[b]%P,P-,P) )%P)%P;
}
printf("%lld\n",ans);
return ;
}