购物网站建设多少钱,wordpress注册网址,搜狐最大的门户网站,建设地方美食网站的目的前言 正题
题目链接:https://www.luogu.com.cn/problem/P5299 题目大意
有2n2n2n张牌#xff0c; nnn张强化牌#xff0c;每张上有一个正整数x(x1)x(x1)x(x1)#xff0c;如果使用后之后的每一张攻击牌伤害都会乘上xxx。nnn张攻击牌#xff0c;每张上有一个正…前言 正题
题目链接:https://www.luogu.com.cn/problem/P5299 题目大意
有2n2n2n张牌
nnn张强化牌每张上有一个正整数x(x1)x(x1)x(x1)如果使用后之后的每一张攻击牌伤害都会乘上xxx。nnn张攻击牌每张上有一个正整数xxx使用后造成xxx点伤害。
随机抽上来mmm张然后按照最优策略打出kkk张的情况下求所有情况造成的伤害和。
1≤k≤m≤2n≤30001\leq k\leq m\leq 2n\leq 30001≤k≤m≤2n≤3000 解题思路
考虑一个最优策略是啥显然地我们有强化牌肯定优先打出直到打完或者只剩最后一费。
因为翻倍至少多一倍的伤害而我们攻击牌肯定是从大往小选所以不可能一张攻击牌使得伤害翻倍。 先把两种牌按照数组从大到小排序 我们可以分为两种情况讨论
打出k−1k-1k−1张强化牌和一张攻击牌打出k−1k-1k−1张强化牌和若干张攻击牌
第一种情况我们设fif_ifi表示选出了iii张强化牌的所有方案中前kkk张牌乘积的和。 然后枚举一个在k−1∼mk-1\sim mk−1∼m之间的数字iii表示抽到了iii张强化牌然后再枚举攻击力最大的一张攻击牌剩下的方案用组合数计算即可。
第二种情况比较麻烦同样的设f0,if_{0,i}f0,i表示抽了i(ik)i(ik)i(ik)张强化牌的所有方案中所有牌的乘积和。然后设fi,jf_{i,j}fi,j表示总共选了iii张攻击牌和强化牌打出了前kkk张强化牌和攻击牌时所有强化牌乘积的和gi,jg_{i,j}gi,j则表示造成的伤害和。 然后转移即可。
时间复杂度O(nm)O(nm)O(nm) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e4,P998244353;
ll T,n,m,k,a[N],b[N],f[N],g[N],fac[N],inv[N],ans;
ll C(ll n,ll m){if(mn)return 0;return fac[n]*inv[m]%P*inv[n-m]%P;
}
signed main()
{inv[0]fac[0]inv[1]1;for(ll i2;iN;i)inv[i]P-inv[P%i]*(P/i)%P;for(ll i1;iN;i)fac[i]fac[i-1]*i%P,inv[i]inv[i-1]*inv[i]%P;scanf(%d,T);while(T--){scanf(%lld%lld%lld,n,m,k);ans0;for(ll i1;in;i)scanf(%lld,a[i]);for(ll i1;in;i)scanf(%lld,b[i]);for(ll i0;im;i)f[i]g[i]0;f[0]1;sort(a1,a1n);reverse(a1,a1n);sort(b1,b1n);reverse(b1,b1n);for(ll i1,x;in;i)for(ll jm;j1;j--){if(jk)(f[j]f[j-1]*a[i]%P)%P;else (f[j]f[j-1])%P;}for(ll ik-1;im;i){for(ll j1;jn;j)(ansf[i]*b[j]%P*C(n-j,m-i-1)%P)%P;f[i]0;}for(ll i1;in;i){for(ll jm;j1;j--){(f[j]f[j-1])%P;if(jk)(g[j]g[j-1]b[i]*f[j-1]%P)%P;else (g[j]g[j-1])%P;}}printf(%lld\n,(ansg[m])%P);}return 0;
}
