链接：https://ac.nowcoder.com/acm/problem/111634
来源：牛客网

题目描述 
Memory and his friend Lexa are competing to get higher score in one popular computer game. Memory starts with score a and Lexa starts with score b. In a single turn, both Memory and Lexa get some integer in the range [ - k;k] (i.e. one integer among  - k,  - k + 1,  - k + 2, ...,  - 2,  - 1, 0, 1, 2, ..., k - 1, k) and add them to their current scores. The game has exactly t turns. Memory and Lexa, however, are not good at this game, so they both always get a random integer at their turn.

Memory wonders how many possible games exist such that he ends with a strictly higher score than Lexa. Two games are considered to be different if in at least one turn at least one player gets different score. There are (2k + 1)2t games in total. Since the answer can be very large, you should print it modulo 109 + 7. Please solve this problem for Memory.

输入描述:
The first and only line of input contains the four integers a, b, k, and t (1 ≤ a, b ≤ 100, 1 ≤ k ≤ 1000, 1 ≤ t ≤ 100) — the amount Memory and Lexa start with, the number k, and the number of turns respectively.

输出描述:
Print the number of possible games satisfying the conditions modulo 1 000 000 007 (109 + 7) in one line.

示例1
输入
复制
1 2 2 1
输出
复制
6
示例2
输入
复制
1 1 1 2
输出
复制
31
示例3
输入
复制
2 12 3 1
输出
复制
0
备注:
In the first sample test, Memory starts with 1 and Lexa starts with 2. If Lexa picks  - 2, Memory can pick 0, 1, or 2 to win. If Lexa picks  - 1, Memory can pick 1 or 2 to win. If Lexa picks 0, Memory can pick 2 to win. If Lexa picks 1 or 2, Memory cannot win. Thus, there are 3 + 2 + 1 = 6 possible games in which Memory wins.

算法 动态规划-线性DP

让我们来翻译一下题意： 一个人初始分数是b-a，他一共做2t轮游戏，每一次游戏都从[-k,k]中选取一个数然后自己的分数加上这个数，求这个人在2t轮游戏结束后分数在0以上的方案数

f[i][j]表示第i轮后分数为j的方案数，有 $f[i][j]=f[i-1][j-k]+\mathrm{.}\mathrm{.}\mathrm{.}+f[i-1][j+k]f[i][j]\; =\; f[i-1][j-k]+...+f[i-1][j+k]$ 由于当前层的状态由上一层得出，因此层数这一维我们可以直接省去，（类似于背包的空间优化） 有$f[j]=f[j-k]+\mathrm{.}\mathrm{.}\mathrm{.}+f[j+k]=s[j+k]-s[j-k-1]f[j]\; =\; f[j-k]+...+f[j+k]\; =\; s[j+k]\; -\; s[j-k-1]$ 其中我们每次求出f[i]的前缀和s[i]来加速求和；

此外还有一个问题就是每一次取负数值可能会导致出现负数下标，因此我们给整体加上一个偏移量delta = 2*t*k即可，于是下标0便是对应2tk，整个动态规划数组大小也就要开到21002*1000以上就行了；

#include<unordered_set>
#include<unordered_map>
#include<functional>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<set>
#include<map>

using namespace std;
//================================
#define debug(a) cout << #a": " << a << endl;
#define rep(i, ll,rr) for(int i = ll; i <= rr; ++i)
#define N 410010
const int mod = 1e9+7;
//================================
typedef pair<int,int> pii;
#define x first
#define y second
typedef long long LL; typedef unsigned long long ULL; typedef long double LD;
inline LL read() { LL s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(LL x, int op = 10) { if (!x) { putchar('0'); if (op)  putchar(op); return; }  char F[40]; LL tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op) putchar(op); }
//================================= 
int a,b,k,t;
int delta,f[N],s[N],v;
long long ans=0;

void solve(){
	for(int i=1;i<=2*t;i++){
		s[0] = f[0];
		for(int i=1;i<=delta*2+k;i++) s[i] = (s[i-1]+f[i])%mod;
		for(int i=0;i<=k;i++) f[i] = s[i+k];
		for(int i=k+1;i<=delta*2;i++) f[i] = ((s[i+k] - s[i-k-1])%mod+mod)%mod;
	}
	for(int i=delta-a+b+1;i<=delta*2;i++) ans=(ans+f[i])%mod;
	print(ans);
}

//=================================
int main(){
	a = read(),b = read(),k = read(),t = read();
    v = b-a , delta = 2*k*t , f[delta] = 1 ;
    solve();    
	return 0;
}