本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-04-10 08:18:55

CF1628D1:

CF1628D1 是这道题的简化版，唯一的不同是数据范围，之后的结论要使用这道题的方法。

想一想这道题的思路，贪心不太可行，因为双方都会选最优方案，双方不可能以贪心的方式来决策，但是如果用 dp 的话可以确保双方都选择了最优方案。

那如何 dp 呢？

1. 设状态 $f_{i,j}$ 表示第 $i$ 轮游戏时，Bob 要选 $j$ 次加的情况下的 $x$
2. Bob 的决策：设当前为第 $i$ 轮游戏，Bob 要选 $j$ 次加。如果这一轮 Bob 不选加，那么答案就是 $f_{i-1,j} -t$，如果这一轮 Bob 选加，那么答案就是 $f_{i-1,j-1}+t$，Bob 肯定会选两个答案中最小的，那么 $f_{i,j}=min(f_{i-1,j}-t,f_{i-1,j-1}+t)$
3. Alice 的决策：因为 $f_{i,j}=min(f_{i-1,j}-t,f_{i-1,j-1}+t)$，所以她需要使 $min(f_{i-1,j}-t,f_{i-1,j-1}+t)$ 尽量大。显然，Alice应当让 $min(f_{i-1,j}-t,f_{i-1,j-1}+t)$ 等于两个数的平均值，显然只有这时候两个数的 min 最大。所以她会让 $t$ 等于 $f_{i-1,j}$ 和 $f_{i-1,j-1}$ 之差的平均值，这样 $min(f_{i-1,j}-t,f_{i-1,j-1}+t) = \frac{f_{i-1,j}-t,f_{i-1,j-1}+t}{2}$ 。
   4.最终的转移方程：$f_{i,j} = \frac{f_{i-1,j}-t,f_{i-1,j-1}+t}{2}$，另外，边界条件：$f_{i,0} = 0,f_{i,i} = i \cdot k$
   当 $n=m$ 时，答案为 $k \cdot n$
   注意：
   因为要取模，所以除以 2 时，应当乘上 2 在模 1e9+7 意义下的逆元，这个逆元用 exgcd 可以轻松求出。这里把我用 exgcd 求出的逆元贴出来：500000004

CF1628D1 的 AC 代码：

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    const ll mod=1e9+7;
    int t;
    const int maxn = 2005;
    ll inv;
    ll f[maxn][maxn];
    int n,m,k;
    inline int read()
    {
        int x = 0, f = 1;
        char ch = getchar();
        while (!isdigit(ch))
        {
            if (ch == '-')
                f = -1;
            ch = getchar();
        }
        while (isdigit(ch))
        {
            x = (x << 1) + (x << 3) + (ch ^ 48);
            ch = getchar();
        }
        return x * f;
    }
    void write(int x)
    {
        if(x<0)
        {
            x=-x;
            putchar('-');
        }
        if(x>=10)write(x\/10);
        putchar(x%10^48);
    }
    int x,y;
    void exgcd(int a,int b)
    {
        if(b==0)
        {
            x=1;
            y=0;
            return;
        }
        exgcd(b,a%b);
        int tmp=x;
        x=y;
        y=tmp-a\/b*y;
    }
    inline void solve()
    {
        n=read();
        m=read();
        k=read();
        for(int i=1;i<=n;i++)
        {
            f[i][0]=0;
            f[i][i]=(ll)i*(ll)k;
            f[i][i]=f[i][i]%mod;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<i;j++)
            {
                f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod*inv%mod;
            }
        }
        write((int)f[n][m]);
        putchar('\n');
    }
    void main()
    {
        exgcd(2,mod);
        inv=(x%mod+mod)%mod;
        t=read();
        while(t--)
        {
            solve();
        }
        #ifndef ONLINE_JUDGE
        system("pause");
        #endif
    }
}
int main()
{
    Main::main();
    return 0;
}

CF1628D2:

这道题与上一道题唯一的区别是数据范围扩大了，不能再 $O(nm)$ dp 了。
可以发现最终的答案都是从直接或间接从 $f_{i,i}$ 转移过去的，所以是不是可以只考虑 $f_{i,i}$ 对答案的贡献？
$f_{i,i}$ 的贡献可以想到，就是由 $(i,i)$ 走到 $(n,m)$ 的路径数( 从任意一点 $(i,j)$ 只能走到 $(i+1,j)$ 或 $(i+1,j+1)$)，再乘上每条路径产生的贡献。
由 $(i,i)$ 走到 $(n,m)$ 的路径数就是从 $n-i-1$ 条向上走的路径中选择 $m-i$ 条路径既向上走又向右走，也就是 $C_{n-i-1}^{m-i}$。$(i,i)$ 的初始值为 $i \cdot k$，路径中每走一个点，就会将其贡献除以 2，一共会除以 $n-i$ 次 2，也就是除以 $2^{n-i}$。
所以，答案就是 $\sum_{i=1}^m \frac{C_{n-i-1}^{m-i} \cdot i \cdot k}{2^{n-i}}$
快速幂和组合数肯定都会写，不说了。

CF1628D2 的 AC 代码：

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    const ll mod=1e9+7;
    int t;
    const int maxn = 1e6+5;
    ll n,m,k;
    inline ll ksm(ll a,ll b,ll p)
    {
        ll ret=1;
        while(b)
        {
            if(b&1)ret=ret*a%p;
            a=a*a%p;
            b>>=1;
        }
        return ret;
    }
    inline ll ny(ll a,ll p)
    {
        return ksm(a,p-2,p);
    }
    
    ll fact[maxn];
    inline ll C(ll n,ll m)
    {
        if(n<m)return 0;
        return fact[n]*ny(fact[m],mod)%mod*ny(fact[n-m],mod)%mod;
    }
    inline void solve()
    {
        scanf("%lld%lld%lld",&n,&m,&k);
        ll ans=0;
        if(n==m)
        {
            printf("%lld\n",k*n%mod);
            return;
        }
        for(ll i=1;i<=m;i++)
        {
            ans+=k*i%mod*C(n-i-1,m-i)%mod*ny(ksm(2,n-i,mod),mod)%mod;
            ans%=mod;
        }
        printf("%lld\n",ans);
    }
    void main()
    {
        fact[0]=1;
        for(int i=1;i<=1000000;i++)
        {
            fact[i]=fact[i-1]*(ll)i;
            fact[i]%=mod;
        }
        scanf("%d",&t);
        while(t--)
        {
            solve();
        }
        #ifndef ONLINE_JUDGE
        system("pause");
        #endif
    }
}
int main()
{
    Main::main();
    return 0;
}