Loj 2538 Slay the Spire

Posted on | Views:

贪心 + dp 计数.

首先,对于给定 $m$ 张牌,由于强化牌的值都 $>1$ ,所以我们可以贪心制定以下打牌策略:

  • 若没有攻击牌,则无论怎么打,伤害值都是 $0$ .

  • 若强化牌 $<k$ 张,则先打出所有强化牌,再从大到小打出攻击牌,直到一共打出 $k$ 张.

  • 若强化牌 $\ge k$ 张,则先从大到小打出 $k-1$ 张强化牌,再打出一张最大的攻击牌.

设 $F(i,j)$ 表示抽了 $i$ 张强化牌,按最优策略打出 $j$ 张时每种方案权值乘积之和.

设 $G(i,j)$ 表示抽了 $i$ 张攻击牌,按最优策略打出 $j$ 张时每种方案权值总和之和.

强化牌 $<k$ 张的情况贡献就是 $\sum F(i,i)\cdot G(m-i,k-i)$ .

强化牌 $\ge k$ 张的情况贡献就是 $\sum F(i,k-1)\cdot G(m-i,1)$ .

只需要考虑 $F,G$ 怎么求.

设 $f(i,j)$ 表示打了 $i$ 张强化牌,权值最小的强化牌是第 $j$ 张的贡献总和,即可求出 $F$ , $G$ 的求法同理.

时间复杂度 $O(n^2)$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	print(x);
	putchar(c);
}
const int P = 998244353;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
int mul(int a, int b)
{	
	return 1LL * a * b % P;
}
int fpow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}
const int N = 3e3 + 10;
int n, m, k, fac[N], invfac[N], sup[N], atk[N];
int binom(int x, int y)
{
	if (x < y || y < 0)
		return 0;
	return mul(fac[x], mul(invfac[y], invfac[x - y]));
}
int f[N][N], g[N][N], sum[N];
int F(int x, int y) // choose x, use y
{
	if (!y)
		return binom(n, x);
	int res = 0;
	for (int i = x - y + 1; i <= n - y + 1; ++i) // i used first
		inc(res, mul(f[y][i], binom(i - 1, x - y)));
	return res;
}
int G(int x, int y) // choose x, use y
{
	int res = 0;
	for (int i = x - y + 1; i <= n - y + 1; ++i) // i used first
		inc(res, mul(g[y][i], binom(i - 1, x - y)));
	return res;
}
void solve()
{
	n = read(), m = read(), k = read();
	for (int i = 1; i <= n; ++i)
		sup[i] = read();
	for (int i = 1; i <= n; ++i)
		atk[i] = read();
	sort(sup + 1, sup + 1 + n);
	sort(atk + 1, atk + 1 + n);
	for (int i = 1; i <= n; ++i)
	{
		f[1][i] = sup[i];
		sum[i] = add(sum[i - 1], f[1][i]);
	}
	for (int i = 2; i <= n; ++i)
	{
		for (int j = 1; j <= n - i + 1; ++j)
			f[i][j] = mul(sup[j], add(sum[n], P - sum[j]));
		for (int j = 1; j <= n; ++j)
		{
			if (j <= n - i + 1)
				sum[j] = add(sum[j - 1], f[i][j]);
			else
				sum[j] = sum[j - 1];
		}
	}
	for (int i = 1; i <= n; ++i)
	{
		g[1][i] = atk[i];
		sum[i] = add(sum[i - 1], g[1][i]);
	}
	for (int i = 2; i <= n; ++i)
	{
		for (int j = 1; j <= n - i + 1; ++j)
			g[i][j] = add(mul(atk[j], binom(n - j, i - 1)), add(sum[n], P - sum[j]));			
		for (int j = 1; j <= n; ++j)
		{
			if (j <= n - i + 1)
				sum[j] = add(sum[j - 1], g[i][j]);
			else
				sum[j] = sum[j - 1];
		}
	}
	int ans = 0;
	for (int i = 0; i < m; ++i)
		if (i < k)
			inc(ans, mul(F(i, i), G(m - i, k - i)));
		else
			inc(ans, mul(F(i, k - 1), G(m - i, 1)));
	write(ans, '\n');
}
int main()
{
	fac[0] = 1;
	for (int i = 1; i <= 3000; ++i)
		fac[i] = mul(fac[i - 1], i);
	invfac[3000] = fpow(fac[3000], P - 2);
	for (int i = 3000 - 1; i >= 0; --i)
		invfac[i] = mul(invfac[i + 1], i + 1);
	int T = read();
	while (T--)
		solve();
	return 0;
}