记录编号	307659	评测结果	AAAAAAAAAA
题目名称	[Codeforces 712D] 随机数游戏	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	5.733 s
提交时间	2016-09-15 20:11:49	内存使用	18.62 MiB

#include <fstream>
#include <cmath>
#include <string>
#define N 300010
using namespace std;
typedef long long ll;
ll f[2*N]={0},g[2*N]={0};
ll s[2*N]={0},sum[2*N]={0};
ll mod=(ll)(1e9+7);
int a,b,delta;
int k,t;
ifstream cin("randomgame.in");
ofstream cout("randomgame.out");
void read()
{
	int i,T,l,r;
	cin>>a>>b>>k>>t;
	f[150000]=1;
	for(T=1;T<=t;T++)
	{
		for(i=0;i<=300000;i++)
		{
			if(i==0)s[i]=f[0];
			else s[i]=(s[i-1]+f[i])%mod;
		}
		for(i=0;i<=300000;i++)
		{
			l=max(0,i-k);
			r=min(300000,i+k);
			if(l)g[i]=s[r]-s[l-1];
			else g[i]=s[r];
		}
		for(i=0;i<=300000;i++)f[i]=g[i];
	}
	for(i=1;i<=300000;i++)sum[i]=(sum[i-1]+g[i])%mod;
}
void work()
{
	ll ans=0;
	delta=b-a+1;
	int i;
	//cout<<mod<<endl;
	for(i=0;i<=300000;i++)
	{
		if(i-delta>=0)
		{
			ans=ans+g[i]*sum[i-delta];
			ans%=mod;
		}
	}
	ans=(ans%mod+mod)%mod;
	cout<<ans<<endl;
}
int main()
{
	read();
	work();
	return 0;
}