P8321 『JROI-4』沈阳大街 2 题解

考虑把

a_i

看作

1

类数，

b_i

看作

2

类数，将所有

a_i

和所有

b_i

扔进一个长度为

2n

的数列

c

中并从大到小排序，每次选出一个

1

类数和

2

类数进行匹配，贡献乘上较小的数的值，将问题转化为求所有匹配方案的贡献之和。

设

f_{i,j}

表示考虑到数列

c

的第

i

项，此时一共匹配了

j

对数的方案的贡献的和。转移时，首先根据

i,j

和前缀和数组，计算出未匹配的

1

类数数量

x

和未匹配的

2

类数数量

y

，再根据

c_{i+1}

的类型分别处理：

若 $c_{i+1}$ $c_{i + 1}$ 为 $1$ $1$ 类数：
- 若 $y>0$ ：对 $c_{i+1}$ 进行匹配， $f_{i+1,j+1} \leftarrow f_{i+1,j+1}+y\times c_{i+1} \times f_{i,j}$ ；
- 不对 $c_{i+1}$ 进行匹配， $f_{i+1,j} \leftarrow f_{i+1,j}+f_{i,j}$ 。
若 $c_{i+1}$ $c_{i + 1}$ 为 $2$ $2$ 类数：
- 若 $x>0$ ：对 $c_{i+1}$ 进行匹配， $f_{i+1,j+1} \leftarrow f_{i+1,j+1}+x\times c_{i+1} \times f_{i,j}$ ；
- 不对 $c_{i+1}$ 进行匹配， $f_{i+1,j} \leftarrow f_{i+1,j}+f_{i,j}$ 。

初始化

f_{0,0}=0

，答案即为

f_{2n,n}

。

时间复杂度

\mathcal O(n^2)

。

const int N=5005,mod=998244353;
int n,f[N<<1][N],s[N<<1][3];
pii p[N<<1];
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
int ksm(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		b>>=1,a=1ll*a*a%mod;
	}
	return res;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>p[i].fi,p[i].se=1;
	for(int i=1;i<=n;i++) cin>>p[n+i].fi,p[n+i].se=2;
	sort(p+1,p+n+n+1),reverse(p+1,p+n+n+1);
	for(int i=1;i<=n+n;i++) for(int k=1;k<=2;k++) s[i][k]=s[i-1][k]+(p[i].se==k);
	f[0][0]=1;
	for(int i=0;i<n+n;i++){
		for(int j=0;j<=min(s[i][1],s[i][2]);j++){
			int x=s[i][1]-j,y=s[i][2]-j;
			if(p[i+1].se==1){
				if(y>0) add(f[i+1][j+1],1ll*y*p[i+1].fi%mod*f[i][j]%mod);
				add(f[i+1][j],f[i][j]);
			}
			else{
				if(x>0) add(f[i+1][j+1],1ll*x*p[i+1].fi%mod*f[i][j]%mod);
				add(f[i+1][j],f[i][j]);
			}
		}
	}
	int fac=1;
	for(int i=1;i<=n;i++) fac=1ll*fac*i%mod;
	cout<<1ll*ksm(fac,mod-2)*f[n+n][n]%mod<<endl;
}

P8321 『JROI-4』沈阳大街 2 题解

文章操作

相关推荐

评论

P8321 『JROI-4』沈阳大街 2 题解