「PKUWC2018」Slay the Spire

朱雀 2022-01-09 07:45 107阅读 0赞

## [ 传送门 ][Link 1] ##

## **Solution ** ##

> 计数问题，和期望没什么关系
> 
> 策略是尽量使用强化牌的同时，至少使用一张攻击牌
> 
> 对于强化牌和攻击牌，都使用面值最大的
> 
> 于是我们发现，两种牌之间并没有什么关系，可以分开求
> 
> `K[i][j]`表示`i`张强化牌中选出`j`张最大的，这样的所有方案的贡献和
> 
> `W[i][j]`表示`i`张攻击牌中选出`j`张最大的，这样的所有方案的贡献和
> 
> 分别求出它们后，枚举强化牌的数量，那么选出的强化牌数量是个定值
> 
> 直接将对应的`K`和`W`相乘即可
> 
> 如何求`K`和`W`
> 
> 枚举选出的最小的数是什么，前面的乘组合数，后面的直接dp

## **Code ** ##

#include<bits/stdc++.h> #define ll long long #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) #define reg register const int P=998244353; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } int Mul(int x,int y){return 1ll*x*y%P;} int Add(int x,int y){return (x+y)%P;} const int MN=1.5e3+5,MM=3e3+5; int n,m,k,a[MN],b[MN],ans; int K[MN][MM],W[MN][MM],ks[MN][MN],ws[MN][MN],c[MM][MM]; inline void init() { memset(K,0,sizeof K); memset(W,0,sizeof W); memset(ks,0,sizeof ks); memset(ws,0,sizeof ws); ans=0; } int C(int x,int y) { if(x<0||x<y||y<0) return 0; return c[x][y]; } int Cal_K(int x,int y) { if(x<y) return 0; if(!y) return c[n][x]; int r=0; for(int i=1;i<=n;++i) r=Add(r,Mul(K[i][y],C(i-1,x-y))); return r; } int Cal_W(int x,int y) { if(x<y) return 0; int r=0; for(int i=1;i<=n;++i) r=Add(r,Mul(W[i][y],C(i-1,x-y))); return r; } int main() { int T,i,j; T=read(); //calc C for(i=0;i<=3000;++i) { c[i][0]=c[i][i]=1; for(j=1;j<i;++j) c[i][j]=Add(c[i-1][j],c[i-1][j-1]); } while(T--) { n=read(),m=read(),k=read(); for(i=1;i<=n;++i) a[i]=read(); for(i=1;i<=n;++i) b[i]=read(); std::sort(a+1,a+n+1); std::sort(b+1,b+n+1); init(); //calc K W for(i=n+1;i;--i) { K[i][0]=1;K[i][1]=a[i]; for(j=2;i+j-1<=n;++j) K[i][j]=Mul(ks[i+1][j-1],a[i]); for(j=0;i+j-1<=n;++j) ks[i][j]=Add(ks[i+1][j],K[i][j]); } for(i=n+1;i;--i) { W[i][1]=b[i]; for(j=2;i+j-1<=n;++j) W[i][j]=Add(ws[i+1][j-1],Mul(b[i],C(n-i,j-1))); for(j=1;i+j-1<=n;++j) ws[i][j]=Add(ws[i+1][j],W[i][j]); } //calc ans for(i=0;i<m&&i<=n;++i) { if(i>=k-1) ans=Add(ans,Mul(Cal_K(i,k-1),Cal_W(m-i,1))); else ans=Add(ans,Mul(Cal_K(i,i),Cal_W(m-i,k-i))); } printf("%d\n",ans); } return 0; }

--------------------

Blog来自**PaperCloud**，未经允许，请勿转载，TKS！

转载于:https://www.cnblogs.com/PaperCloud/p/10908383.html

[Link 1]: https://loj.ac/problem/2538