CF1628D1 Game on Sum (Easy Version) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
个人认为博弈论的板子题。
首先 \(k\) 就是个障眼法。当 \(k\) 变化的时候，Alice 选择的数也按比例变化，这样操作后的 \(x\) 也总会按比例变化（\(x\) 初值为 \(0\)），仍然可以最优。因此只需要计算 Alice 在 \([0, 1]\) 之间选数最后答案乘 \(k\) 即可。
然后又是一个障眼法：Bob 肯定会选择恰好 \(m\) 次让 \(x \gets x + t\)，多选显然在 Bob 的角度上更劣。
博弈论经典倒序 dp，这是因为每个人都聪明绝顶，可以根据接下来的局势判断当前局势做什么更优（而跟之前的局势无关）。
设 \(f(i, j)\) 为游戏还剩 \(i\) 轮，Bob 还能做 \(j\) 次加法时 \(x\) 的值。
接着倒着思考，先思考 Bob 再思考 Alice，因为 Alice 的决策取决于 Bob。
设这一轮 Alice 选择的是 \(t\)。如果 Bob 选择的是加法，答案是 \(f(i - 1, j - 1) + t\)；如果 Bob 选择的是减法，答案是 \(f(i - 1, j) - t\)。
Bob 为了让 \(x\) 尽可能小，会选择两种方案中更小的那种，也就是 \(\min(f(i - 1, j - 1) + t, f(i - 1, j) - t)\)。那么 Bob 就思考完成了。
当然聪明绝顶秃头的 Alice 也思考到了 Bob 的思考。那么她的目标就是让 \(x = \min(f(i - 1, j - 1) + t, f(i - 1, j) - t)\) 最大。
推导可得当且仅当 \(t = \dfrac{f(i - 1, j) - f(i - 1, j - 1)}{2}\) 时，\(x\) 有最大值 \(\dfrac{f(i - 1, j - 1) + f(i - 1, j)}{2}\)。
得到转移方程：\(f(i, j) = \dfrac{f(i - 1, j - 1) + f(i - 1, j)}{2}\)。
边界：\(f(i, 0) = 0\)，\(f(i, i) = i\)。前面那种 Alice 每次只能选 \(0\)，不然 Bob 就能把他减成负数；后面那种就是 Alice 欺负 Bob，每次都选 \(1\)，反正 Bob 不能减。
多组询问，先预处理然后 \(\mathcal{O}(1)\) 回答即可。
时间复杂度 \(\mathcal{O}(nm + q)\)。
/*
* @Author: crab-in-the-northeast
* @Date: 2022-10-17 02:13:13
* @Last Modified by: crab-in-the-northeast
* @Last Modified time: 2022-10-17 02:20:25
*/
#include <bits/stdc++.h>
#define int long long
inline int read() {
int x = 0;
bool flag = true;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
flag = false;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
if(flag)
return x;
return ~(x - 1);
}
const int mod = (int)1e9 + 7, in2 = (int)5e8 + 4;
const int maxn = 2005, maxm = 2005;
int f[maxn][maxm];
signed main() {
for (int i = 1; i <= 2000; ++i)
f[i][i] = i;
for (int i = 2; i <= 2000; ++i)
for (int j = 1; j < i; ++j)
f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % mod * in2 % mod;
int q = read();
while (q--) {
int n = read(), m = read(), k = read();
printf("%lld\n", f[n][m] * k % mod);
}
return 0;
}