我们不难发现，假设抽了x张攻击牌，y张强化牌，那么肯定是打出尽可能多张的强化牌后，再开始出攻击牌（当然最少要一张攻击牌）

我们设G(i,j)表示：所有（抽到的攻击牌牌数为i，打出的攻击牌牌数为j）的方案，所产生的攻击值的总和

形式化地说：​$G(i,j)=\sum\limits_{S∈攻击牌\and|S|=i}S中前j大的牌的攻击值之和$

考虑到G(i,j)难以一次求出，我们考虑设置一些中间变量

设g[i][j]表示：我们对攻击牌从小大大进行排序，目前选了i张牌，其中最小的牌是第j张的总贡献，其中b[j]表示第j小的牌的攻击值

当i=1时，有$g[i][j]=b[j]$

当i>1时，有$g[i][j]=b[j]\times \binom{n-j+1}{i}+\sum\limits_{k=j+1}^{n} g[i-1][k]$

后面那个$\sum$我们可以通过求前缀和，实现快速求解

考虑如何通过g(i,j)求解G(i,j)

不难推出：$G(i,j)=\sum\limits_{k=1}^{n-j+1} g[i][k]$

我们设F(i,j)表示：所有（抽到的强化牌牌数为i，打出的强化牌数为j）的方案里，每一个方案所产生的贡献（抽到的i张牌中，最大的j张牌之积）的和

形式化地说：$F(i,j)=\sum\limits_{S∈强化牌\and|S|=i}S中前j大的牌的强化值之积$

考虑到F(i,j)难以一次求出，我们考虑设置一些中间变量

设f[i][j]表示：我们对强化牌从小大大进行排序，目前选了i张牌，其中最小的牌是第j张的总贡献，其中a[j]表示第j小的牌的攻击值

当i=1时，有$f[i][j]=a[j]$

当i>1时，有$f[i][j]=a[j]\times \sum\limits_{k=j+1}^{n} f[i-1][k]$

后面那个$\sum$我们可以通过求前缀和，实现快速求解

考虑如何通过f(i,j)求解F(i,j)

不难推出：$F(i,j)=\sum\limits_{k=1}^{n-j+1} f[i][k]$

最后我们要求的答案ans，假设当前，我们抽到的强化牌数量为i

若i<k，则$ans+=F(i,i)\times G(m-i,k-i)$

若i≥k，则$ans+=F(i,k-1)\times G(m-i,1)$

完结撒花~

1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6 typedef long long ll;
7 const int mod=998244353;
8 int T, n, m, k, a[1505], b[1505], c[3005][3005], f[1505][1505];
9 int g[1505][1505], sum[1505];
10 int F(int x, int y){
11 if(x>T;
28 for(int i=0; i<=3000; i++){
29 c[i][0] = 1;
30 for(int j=1; j<=i; j++)
31 c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod;
32 }
33 while(T--){
34 memset(f, 0, sizeof(f));
35 memset(g, 0, sizeof(g));
36 scanf("%d %d %d", &n, &m, &k);
37 for(int i=1; i<=n; i++) scanf("%d", &a[i]);
38 for(int i=1; i<=n; i++) scanf("%d", &b[i]);
39 sort(a+1, a+1+n);//跟牌的顺序无关，可以sort
40 sort(b+1, b+1+n);
41 for(int i=1; i<=n; i++){
42 f[1][i] = a[i];//初始化f[][]，显然只选1张的倍率之和是a[i]
43 sum[i] = (sum[i-1] + a[i]) % mod;//前缀和，方便转移
44 }
45 for(int i=2; i<=n; i++){
46 for(int j=1; j<=n-i+1; j++)
47 f[i][j] = (ll)a[j] * (sum[n]-sum[j]+mod) % mod;
48 //打了i张牌，最前头的是第j张，那它就是f[i-1][j+1..n]的和再乘上第j号元素。这个转移的思想是枚举在打了i-1张牌的时候最前头的是哪一张
49 for(int j=1; j<=n; j++)
50 sum[j] = (sum[j-1] + f[i][j]) % mod;
51 }
52 for(int i=1; i<=n; i++){
53 g[1][i] = b[i];
54 sum[i] = (sum[i-1] + b[i]) % mod;
55 }
56 for(int i=2; i<=n; i++){
57 for(int j=1; j<=n-i+1; j++)
58 g[i][j] = ((ll)b[j]*c[n-j][i-1]%mod+(sum[n]-sum[j]+mod)%mod) % mod;
59 //打了i张牌，最前头的是第j张。注意g代表的是（不加强化的）攻击力和。在这种情况下，打了i-1张牌的总情况是c[n-j][i-1]种（j+1..n中选i-1个的方案数），这是第一项；第二项就是继承自g[i-1][j+1..n]
60 for(int j=1; j<=n; j++)
61 sum[j] = (sum[j-1] + g[i][j]) % mod;
62 }
63 int ans=0;
64 for(int i=0; i<m; i++)
65 if(i<k) ans = (ans + (ll)F(i,i)*G(m-i,k-i)%mod) % mod;
66 else ans = (ans + (ll)F(i,k-1)*G(m-i,1)%mod) % mod;
67 printf("%d\n", ans);
68 }
69 return 0;
70 }