题目传送门 (Easy Version) | 题目传送门 (Hard Version)
前置知识
解法
CF1628D1 Game on Sum (Easy Version)
设 \(x_{i}\) 表示第 \(i\) 轮时 Alice 选择的数。
设 \(f_{i,j}\) 表示已经进行了 \(i\) 轮，且使用了 \(j\) 次加法时的最大得分，状态转移方程为 \(f_{i,j}= \max \{ \min(f_{i-1,j}-x_{i},f_{i-1,j-1}+x_{i}) \}=\frac{f_{i-1,j}+f_{i-1,j-1}}{2}\)，边界为 \(\begin{cases} f_{i,0 \sim \infty}=0 & i=0 \\ f_{i,0}=0, f_{i,i}=i \times k & i \ne 0 \end{cases}\)。
- 由于
Bob想让结果尽可能小，所以有 \(f_{i,j}= \min(f_{i-1,j}-x_{i},f_{i-1,j-1}+x_{i})\)。 - 由于
Alice想让结果尽可能大，所以会让 \(\min(f_{i-1,j}-x_{i},f_{i-1,j-1}+x_{i})\) 取到最大值，即 \(f_{i-1,j}-x_{i}=f_{i-1,j-1}+x_{i}\) 时，解得 \(x_{i}= \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}\)。
由于 Bob 想让结果尽可能小，所以至多使用 \(m\) 次加法，故最终 \(f_{n,m}\) 即为所求。
另外，由于求解 \(f_{n,m}\) 的过程中只有加法和 \(\times \frac{1}{2}\) 运算，故可以将 \(k\) 缩小至 \(1\) 进行预处理 \(f_{n,m}\)，询问时再扩大到 \(k\)，即 \(f_{n,m} \times k\)。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
const ll p=1000000007;
ll f[2010][2010];
ll qpow(ll a,ll b,ll p)
{
ll ans=1;
while(b>0)
{
if(b&1)
{
ans=ans*a%p;
}
b>>=1;
a=a*a%p;
}
return ans;
}
int main()
{
ll t,n,m,k,i,j;
cin>>t;
for(i=1;i<=2000;i++)
{
f[i][0]=0;
f[i][i]=i;
for(j=1;j<=i-1;j++)
{
f[i][j]=((f[i-1][j]+f[i-1][j-1])%p)*qpow(2,p-2,p)%p;
}
}
for(i=1;i<=t;i++)
{
cin>>n>>m>>k;
cout<<f[n][m]*k%p<<endl;
}
return 0;
}
CF1628D2 Game on Sum (Hard Version)
观察到 \(f\) 的转移过程比较像杨辉三角的转移过程。
当 \(n=m\) 时，有 \(f_{n,m}=m \times k\) 即为所求。
当 \(n \ne m\) 时，
- 考虑计算 \(f_{i,i}\) 对 \(f_{n,m}\) 产生的贡献。
- 从 \(f_{i,i}\) 到 \(f_{n,m}\) 一共进行了 \(n-i\) 次 \(\times \frac{1}{2}\) 操作。
- 由 \(f_{i,j}\) 会向 \(f_{i+1,j}\) 和 \(f_{i+1,j+1}\) 进行转移，故等价于 \((i,j)\) 一次可以走到 \((i+1,j)\) 或 \((i+1,j+1)\)，求不经过形如 \((x,x)\) 的点时从 \((i,i)\) 走到 \((n,m)\) 的方案数，即从 \((i+1,i)\) 走到 \((n,m)\) 的方案数 \(\dbinom{n-(i+1)}{m-i}\)。
- 故 \(\sum\limits_{i=1}^{m}\frac{i \times k \times \binom{n-(i+1)}{m-i}}{2^{n-i}}\) 即为所求。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
const ll p=1000000007;
ll jc[2000010],inv[2000010],jc_inv[2000010],a[2000010];
ll qpow(ll a,ll b,ll p)
{
ll ans=1;
while(b>0)
{
if(b&1)
{
ans=ans*a%p;
}
b>>=1;
a=a*a%p;
}
return ans;
}
ll C(ll n,ll m,ll p)
{
return (n>=m&&n>=0&&m>=0)?(jc[n]*jc_inv[m]%p)*jc_inv[n-m]%p:0;
}
int main()
{
ll t,n,m,k,ans=0,i,j;
cin>>t;
jc[0]=jc_inv[0]=1;
for(i=1;i<=1000000;i++)
{
a[i]=i;
jc[i]=jc[i-1]*a[i]%p;
}
for(i=1000001;i<=2000000;i++)
{
a[i]=qpow(2,i-1000000-1,p);
jc[i]=jc[i-1]*a[i]%p;
}
jc_inv[2000000]=qpow(jc[2000000],p-2,p);
for(i=2000000-1;i>=1;i--)
{
jc_inv[i]=jc_inv[i+1]*a[i+1]%p;
}
for(i=1;i<=2000000;i++)
{
inv[i]=jc_inv[i]*jc[i-1]%p;
}
for(i=1;i<=t;i++)
{
cin>>n>>m>>k;
ans=0;
if(n==m)
{
cout<<m*k%p<<endl;
}
else
{
for(j=1;j<=m;j++)
{
ans=(ans+((j*k%p)*C(n-(j+1),m-j,p)%p)*inv[1000000+1+n-j]%p)%p;
}
cout<<ans<<endl;
}
}
return 0;
}