洛谷P5299 [PKUWC2018]Slay the Spire 题解

题目链接：P5299 [PKUWC2018]Slay the Spire

题意：

九条可怜在玩一个很好玩的策略游戏：Slay the Spire，一开始九条可怜的卡组里有 \(2n\) 张牌，每张牌上都写着一个数字\(w_i\)，一共有两种类型的牌，每种类型各 \(n\) 张：

攻击牌：打出后对对方造成等于牌上的数字的伤害。

强化牌：打出后，假设该强化牌上的数字为 \(x\)，则其他剩下的攻击牌的数字都会乘上 \(x\)。

保证强化牌上的数字都大于 1。

现在九条可怜会等概率随机从卡组中抽出 \(m\) 张牌，由于费用限制，九条可怜最多打出 \(k\) 张牌，假设九条可怜永远都会采取能造成最多伤害的策略，求她期望造成多少伤害。

假设答案为 \(\text{ans}\) ，你只需要输出

\[ \left (\text{ans}\times \frac{(2n)!}{m!(2n-m)!}\right) ~\bmod 998244353 \] 即可。其中 \(x!\) 表示 \(\prod_{i=1}^{x}i\)，特别地，\(0!=1\) 。

输入格式：

第一行一个正整数 \(T\) 表示数据组数

接下来对于每组数据：

第一行三个正整数 \(n,m,k\) 。

第二行 \(n\) 个正整数 \(w_i\)，表示每张强化牌上的数值。

第三行 \(n\) 个正整数 \(w_i\)，表示每张攻击牌上的数值。

输出格式：

输出 \(T\) 行，每行一个非负整数表示每组数据的答案。

数据范围：

对于所有数据，有 \(1\leq k\leq m\leq 2n\leq 3\times 10^3,~1\leq \sum 2n\leq 3000\)，且 \(1\leq w_i\leq 10^8\) 。

首先考虑最优出牌策略是什么。

记 \(a_i\) 为强化牌，\(b_i\) 为攻击牌，并且从大到小排序。

根据贪心的套路，考虑什么时候会用强化牌来替换攻击牌。

设某个策略中使用了 \(x\) 张强化牌，\(y\) 张攻击牌。

我们将第 \(y\) 张攻击牌（也就是最小的那张）换成第 \(x+1\) 张强化牌。

如果和原先的策略比没有变劣，则 \[ \prod_{i=1}^x a_i \times \sum_{i=1}^y b_i \le \prod_{i=1}^{x+1} a_i \times \sum_{i=1}^{y-1} b_i \] 移项整理得 \[ \left(a_{x+1}-1\right) \times\left(\prod_{i=1}^x a_i \times \sum_{i=1}^{y-1} b_i\right) \geq\left(\prod_{i=1}^x a_i\right) \times b_y \] 等式两侧除以 \(\prod_{i=1}^{x}a_i\) ，得 \[ \left(a_{x+1}-1\right) \times\left(\sum_{i=1}^{y-1} b_i\right) \geq b_y \] 由于题目中保证强化牌上的数字都大于 1，因此 \[ a_{x+1}-1 \ge 1 \] 又因为 \(y>1\) 时 \(b_i\) 从大到小排序过了，所以 \(\sum_{i=1}^{y-1} b_i\) 大于等于 \(b_y\) 恒成立。

因此在至少有一张攻击牌时，一定优先选择强化牌。

接下来我们就可以开始dp了。状态设计的思路来源于计算答案的部分。

设

\(f_{i,j,0}\) 表示在前 \(i\) 张强化牌中选择 \(j\) 张，且第 \(i\) 张被选中的所有情况中，这 \(j\) 张牌的乘积之和。
\(g_{i,j,0}\) 表示在前 \(i\) 张攻击牌中选择 \(j\) 张，且第 \(i\) 张被选中的所有情况中，这 \(j\) 张牌的和之和。
\(f_{i,j,1}\) 定义为 \(\sum_{t=1}^i f_{t, j, 0}\) ，前缀和优化。
\(g_{i,j,1}\) 定义为 \(\sum_{t=1}^i g_{t, j, 0}\) ，前缀和优化。

考虑转移，这个还算比较简单 \[ \begin{gathered} f_{i, j, 0}=a_i \times f_{i-1, j-1,1} \\[6pt]f_{i, j, 1}=f_{i, j, 0}+f_{i-1, j, 1} \\[6pt]g_{i, j, 0}=b_i \times \dbinom{i-1}{j-1}+g_{i-1, j-1,1} \\[6pt]g_{i, j, 1}=g_{i, j, 0}+g_{i-1, j, 1} \end{gathered} \] 第一、三行可能比较难理解，因为这里表示的是所有情况的和

第一行，每个和都会乘上 \(a_i\) ，根据乘法分配律，就等价于原来所有的和乘以 \(a_i\) 。

第三行，这里的乘法是因为 \(\binom{i-1}{j-1}\) 种选攻击牌的方案，每种都加上了权值 \(b_i\) ，因此一共加上了 \(b_i \times \binom{i-1}{j-1}\) 。

~~有了这些奇奇怪怪的dp式子后有啥用呢？~~

考虑统计答案，需要分类讨论（因为策略不同）。

第一种情况： \(m\) 张牌中强化牌的数量小于 \(k-1\) 张。

此时比较好处理，可以把所有强化牌都拿上，然后选较大的那些攻击牌就好了。

不难发现其实等于 \(k-1\) 的也是满足的，但是其实在另一类中可以方便一些。

我们枚举 \(i,j\) ，分别表示强化牌有 \(i\) 张以及最后被选中的攻击牌是第 \(j\) 张。

在强化牌中选择 \(i\) 张的所有合法情况的乘积之和，根据定义就是 \(f_{n,i,1}\) 。

在攻击牌中选剩下的 \(k-i\) 张，且最后一张一定是第 \(j\) 张的所有合法情况的和之和，根据定义就是 \(g_{j,k-i,0}\) 。

同时我们需要满足剩下的 \(m-k\) 张牌

没有强化牌，否则不满足假设
所有攻击牌都在第 \(j\) 张之后，否则不是最优策略

故方案数为 \(\binom{n-j}{m-k}\times\binom{n-i}{0} = \binom{n-j}{m-k}\) 。

因此对于每个 \((i,j)\) ，贡献为 \[ f_{n,i,1}\times g_{j,k-i,0} \times \binom{n-j}{m-k} \] 第二种情况：\(m\) 张牌中，强化牌的数量大于等于 \(k-1\) 。

此时必然是选择最大的 \(k-1\) 张强化牌，然后选极大的那张攻击牌。

对于这种情况，我们枚举 \(i,j\) ，分别表示最后被选中的强化牌是第 \(i\) 张，且选中的攻击牌是第 \(j\) 张。

在前 \(i\) 张强化牌中选择 \(k-1\) 张，且第 \(i\) 张必须选，所有合法情况下的乘积之和，即 \(f_{i,k-1,0}\) 。

选择第 \(j\) 张攻击牌，则攻击牌之和就是 \(b_j\) 。

同时我们需要满足剩下的 \(m-k\) 张牌

所有强化牌都在第 \(i\) 张之后
所有攻击牌都在第 \(j\) 张之后

故方案数为 \(\binom{2n-i-j}{m-k}\) 。

因此对于每个 \((i,j)\) ，贡献为 \[ f_{i,k-1,0} \times b_j \times \dbinom{2n-i-j}{m-k} \] 时间复杂度 \(\mathcal{O}(Qn^2)\) ，有点卡常

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
const ll mod = 998244353;
#define mul3(a,b,c) ( (a) % mod * (b) % mod * (c) % mod )
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x,int y) { (x += y) >= mod ? x-=mod : 0; }
int Add(int x,int y) { return ((x+=y) >= mod) ? (x-=mod) : x; }
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
    template<typename T>void print(T k) { write(k); pc('\n'); }
}using namespace FastIO;
#define N ((int)(3e3+15))

int n,m,k,Q,res,a[N],b[N],C[N][N],f[N][N][2],g[N][N][2];
void init()
{
    C[0][0] = 1;
    for(int i=1; i<=N-5; i++)
    {
        C[i][0] = 1;
        for(int j=1; j<=i; j++)
            C[i][j] = Add(C[i-1][j-1], C[i-1][j]);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    init(); for(read(Q); Q--; res = 0)
    {
        read(n); read(m); read(k);
        for(int i=1; i<=n; i++) read(a[i]); sort(a+1, a+1+n, greater<int>());
        for(int i=1; i<=n; i++) read(b[i]); sort(b+1, b+1+n, greater<int>());
        f[0][0][0] = f[0][0][1] = 1;
        for(int i=1; i<=n; i++)
        {
            f[i][0][1] = 1;
            for(int j=1; j<=i; j++)
            {
                f[i][j][0] = (ll)a[i] * f[i-1][j-1][1] % mod;
                f[i][j][1] = Add(f[i][j][0], f[i-1][j][1]);
                g[i][j][0] = Add((ll)b[i] * C[i-1][j-1] % mod, g[i-1][j-1][1]);
                g[i][j][1] = Add(g[i][j][0], g[i-1][j][1]);
            }
        }
        for(int i=0; i < k-1; i++)
            for(int j=1; j<=n; j++)
                add(res, mul3(f[n][i][1], g[j][k - i][0], C[n - j][m - k]));
        for(int i=0; i<=n; i++)
            for(int j=1; j<=n; j++)
                add(res, mul3(f[i][k-1][0], b[j], C[2*n - i - j][m - k]));
        print(res);
    }
    return 0;
}