何老板和你玩一个加法计算游戏。 游戏开始，何老板手中有一个整数a，你手中有一个整数b。 每一轮,两人各自都从区间[-k,k]中任意取出一个整数，加到自己手中的数字上。游戏总共进行了t轮。
何老板希望，游戏结束时，他手中的数字比你手中的数字大。 问满足何老板希望的游戏方案数有多少？ 如果两场游戏中，存在一轮，某个玩家取的数字不同，我们就认为这是两场方案不同的游戏。 比如：下面两场游戏，a=5,b=4,t=2，两人最终取得的分数没有变化，但我们认为这是两场不同的游戏。 第一场： 何: 5 3 2 你: 4 2 2 第二场： 何:5 3 2 你:4 1 3
一行，四个整数a,b,k,t 1 ≤ a, b ≤ 100 1 ≤ k ≤ 1000 1 ≤ t ≤ 100
一行，一个整数，表示计算结果。 结果可能很大，mod 1000000007 后再输出
我不会告诉你我这道题光推柿子推了两天。
我也不会告诉你我因为MOD WA了5次。
我更不会告诉你这道题的方程恶心得一批算了不能骂街。
这道题真的恶心毒瘤。/毫无防备地流下了属于真正蒟蒻的眼泪
好了让我们控制一下情绪进入正题。
首先不要看到数据范围就慌，这题复杂度是 O ( t 2 k ) O(t^2k) O(t2k) 的（话说NKOJ评测姬原来这么快的吗）。
看到这道题，显然是按照轮数划分阶段。每轮的状态又如何表示呢？我们可以用何老板和你手中数字的差值来表示。但是这样可能出现何老板手中的数字比你小的情况，所以我们要加上一个偏移量。
于是状态：
设 f [ i ] [ j ] f[i][j] f[i][j] 表示游戏进行i轮后，何老板手中数字比你多j+偏移量的方案数。
状态转移方程很好推：
f [ i ] [ j ] = f[i][j]= f[i][j]= s u m sum sum { f [ i − 1 ] [ j + l ] × ( 2 k − ∣ l ∣ + 1 ) f[i-1][j+l] \times (2k-\vert l\vert + 1) f[i−1][j+l]×(2k−∣l∣+1)} ( − 2 k ≤ l ≤ 2 k ) (-2k \leq l \leq 2k) (−2k≤l≤2k)
为什么要乘 ( 2 t − ∣ l ∣ + 1 ) (2t-\vert l\vert + 1) (2t−∣l∣+1) 呢？这是因为在一轮之内使何老板与你的差值增加 l l l 有 ( 2 k − ∣ l ∣ + 1 ) (2k-\vert l\vert + 1) (2k−∣l∣+1) 种取数方案。
妈妈我做出来这道题了！
看一下时间复杂度这不是 O ( k 2 t 2 ) O(k^2t^2) O(k2t2)吗（j那一维可达 2 k × t 2k \times t 2k×t）。
笑容逐渐消失。
那么我们尝试将原来的式子展开：
f [ i ] [ j ] = f[i][j]= f[i][j]= s u m sum sum { f [ i − 1 ] [ j + l ] × ( 2 k + 1 ) f[i-1][j+l] \times (2k+ 1) f[i−1][j+l]×(2k+1)} - s u m sum sum { f [ i − 1 ] [ j + l ] × ∣ l ∣ f[i-1][j+l] \times \vert l \vert f[i−1][j+l]×∣l∣}
为什么要这么展开呢？因为我们发现后面要乘的系数中 2 k + 1 2k+1 2k+1 是定值！
这不就可以前缀和优化了？
令 s [ i ] [ j ] = ∑ j = 1 j ≤ n f [ i ] s[i][j]=\sum^{j\leq n}_{j=1} f[i] s[i][j]=∑j=1j≤nf[i]。
则 s u m sum sum { f [ i − 1 ] [ j + l ] × ( 2 k + 1 ) f[i-1][j+l] \times (2k+ 1) f[i−1][j+l]×(2k+1)} = ( s [ i ] [ j + l ] − s [ i ] [ j − l − 1 ] ) × ( 2 k + 1 ) =(s[i][j+l]-s[i][j-l-1])\times (2k+1) =(s[i][j+l]−s[i][j−l−1])×(2k+1)
显然我们还有一个变化的系数 ∣ l ∣ \vert l \vert ∣l∣ 没有消去。
于是思来想去，可不可以用计算出的 f [ i ] [ j − 1 ] f[i][j-1] f[i][j−1] 来优化呢？
对于 f [ i ] [ j − 1 ] f[i][j-1] f[i][j−1] 到 f [ i ] [ j ] f[i][j] f[i][j] 的过程，我们可以发现，在这个过程中，对于 f [ i − 1 ] [ k ] f[i-1][k] f[i−1][k]，如果 k > j k>j k>j，则 ∣ j − k ∣ = ∣ j − 1 − k ∣ + 1 \vert j - k \vert = \vert j - 1 - k \vert + 1 ∣j−k∣=∣j−1−k∣+1，反之 k ≤ j k\leq j k≤j, 则 ∣ j − k ∣ + 1 = ∣ j − 1 − k ∣ \vert j - k \vert + 1 = \vert j - 1 - k \vert ∣j−k∣+1=∣j−1−k∣。
综上，可以得出方程：
f [ i ] [ j ] = f [ i ] [ j − 1 ] − ( s [ i − 1 ] [ j − 1 ] − s [ i − 1 ] [ j − k − 2 ] ) + ( s [ i − 1 ] [ j + k ] − s [ i − 1 ] [ j − 1 ] ) f[i][j]=f[i][j-1]-(s[i-1][j-1]-s[i-1][j-k-2])+(s[i-1][j+k]-s[i-1][j-1]) f[i][j]=f[i][j−1]−(s[i−1][j−1]−s[i−1][j−k−2])+(s[i−1][j+k]−s[i−1][j−1]) = f [ i ] [ j − 1 ] + s [ i − 1 ] [ j + k ] + s [ i − 1 ] [ j − k − 2 ] − s [ i − 1 ] [ j − 1 ] × 2 =f[i][j-1]+s[i-1][j+k]+s[i-1][j-k-2]-s[i-1][j-1]\times 2 =f[i][j−1]+s[i−1][j+k]+s[i−1][j−k−2]−s[i−1][j−1]×2
这里不多做解释，自己去推一下，可以说明文字在数学柿子面前是多么无力其实是因为作者太懒以及语文太辣鸡。
最后：
别忘了滚动数组！别忘了取模别忘了+mod再取模！如果你像作者一样懒，不想把取模分成很多步请开long long！（像作者这种懒到极致的人可以define int long long）如果你的写法常数大请注意卡常（对于这道题register是最有效的卡常手段）！接下来就是激动人心的只有20行不到的：
