bzoj 3398 [Usaco2009 Feb]Bullcow 牡牛和牝牛——前缀和优化dp / 排列组合

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3398

好简单呀。而且是自己想出来的。

dp[ i ]表示最后一个牡牛在 i 的方案数。

当前位置放牝牛，之前的dp[ k ]不变；当前位置放牡牛，出现了dp[ i ]，值是距离大于k的dp[ j ]的和，所以可以前缀和优化。

当然有dp[0]啦。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+,mod=;
int dp[N],c[N],n,k;
int main()
{
scanf("%d%d",&n,&k);
dp[]=;c[]=;
for(int i=;i<=n;i++)dp[i]=c[max(,i-k-)],c[i]=(c[i-]+dp[i])%mod;
printf("%d\n",c[n]);
return ;
}

但是这其实是排列组合的题目。https://www.cnblogs.com/harden/p/6286182.html

逆元不预处理而是现弄其实也挺方便的。“古代猪文”那道题预处理阶乘逆元似乎爆了什么。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+,mod=;
int n,k,jc[N],ans;
void init()
{
jc[]=;
for(int i=;i<=n;i++)jc[i]=(long long)jc[i-]*i%mod;
}
int pw(int x,int k)
{
int ret=;while(k){if(k&)ret=(long long)ret*x%mod;x=(long long)x*x%mod;k>>=;}return ret;
}
int C(int i,int j)
{
return (long long)jc[i]*pw(jc[j],mod-)%mod*pw(jc[i-j],mod-)%mod;
}
int main()
{
scanf("%d%d",&n,&k);
init();
int lm=n/(k+)+-(n%(k+)==);
for(int i=;i<=lm;i++)(ans+=C(n-k*(i-),i))%=mod;// no i=0
printf("%d",(ans+)%mod);
return ;
}