2019/01/18 19:38

# Description

<font size="3">

1. 攻击牌：打出后对对方造成等于牌上的数字的伤害。

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

$$\left (\text{ans}\times \frac{(2n)!}{m!(2n-m)!}\right) ~\bmod 998244353$$

</font>

<font size="3">

</font>

<font size="3">

</font>

# Solution

<font size=“3”>

$$G_{i,j}=\sum_{k=j-1}^{i-1} {G_{k,j-1} * w_i}$$

$$F_{i,j}=\sum_{k=j-1}^{i-1} {F_{k,j-1}+C_{k}^{j-1} * w_i}$$

</font>

# Code

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=3010,Mod=998244353;
int T,n,m,k,w[N],atk[N],ans;
{
int ans=0;char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
return ans;
}
int C(int x,int y)
{
return (x>=y?1LL*J[x]*R[y]%Mod*R[x-y]%Mod:0);
}
int fpow(int a,int k)
{
int ans=1;
while (k)
{
if (k&1) ans=1LL*ans*a%Mod;
a=1LL*a*a%Mod;
k>>=1;
}
return ans;
}
bool cmp(int a,int b)
{
return a>b;
}
void init()
{
ans=0;
memset(F,0,sizeof(F));
memset(G,0,sizeof(G));
memset(pro_sum,0,sizeof(pro_sum));
memset(mul_sum,0,sizeof(mul_sum));
}
int main()
{
J[0]=1;
for (int i=1;i<=3000;i++) J[i]=1LL*J[i-1]*i%Mod;
for (int i=0;i<=3000;i++) R[i]=fpow(J[i],Mod-2);
while (T--)
{
init();
sort(w+1,w+n+1,cmp);
sort(atk+1,atk+n+1,cmp);
mul_sum[0]=1;
G[0][0]=1;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=min(i,k-1);j++)
G[i][j]=(G[i][j]+1LL*mul_sum[j-1]*w[i]%Mod)%Mod;
for (int j=1;j<=min(i,k-1);j++)
mul_sum[j]=(mul_sum[j]+G[i][j])%Mod;
}
pro_sum[0]=1;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=min(i,k);j++)
for (int j=1;j<=min(i,k);j++)
{
pro_sum[j]=(pro_sum[j]+C(i-1,j-1))%Mod;
}
}
for (int i=0;i<=min(n,m-1);i++)
{
if (m-i>n) continue;
if (i<k)
{
int num=0,res=k-i;
for (int j=i;j<=n;j++) num=(num+G[j][i])%Mod;
for (int j=res;j<=n;j++)
ans=(ans+1LL*num*F[j][res]%Mod*C(n-j,m-k)%Mod)%Mod;
//因为要保证res张攻击牌只能在前j张产生。所以要使得m-k张攻击牌的权值小于前j张
}
else
{
int num=0;
for (int j=k-1;j<=n;j++) num=(num+1LL*G[j][k-1]*C(n-j,i-(k-1))%Mod)%Mod;
for (int j=1;j<=n;j++)
ans=(ans+1LL*num*F[j][1]%Mod*C(n-j,m-i-1)%Mod)%Mod;//同理
}
}
printf("%d\n",ans);
}
return 0;
}


0
0 收藏

0 评论
0 收藏
0