Description

九条可怜在玩一个很好玩的策略游戏：Slay the Spire，一开始九条可怜的卡组里有2n张牌，每张牌上都写着一个

数字wi，一共有两种类型的牌，每种类型各n张：1.攻击牌：打出后对对方造成等于牌上的数字的伤害。2.强化牌

：打出后，假设该强化牌上的数字为x，则其他剩下的攻击牌的数字都会乘上x。保证强化牌上的数字都大于1。现

在九条可怜会等概率随机从卡组中抽出m张牌，由于费用限制，九条可怜最多打出k张牌，假设九条可怜永远都会采

取能造成最多伤害的策略，求她期望造成多少伤害。

假设答案为y，你只需要输出

（2n）!*y / (m!*(2n-m)!) Mod 998244353

 

 

Input

第一行一个正整数T表示数据组数

接下来对于每组数据：

第一行三个正整数n,m,k

第二行n个正整数wi，表示每张强化牌上的数值。

第三行n个正整数wi，表示每张攻击牌上的数值。

1<=k<=m<=2n<=3e3

1<=wi<=1e8

Σ2n <= 3e4

 

 

Output

输出T行，每行一个非负整数表示每组数据的答案。

 

 

Sample Input

2

2 3 2

2 3

1 2

10 16 14

2 3 4 5 6 7 8 9 10 11

1 2 3 4 5 6 7 8 9 10

Sample Output

19

253973805

---

可以发现题目要求的期望是假的，乘上的那个相当于一个总方案数

也就是说只要求出所有抽m张牌的产生的总和即可

再进一步分析题目，发现强化卡>=1的性质使得必定是先尽量用强化卡

设强化卡的数量为i

当$i<k$时，有多少用多少，接下来再用最大的$k-i$张攻击卡

当$i>k$时，用$k-1$张强化卡，再用一张最大的攻击卡

我们找最优取法，再乘上这个取法出现的次数即可

设$F(i,j)$为用了$i$张强化卡，其中最大的是第$j$大的，所有取法的乘积的和

设$G(i,j)$为用了$i$张攻击卡，其中最大的是第$j$大的，所有取法的和的和

那么若抽m张中有x张是强化卡，最优策略会用掉y张，则有

$\sum\limits_i \sum\limits_j f_{y,i} \times g_{k-y,j} \times C_{n-i}^{x-y} \times C_{n-j}^{m-x-(k-y)}$

我们用$f(i,j)$表示用了$i$张强化卡，其中最大的小于等于第$j$大的，所有取法的乘积的和

可也得出$f(i,j)=f(i-1,j-1)*w[j]+f(i,j-1)$，$F(i,j)=f(i,j)-f(i,j-1)$

G的处理类似

而对于上面的那组求和公式，因为满足乘法分配律

其实我们可以对$f$和$g$分别求和，再乘到一起，效果是一样的

再代码中我们可以对种觉察情况分别求和，再加到一起

 

1 #include
         
           2 #include
          
            3 #define N 3005 4 #define ll long long 5 #define mod 998244353 6 using namespace std; 7 int T; 8 ll n,m,k; 9 ll fac[N],inv[N],c[N][N],ans,f[N][N],g[N][N];10 ll w[2][N];11 ll ksm(ll x,ll t){12     ll ans=1;13     for(;t;t>>=1,x=(x*x)%mod)if(t&1)ans=(ans*x)%mod;14     return ans;15 }16 inline void pre(){17     fac[0]=1;for(int i=1;i<=3000;i++)fac[i]=(fac[i-1]*i)%mod;18     inv[3000]=ksm(fac[3000],mod-2);19     for(int i=2999;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;20     c[0][0]=1;21     for(int i=1;i<=3000;i++)22     for(int j=0;j<=i;j++)23     c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;24     for(int i=0;i<=3000;i++)f[0][i]=1;25 }26 bool cmp(int a,int b){
       return a>b;}27 int main(){28     pre();29     scanf("%d",&T);30     while(T--){31         scanf("%lld%lld%lld",&n,&m,&k);32         for(int i=1;i<=n;i++)scanf("%lld",&w[0][i]);33         for(int i=1;i<=n;i++)scanf("%lld",&w[1][i]);34         sort(w[0]+1,w[0]+n+1,cmp);35         sort(w[1]+1,w[1]+n+1,cmp);36         ans=0;37         for(int i=1;i<=n;i++)38         for(int j=1;j<=n;j++){39             f[i][j]=(1ll*f[i-1][j-1]*w[0][j]+f[i][j-1])%mod;40             g[i][j]=(g[i-1][j-1]+1ll*(c[j][i]-c[j-1][i]+mod)*w[1][j]+g[i][j-1])%mod;41         }42         for(int i=0;i
           
            =m-k;j++)45             sum2=(sum2+1ll*(g[k-i][j]-g[k-i][j-1]+mod)*fac[n-j]%mod*inv[m-k]%mod*inv[n-j-(m-k)])%mod;46             ans=(ans+sum1*sum2)%mod;47         }48         for(int i=k;i
            
             =i-(k-1);j++)51             sum1=(sum1+1ll*(f[k-1][j]-f[k-1][j-1]+mod)*fac[n-j]%mod*inv[i-(k-1)]%mod*inv[n-j-(i-(k-1))])%mod;52             for(int j=1;n-j>=m-i-1;j++)53             sum2=(sum2+1ll*(g[1][j]-g[1][j-1]+mod)*fac[n-j]%mod*inv[m-i-1]%mod*inv[n-j-(m-i-1)])%mod;54             ans=(ans+sum1*sum2)%mod;55         }56         printf("%lld\n",ans);57     }58     return 0;59 }
            
           
          
         

这道题我在LOJ上WA的时候发现w数组开成了w[0][N]，然而这样的码还能A掉BZ上的数据

感到十分震惊并认为其中有鬼23333