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;
}