Nothing is compiled: OUTPUT exceeds.
查看原帖
Nothing is compiled: OUTPUT exceeds.
1072900
Segment_Treap楼主2025/7/31 20:17

Nothing is compiled: OUTPUT exceeds.

这是个什么东西

#include <bits/stdc++.h>
using namespace std;
const int N=1000100,M=998244353;
int n,ans,ls[N],rs[N],siz[N],cat[N]={1},fac[(N<<1)]={1,1},inv[(N<<1)]={1,1};
int comb(int sum1,int sum2){
	return 1ll*fac[sum1]*inv[sum2]%M*inv[sum1-sum2]%M;
}
void dfs1(int id){
	siz[id]=1;
	if(ls[id]) dfs1(ls[id]),siz[id]+=siz[ls[id]];
	if(rs[id]) dfs1(rs[id]),siz[id]+=siz[rs[id]];
}
void dfs2(int id,int mul){
	if(siz[ls[id]]<=siz[rs[id]]+1){
		for(int lsiz=0;lsiz<siz[ls[id]];lsiz++)
			(ans+=1ll*mul*cat[lsiz]%M*cat[siz[id]-1-lsiz]%M)%=M;
	}else{
		(ans+=1ll*mul*cat[siz[id]]%M)%=M;
		for(int rsiz=0;rsiz<=siz[rs[id]];rsiz++)
			(ans+=M-(1ll*mul*cat[rsiz]%M*cat[siz[id]-1-rsiz]%M))%=M;
	}
	if(ls[id]) dfs2(ls[id],1ll*mul*cat[siz[rs[id]]]%M);
	if(rs[id]) dfs2(rs[id],mul);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&ls[i],&rs[i]);
	for(int i=2;i<=2*n;i++){
		fac[i]=1ll*fac[i-1]*i%M;
		inv[i]=1ll*inv[M%i]*(M-M/i)%M;
	}
	for(int i=2;i<=2*n;i++)
		inv[i]=1ll*inv[i-1]*inv[i]%M;
	for(int i=1;i<=n;i++)
		cat[i]=(comb(2*i,i)-comb(2*i,i-1)+M)%M;
	dfs1(1),dfs2(1,1);
	for(int i=1;i<n;i++) (ans+=cat[i])%=M;
	printf("%d",ans);
}
2025/7/31 20:17
加载中...