abc g求调
  • 板块学术版
  • 楼主Judgelight
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/11/5 10:39
  • 上次更新2023/11/5 12:06:57
查看原帖
abc g求调
461616
Judgelight楼主2023/11/5 10:39
#include<bits/stdc++.h>
#define N 1009
using namespace std;
const int mod=998244353,i2=499122177;
inline int md(int x){if(x>=mod)x-=mod;if(x<0)x+=mod;return x;}
int ksm(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=1ll*ans*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return ans;
}
int n,m,l,fc[N],ifc[N],F[N][N],G[N][N],H[N][N];
inline int c(int n,int m){if(n<m||n<0||m<0)return 0;return 1ll*fc[n]*ifc[m]%mod*ifc[n-m]%mod;}
inline int s(int n,int m){
	int ans=0;
	for(int i=0,j=1;i<=m;i++,j=-j)ans=md(ans+1ll*j*c(m,i)*ksm(m-i,n)%mod);
	return ans;
}
inline int g(int n,int m){
	if(~G[n][m])return G[n][m];
	int ans=0;for(int i=0;i<=n;i++)ans=md(ans+1ll*c(n,i)*c(i*(n-i),m)%mod);
	return G[n][m]=ans;
}
inline int h(int n,int m){
	if(~H[n][m])return H[n][m];
	int ans=g(n,m);
	for(int i=1;i<n;i++)for(int j=0;j<=m;j++)ans=md(ans-1ll*c(n-1,i-1)*h(i,j)%mod*g(n-i,m-j)%mod);
	return H[n][m]=ans;
}
inline int f(int n,int m){
	if(~F[n][m])return F[n][m];
	int ans=1ll*h(n,m)*i2%mod;
	for(int i=1;i<n;i++)for(int j=0;j<=m;j++)ans=md(ans+1ll*c(n-1,i-1)*f(i,j)%mod*h(n-i,m-j)%mod*i2%mod);
	return F[n][m]=ans;
}
signed main(){
	memset(F,-1,sizeof(F)),memset(G,-1,sizeof(G)),memset(H,-1,sizeof(H));
	scanf("%d%d",&n,&m),l=n*(n+1)/2;
	fc[0]=1;for(int i=1;i<=l;i++)fc[i]=1ll*fc[i-1]*i%mod;
	ifc[l]=ksm(fc[l],mod-2);for(int i=l;i;i--)ifc[i-1]=1ll*ifc[i]*i%mod;
	int ans=0;
	for(int i=0;i<=l;i++)ans=md(ans+1ll*f(n,i)*s(m,i)%mod);
	printf("%lld",1ll*ans*ksm(2,m)%mod);
	return 0;
}
2023/11/5 10:39
加载中...