Game on sum(easy+hard)
pengyule
·
·
题解
博弈论 dp 好题。
博弈论 dp 通常都是从终止态开始往前 dp。
首先还是找关键词——我们用什么刻画一个子游戏——Bob 还剩几个加法要做、游戏（还剩）的轮数。
设 f(i,j) 表示还剩 i 轮，Bob 还剩 j 个加法要做，聪明的 Alice 在这一轮中能把自己引向的最大局面的值。
f(i,j)=\max_{x\in[0,k]}\{\min(f(i-1,j-1)+x,\min(f(i-1,j)-x\}
由于根据常识 f(i-1,j)\ge f(i-1,j-1) 而两者都是定值，所以当且仅当 x=\frac{f(i-1,j)-f(i-1,j-1)}2 时，f(i,j) 取到最大值 \frac{f(i-1,j)+f(i-1,j-1)}2。
当 i=j 时，只能够从 f(i-1,j-1) 转移，并且不难发现 f(i,i)=i\times k。
这个 O(nm) 的 dp 足以解决 Easy Version。
由于 dp 数组的每一个位置都可看作关于 dp 边界值的函数，所以我们考虑每一个 dp 边界值（f(i,i)）对于 f(n,m) 的贡献。
$$f(n,m)=\sum_{i=1}^n\frac {n-i-1\choose m-i}{2^{n-i}}\cdot i\times k$$
```cpp
#include <bits/stdc++.h>
using namespace std;
inline int read(){
register char ch=getchar();register int x=0;
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
const int N=1e6+5,mod=1e9+7,I2=(mod+1)/2;
int n,m,K,jc[N],ijc[N],miI2[N];
int C(int n,int m){return 1ll*jc[n]*ijc[m]%mod*ijc[n-m]%mod;}
void add(int &x,int y){(x+=y)>=mod&&(x-=mod);}
inline int qp(int a,int b){int c=1;for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)c=1ll*c*a%mod;return c;}
void solve(){
n=read(),m=read(),K=read();
jc[0]=ijc[0]=1;for(int i=1;i<=n;i++)jc[i]=1ll*jc[i-1]*i%mod;
ijc[n]=qp(jc[n],mod-2);
for(int i=n-1;i;i--)ijc[i]=1ll*ijc[i+1]*(i+1)%mod;
miI2[0]=1;for(int i=1;i<=n;i++)miI2[i]=1ll*miI2[i-1]*I2%mod;
if(n==m){cout<<1ll*n*K%mod<<'\n';return;}
int ans=0;
for(int i=1;i<=min(m,n-1);i++)add(ans,1ll*C(n-i-1,m-i)*miI2[n-i]%mod*i%mod*K%mod);
cout<<ans<<'\n';
}
int main(){
int T=read();
while(T--)solve();
}
```