Part1
神奇的博弈类型 \(Dp\) 。
我们发现与当前状态有关的量，有且只有 现在是第几轮，还有 Bob 用了几次加的操作 ,这都会影响之后的决策，而和之前的决策无关，换句话说，当前决策有后效性，没有前效性。那我们考虑倒着 \(Dp\).
Part2
设 \(f_{i,j}\) 表示还有 \(i\) 轮，且 \(Bob\) 还要用 \(j\) 次加操作，考虑当前选择加操作还是减操作， 如果是加操作，有 \(f_{i,j}=f_{i-1,j-1}+x\), 如果是减操作，有 \(f_{i,j}=f_{i-1,j}-x\), 对于 \(Bob\) 而言，两者取 \(\min\) ,而 \(Alice\) 为了使结果最大，她会改变 \(x\) ，让 \(f_{i-1,j-1}+x=f_{i-1,j}-x\)，解得 $x=\frac{f_{i-1,j}-f_{i-1,j-1}}{2} $ ,那么有转移：
初始状态 \(f_{0,0}=0\), \(f_{i,i}=i*k\)
直接暴力转移，复杂度 \(O(nm)\) ,可以通过 \(Easy\).
Part3
考虑优化，发现对答案相当于每个 \(f_{i,i}\) 的累加，考虑计数。
想象一个平面直角坐标系的第一象限，\(f_{i,i}\) 会对他的右边和右上方产生贡献，那么每个 \(f_{i,i}\) 对答案产生的贡献相当于从 \((i+1,i)\) ，每次走右边或者右上，走到 \((n,m)\) 的方案数，不是 \((i,i)\) 的原因是 \(f_{i,i}\) 不可以对 \(f_{i+1,i+1}\) 产生贡献，相当于第一步只能走右边，而不能走右上。
每次走必定向右走一格，所以一共可以走 \((n-(i+1))\) 步，其中任意选 \((m-i)\) 步改为 右上，所以方案数为 \(\dbinom{n-i-1}{m-i}\)，再除以 \(2^{n-i}\) 。
答案即为：
复杂度 \(O(m)\)。
Code
#include <iostream>
#include <cstdio>
#define int long long
const int N=1e6+10;
const int mod=1e9+7;
using namespace std;
inline int read() {
int f=1, x=0;
char ch=getchar();
while(ch>'9' || ch<'0') {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9') {
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return f*x;
}
inline void write(int x) {
cout<<x; putchar('\n');
}
int T, n, m, k;
int fac[N], inv[N], invj[N], power[N];
void prework() {
fac[0]=fac[1]=inv[0]=inv[1]=invj[0]=invj[1]=1;
for(int i=2;i<=N-5;i++) {
fac[i]=fac[i-1]*i%mod;
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
invj[i]=invj[i-1]*inv[i]%mod;
}
power[0]=1;
for(int i=1;i<=N-5;i++) power[i]=power[i-1]*inv[2]%mod;
}
inline int C(int n,int m) {
if(m>n) return 0;
return fac[n]*invj[m]%mod*invj[n-m]%mod;
}
signed main() {
prework();
T=read();
while(T--) {
n=read(), m=read() ,k=read();
if(n==m) {
write(m*k%mod);
continue;
}
int ans=0;
for(int i=1;i<=m;i++) {
int sum=i*C(n-i-1,m-i)%mod*power[n-i]%mod;
ans=(ans+sum)%mod;
}
write(ans*k%mod);
}
return 0;
}