题解 CF712D 【Memory and Scores】

lhjy666 · 2018-12-25 14:09:27 · 题解

不说了，直接上代码

#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
ll f[1000005],s[1000005];
int main()
{
    ll a,b,k,t,ans=0;
    scanf("%lld%lld%lld%lld",&a,&b,&k,&t);
    f[0]=1;
    for (ll i=0;i<=2*k*t;i++)
    {
        s[i]=1;
    }
    for (ll i=1;i<=t;i++)
    {
        for (ll j=0;j<=2*k*t;j++)
        {
            if(j<=2*k)
            {
                f[j]=s[j];
            }
            else
            {
                f[j]=(s[j]-s[j-2*k-1]+mod)%mod;
            }
        }
        s[0]=f[0];
        for (ll j=1;j<=2*k*t+10000;j++)
        {
            s[j]=s[j-1]+f[j];
            s[j]=s[j]%mod;
        }
    }
    for (ll i=(b-a+1)*(b+1>a);i<=2*k*t;i++)
    {
        ans=(ans+s[i-(b-a+1)]*f[i])%mod;
    }
    printf("%lld",ans);
    return 0;
}