bzoj3398 [Usaco2009 Feb]Bullcow 牡牛和牝牛—

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

对于这种有点巧妙的递推还是总是没有思路...

设计一个状态 f[i] 表示第 i 位置上是公牛，那么 f[i] = ∑(0<=j<i-k) f[j]；

再前缀和优化一下即可。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int const maxn=1e5+,mod=;

int n,k,f[maxn],s[maxn];

int main()

{

    scanf("%d%d",&n,&k);

    f[]=;s[]=;

    for(int i=;i<=n;i++)

    {

        f[i]=(s[max(,i-k-)])%mod;

        s[i]=(s[i-]+f[i])%mod;

    }

    printf("%d",s[n]);

    return ;

}

当然也可以用组合数：https://www.cnblogs.com/harden/p/6286182.html

(注意取模与 (ll) 与加括号的艺术...)

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

ll ans;

int n,k,mod=;

int pw(int a,int b)

{

    int ret=;

    for(;b;b>>=,a=((ll)a*a)%mod)

        if(b&)ret=((ll)ret*a)%mod;

    return ret;

}

int C(int n,int m)

{

    int a=,b=;

    for(int i=n-m+;i<=n;i++) a=((ll)a*i)%mod;

    for(int i=;i<=m;i++) b=((ll)b*i)%mod;

    return ((ll)a*pw(b,mod-))%mod;

}

int main()

{

    scanf("%d%d",&n,&k);

    for(int i=;i<=n;i++)

    {

        int m=n-(i-)*k;

        if(m<i)break;

        ans=((ll)ans+C(m,i))%mod;

    }

    printf("%d",ans%mod);

    return ;

}

巴特西

bzoj3398 [Usaco2009 Feb]Bullcow 牡牛和牝牛——递推 / 组合数

最新文章

热门文章