首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。