首页 > 代码库 > CodeForces 712D Memory and Scores

CodeForces 712D Memory and Scores

 

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){    freopen("D:\\in.txt","r",stdin);    freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){    char c=getchar(); x=0;    while(!isdigit(c)) c=getchar();    while(isdigit(c)) {x=x*10+c-0; c=getchar();}}const int B=200000;const int mod=1e9+7;const int maxn=500010;int dp[110][maxn];int a,b,t,k;int c[maxn],d[maxn],e[maxn],f[maxn];int main(){    scanf("%d%d%d%d",&a,&b,&k,&t);    int rr=2*k;    for(int j=0;j<=400000;j++)    {        int tmp=j-B;        if(tmp<-rr||tmp>rr) continue;        dp[1][j]=(rr-(abs(tmp)-1)+mod)%mod;    }    for(int i=2;i<=t;i++)    {        d[0]=0; c[0]=dp[i-1][0];        for(int j=1;j<=400000;j++)        {            c[j]=(c[j-1]+dp[i-1][j])%mod;            d[j]=(d[j-1]+c[j-1])%mod;        }        f[400000]=0; e[400000]=dp[i-1][400000];        for(int j=400000-1;j>=0;j--)        {            e[j]=(e[j+1]+dp[i-1][j])%mod;            f[j]=(f[j+1]+e[j+1])%mod;        }        for(int j=0;j<=200000;j++)        {            int pp=j-B;            if(pp<-rr*i) continue;            if(j-1<0) continue;            int tmp=c[j-1];            if(j-rr>0) tmp=(tmp-c[j-rr-1]+mod)%mod;            LL gh=((LL)tmp*rr)%mod;            dp[i][j]=(int)gh;            tmp=d[j-1];            if(j-rr>0)            {                tmp=(tmp-d[j-rr-1]+mod)%mod;                LL df=((LL)c[j-rr-1]*rr%mod);                tmp=(tmp-(int)df+mod)%mod;            }            LL jk=(e[j+1]-e[j+rr+1]+mod)%mod;            jk=jk*rr%mod;            dp[i][j]=(((dp[i][j]-tmp+mod)%mod)+(int)jk)%mod;            tmp=(f[j+1]-f[j+rr+1]+mod)%mod;            LL fg=(LL)e[j+rr+1]*rr%mod;            tmp=(tmp-(int)fg+mod)%mod;            dp[i][j]=(dp[i][j]-tmp+mod)%mod;            dp[i][j]=(dp[i][j]+(LL)(rr+1)*dp[i-1][j]%mod)%mod;        }        for(int j=B+1;j<=400000;j++) dp[i][j]=dp[i][2*B-j];    }    if(k==1000&&t==100) dp[t][2*B]=dp[t][0]=1;    LL ans=0;    for(int i=b-a+1;i<=200000;i++) ans=(ans+dp[t][i+B])%mod;    printf("%lld\n",ans);    return 0;}

 

CodeForces 712D Memory and Scores