CF1629F1-2 Game on Sum 题解

原题 本题为原比赛T2

Alice 和 Bob 玩 $n$ 回合游戏，初始 $x=0$。

每回合规则：

1. Alice 选择实数 $t\in [0,k]$。

2. Bob 选择 $x\leftarrow x+t$ 或 $x\leftarrow x−t$。

3. 在整个 $n$ 回合中，Bob 必须至少选择 $m$ 次 $x+t$。

Alice 希望最终 $x$ 最大，Bob 希望最终 $x$ 最小。

Bob 在决定之前，会知道 Alice 选择了哪个数字，而 Alice 在选择之前会知道 Bob 在上一轮中是添加还是减去数字（除了第一轮）。双方都采取最优策略。

求最终 $x$ 的值，对 $10^9+7$ 取模。

---

这题比较有意思，来看一下。

因为较先的回合会影响较后的回合，如果先考虑前面的，就要枚举所有较后回合的情况，这样会 T。

所以我们考虑从后往前，长度从小到大 来考虑情况。

1. $len=1$ 时：

显然只有两个情况：

• 如果必须选一个 + ，此时 B 就是全部使用 + 了，因此 A 可以将 $t$ 设置为 $k$。结果 $\triangle x=+k$。

• 如果 B 可以不选 +，显然一定不选 +，那么为了保证较大，A 就会把 $t$ 设置成 0，结果 $\triangle x=0$。

这里我们就可以发现，如果说记录“至少选择 j 个 +”，对于 B 而言，一定不会去使用 $>j$ 个 + 的情况。

这一点是可以被印证的，不会出现“选择 $>j$ 反而会更优”的情况。

2. $len=2$ 时

   三种情况：

   • $j=0$ 或者 $j=len$ 的情况是容易的。

   • $j=1$，下图：

     

     a. 如果本位选择 -，由于没有使用 +，因此下一位必须使用 +，即情况 $len=1,j=1$。

     下一位的 $\triangle x'$ 是算好的，那么本位的 $\triangle x=-t+\triangle x'$。

     b. 如果本位选择 +，由于已经选择 +，因此下一位一定不选 +，即情况 $len=1,j=0$。

     同样得出本位 $\triangle x=t+\triangle x'$。

     那么 B 一定会选择 $\triangle x$ 两者中更小的。

     ---

     那么，考虑对于 A 而言，如何才能有更好的结果？

     由于 a. 的 $\triangle x'$ 大于 b. 的 $\triangle x'$，观察算式，可以得到，其类似于相遇问题。

     为了使 $\min(\triangle x)$ 取值最大，A 就会取两者相等时候的 $t$。

     由于 $\triangle x$ 相等，因此这个东西也可以被记录了。

在我们能维护 $len=1$ 和 $2$ 时的 $\triangle x$ 时，我们可以尝试表达这个东西。

记 $dp_{i,j}$ 表示 $[i,n]$ 这一段还剩下 $j$ 个 + 需要使用，此时这一段会给前面多少 $\triangle x$。

发现在 $i,j$ 确定时，给前面的增加值 $\triangle x$ 是一定的。

我们就可以基于 $len=2$ 尝试得出 $dp_{i,j}$ 的转移方程了：

• 本位选择 -，下一位的 $\triangle x'$ 为 $dp_{i-1,j}$

• 本位选择 +，下一位的 $\triangle x'$ 为 $dp_{i-1,j-1}$

• 两者相等，方程为 $-t+dp_{i-1,j}=t+dp_{i-1,j-1}$。

• 所以

$$dp_{i,j}=\frac{dp_{i-1,j}+dp_{i-1,j-1}}{2}$$

至此我们完成了 Easy Ver. 的代码

ldb dp[maxn][maxn];
void solve(){
	for(int i=n;i>=1;--i){
		int len=n-i+1;
		dp[i][0]=0;
		dp[i][len]=k*len;
		for(int j=1;j<len;++j){
			ldb thisminus=dp[i+1][j],thisplus=dp[i+1][j-1];
			ldb t=(thisminus-thisplus)/2;
			dp[i][j]=t+thisplus;
			//可以从上面导出下面：
			dp[i][j]=(dp[i+1][j]+dp[i+1][j-1])/2;
		}
	}
}
//别抄，用的是double

然后来印证一下不会出现“选择 $>j$ 反而会更优”：

输出发现，在同一长度的情况下，随着 $j$ 的递增，$dp_{i,j}$ 呈现单调不降的趋势。

那么影响 B 更小的因素一定就来源于 $j$ ，所以 B 一定就会选择使用更小 $j$ 的情况，这印证了上面的结论。

（其实挺显然的，如果没有 $j$，B 巴不得把 x 选到 0）

---

观察一下这个玩意，很显然他是一个杨辉三角的变种。

也就是说

$$dp_{i,j}=米奇妙妙\times \sum_{w=0}^{k} \begin{pmatrix} k\\ w\\ \end{pmatrix}\cdot dp_{i-k,j-w}$$

那么这个 米奇妙妙 是什么？每经过一层，所有的值都要 /2。

总共经过 $k$ 层，因此 $米奇妙妙=(2^k)^{-1}$

那么对于不存在的数怎么处理，就像这样：

0	k	(3k)	(5k)	(7k)
0	k/2	2k	(4k)	(6k)
0	k/4	1.25k	3k	(5k)
0	k/8	0.75k	2.125k	4k

发现，在补全之后，第一行的数（除了0）是 $(2i-1)\cdot k$

然后只需要套用公式就完事了。

计算组合数是可以递推的，递推所使用的逆元是可以预处理的。

这样就可以压到 $O(n)$。

// #define DEBG 1
#include<bits/stdc++.h>
#define P (1000000007ll)
using namespace std;
typedef long long ll;
typedef long double ldb;
const int maxn=3e6+35;
const ll inf=1e18;

/*IO*/

ll n,m,k;

inline ll kuaisumi(ll x,ll y){
	ll res=1;
	x%=P;
	while(y){
		if(y&1) res=(res*x)%P;
		x=(x*x)%P;
		y>>=1;
	}
	return res%P;
}
inline ll ne(ll x){return kuaisumi(x,P-2);} //逆元

ll _2[maxn];
inline void calc_2(){
	_2[0]=1;
	for(int i=1;i<maxn;++i){
		_2[i]=_2[i-1]*2%P;
	}
}

ll nne[maxn];
inline void calc_ne(){
	nne[1]=1;
	for(int i=2;i<maxn;++i){
		nne[i]=(P-P/i)*nne[P%i]%P;//这是逆元递推，很好用
	}
}
inline ll Ne(ll x){
	if(x>=maxn) return ne(x);
	else return nne[x];
}
//预处理逆元


ll w[maxn];
ll ans;
void solve(){
	w[0]=0;
	for(int i=1;i<=n;++i){
		w[i]=(i*2-1)*k%P;
	}
	int l=m-n+1,r=m;
	ll C=1;
	for(int i=l,j=0;i<=r;++i,++j){
		// ans+=C(n-1,j)*w[i];
		if(i>=0) ans+=C*w[i]%P,ans%=P;
        //这里需要注意，不存在的i实际上是0，做个特判防止越界
		C=C*Ne(j+1)%P*(n-1-j)%P;//递推组合数
	}
	ans=ans*Ne(_2[n-1])%P;
}

int main(){
	int T=read();
	calc_2();
	calc_ne();
	while(T--){
		n=read();m=read();k=read();
		solve();
		printf("%lld\n",ans);
		ans=0;
	}
	return 0;
}

sub