loj2538 「PKUWC 2018」Slay the Spire

2018/05/21 08:43
阅读数 24

pkusc 快到了……做点题涨涨 rp。 ref我好菜啊QAQ。


可以发现期望只是一个幌子。我们的目的是:对于所有随机的选择方法(一共 $\binom{2n}{m}$种),这些选择方法都最优地打出 $k$ 张牌,他们能造成的伤害的和是多少。

显然的是,能打强化就打强化(不过你好歹也要攻击一张)。记 $m$ 张卡中分给强化卡的数量为 $i$。我们枚举 $i$,根据 $i$ 与 $k$ 的大小关系来决定怎样打牌。

那么 $i < k$ 时,就打出 $i$ 张强化卡,$k-i$ 张攻击卡。(这意味着你能打的强化卡总共才 $i$ 张,当然是能打强化卡就打强化卡)

$i \geq k-1$ 时,就打出 $k-1$ 张强化卡,$1$ 张攻击卡。(这意味着你能打的强化卡还挺多,留一张攻击就行了)。

记 $F(i,j)$ 为分给强化卡的数量为 $i$,打出 $j$ 张,所有方案翻的倍率的和。$G(i,j)$ 为分给攻击卡的数量为 $i$,打出 $j$ 张,所有方案的(不加强化的)攻击力和。

两者分别对应 $F(i,i) \times G(m-i,k-i)$ 和 $F(i,k-1) \times G(m-i,1)$。为什么可以是这种“和乘和”的形式呢?因为乘法分配律。


现在的问题变成快速计算 $F$ 和 $G$。

关于 $F$,可以 sort 以后定义一个 $f$,$f(i,j)$ 表示(注意是选,不是分)了 $i$ 张强化牌且最这 $i$ 张牌中位置靠前的那张牌是所有强化牌中的第 $j$ 个,这样的所有方案翻的倍率的和。转移看代码。$G$ 和 $g$ 也类似。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
const int mod=998244353;
int T, n, m, k, a[1505], b[1505], c[3005][3005], f[1505][1505];
int g[1505][1505], sum[1505];
int F(int x, int y){
	if(x<y)	return 0;
	if(!y)	return c[n][x];
	int re=0;
	for(int j=x-y+1; j<=n-y+1; j++)
		re = (re + (ll)f[y][j]*c[j-1][x-y]%mod) % mod;
    //感性理解一下……大概就是把x-y张不打出的牌放到j前头,这里我讲不太清QAQ
	return re;
}
int G(int x, int y){
	if(x<y)	return 0;
	int re=0;
	for(int j=x-y+1; j<=n-y+1; j++)
		re = (re + (ll)g[y][j]*c[j-1][x-y]%mod) % mod;
	return re;
}
int main(){
	cin>>T;
	for(int i=0; i<=3000; i++){
		c[i][0] = 1;
		for(int j=1; j<=i; j++)
			c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod;
	}
	while(T--){
		memset(f, 0, sizeof(f));
		memset(g, 0, sizeof(g));
		scanf("%d %d %d", &n, &m, &k);
		for(int i=1; i<=n; i++)	scanf("%d", &a[i]);
		for(int i=1; i<=n; i++)	scanf("%d", &b[i]);
		sort(a+1, a+1+n);//跟牌的顺序无关,可以sort
		sort(b+1, b+1+n);
		for(int i=1; i<=n; i++){
			f[1][i] = a[i];//初始化f[][],显然只选1张的倍率之和是a[i]
			sum[i] = (sum[i-1] + a[i]) % mod;//前缀和,方便转移
		}
		for(int i=2; i<=n; i++){
			for(int j=1; j<=n-i+1; j++)
				f[i][j] = (ll)a[j] * (sum[n]-sum[j]+mod) % mod;
            //打了i张牌,最前头的是第j张,那它就是f[i-1][j+1..n]的和再乘上第j号元素。这个转移的思想是枚举在打了i-1张牌的时候最前头的是哪一张
			for(int j=1; j<=n; j++)
				sum[j] = (sum[j-1] + f[i][j]) % mod;
		}
		for(int i=1; i<=n; i++){
			g[1][i] = b[i];
			sum[i] = (sum[i-1] + b[i]) % mod;
		}
		for(int i=2; i<=n; i++){
			for(int j=1; j<=n-i+1; j++)
				g[i][j] = ((ll)b[j]*c[n-j][i-1]%mod+(sum[n]-sum[j]+mod)%mod) % mod;
            //打了i张牌,最前头的是第j张。注意g代表的是(不加强化的)攻击力和。在这种情况下,打了i-1张牌的总情况是c[n-j][i-1]种(j+1..n中选i-1个的方案数),这是第一项;第二项就是继承自g[i-1][j+1..n]
			for(int j=1; j<=n; j++)
				sum[j] = (sum[j-1] + g[i][j]) % mod;
		}
		int ans=0;
		for(int i=0; i<m; i++)
			if(i<k)	ans = (ans + (ll)F(i,i)*G(m-i,k-i)%mod) % mod;
			else	ans = (ans + (ll)F(i,k-1)*G(m-i,1)%mod) % mod;
		printf("%d\n", ans);
	}
	return 0;
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部