Memory and Scores

题目描述

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 $10^9+7$. Please solve this problem for Memory.

算法分析

$$f_{i, j} = \sum_{|j-l| \le 2k} (2k+1-|j-l|)f_{i-1, l}$$
$j$的范围是$[-200000, 200000]$，暴力求$f_{i, j}$会超时。

代码

#include <iostream>
#define MOD 1000000007
using namespace std;
long long a, b, k, t, p, now, ans, f, sign;
int main()
{
cin >> a >> b >> k >> t;
sign[a - b + 250000] = 1;
sign[a - b + 250001] = -2;
sign[a - b + 250002] = 1;
for (int i = 0; i <= t; ++i, now ^= 1) {
p = f[now] = 0;
for (int j = 0; j < 500002; ++j) {
p += sign[now][j];
f[now][j] = p;
if (j) f[now][j] += f[now][j - 1];
f[now][j] %= MOD;
if (f[now][j] < 0) f[now][j] += MOD;
if (f[now][j]) {
sign[now ^ 1][j - (k << 1)] += f[now][j];
sign[now ^ 1][j + 1] -= f[now][j] << 1;
sign[now ^ 1][j + (k + 1 << 1)] += f[now][j];
}
sign[now][j] = f[now ^ 1][j] = 0;
}
}
for (int i = 250001; i < 500001; ++i) {
ans += f[now ^ 1][i];
}
cout << ans % MOD << endl;
return 0;
} 418 I'm a teapot