链接: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]
的前缀和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;
}