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.

题意概述

给定$a, b$和$k$，进行$t$次$a+=rand_{-k, k}, \ b+=rand_{-k, k}$，其中$rand_{i, j}$表示区间$[i, j]$中的随机整数。求最终$a \gt b$的方案数。

数据范围：$1 \le a, b \le 100, \ 1 \le k \le 1000, \ 1 \le t \le 100$。

算法分析

令$f_{i, j}$表示第$i$轮两人分数相差$j$的方案数。显然，每一轮两人分数之差增加$t \ (|t| \le 2k)$的方案数为$2k+1-|t|$。

容易写出 DP 方程

$$
f_{i, j} = \sum_{|j-l| \le 2k} (2k+1-|j-l|)f_{i-1, l}
$$

$j$的范围是$[-200000, 200000]$，暴力求$f_{i, j}$会超时。

考虑到$f_{i, j}$对$f_{i+1, j-2k}, f_{i+1, j-2k+1}, f_{i+1, j-2k+2}, …, f_{i+1, j-1}, f_{i+1, j}$以及$f_{i+1, j+1}, f_{i+1, j+2}, f_{i+1, j+3}, …, f_{i+1, j+2k-1}, f_{i+1, j+2k}$的贡献都是等差数列，因此 DP 时可以用前缀和优化，在$f_{i+1, j-2k}, f_{i+1, j+2k+2}$打上$+f_{i, j}$的标记，在$f_{i+1, j+1}$打上$-2f_{i, j}$的标记。

开满数组会导致 MLE，需要滚动数组。

代码

#include <iostream>
#define MOD 1000000007
using namespace std;
long long a, b, k, t, p, now, ans, f[2][500002], sign[2][500002];
int main()
{
    cin >> a >> b >> k >> t;
    sign[0][a - b + 250000] = 1;
    sign[0][a - b + 250001] = -2;
    sign[0][a - b + 250002] = 1;
    for (int i = 0; i <= t; ++i, now ^= 1) {
        p = f[now][0] = 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;
}