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