CF1628D1 & CF1628D2题解

· · 个人记录

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} 对答案的贡献？

    由 $(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;
}