Submission #39102934

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int N=88,mod=998244353;

int ksm(int a,int x){
	int tot=1;
	while(x){
		if(x&1) tot=1ll*tot*a%mod;
		a=1ll*a*a%mod;
		x>>=1ll;
	}
	return tot;
} 
int C[N][N];
void init(int lim){
	for(int i=0;i<=lim;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	}
}
int ID(int x){
	return (x & 1ll)?mod-1:1;
}

int a[N][N];
int det(int a[N][N],int n){
	int tot=1;
	for(int k=1;k<=n;k++){
		int st=0;
		for(int i=k;i<=n;i++){
			if(a[i][k]){
				st=i;
				break;
			}
		}
		if(!st) return 0;
		for(int j=1;j<=n;j++) swap(a[k][j],a[st][j]);
		if(st!=k) tot=mod-tot;
		for(int i=k+1;i<=n;i++){
			int t=1ll*a[i][k]*ksm(a[k][k],mod-2)%mod;
			for(int j=k;j<=n;j++) a[i][j]=(a[i][j]+mod-1ll*a[k][j]*t%mod)%mod;
		}
		tot=1ll*tot*a[k][k]%mod;
	}
	return tot;
}

int n,m,ans;
int f[N][N],f_[N][N];

int val[N][N];

int F[N][N],G[N][N],S[N][N];

int main(){
	init(N-5);
	cin>>n>>m;
	
	for(int T=1;T<=2;T++){
		memset(f,0,sizeof(f));
		memset(f_,0,sizeof(f_));
		memset(F,0,sizeof(F));
		memset(G,0,sizeof(G));
		memset(S,0,sizeof(S));
		
		int k=n+m;
		
		for(int i=1;i<=m;i++)
			for(int j=1;j<=n;j++)
				f[i][j]=C[i-1+j-1][i-1];
		for(int i=1;i<=m;i++){
			if(i>1) f_[i][i+n]=1;
			for(int j=1;j<=i;j++)
				f[i][j+n]=C[i-j+n-1][n-1];
		}
		for(int i=1;i<=n;i++){
			f_[i+m][i]=1;
			for(int j=i;j<=n;j++)
				f[i+m][j]=C[j-i+m-1][m-1];
		}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				f[i+m][j+n]=C[n-i+m-j][n-i];
		
		for(int x=0;x<=n;x++){
			for(int y=0;y<=m;y++){
				for(int i=1;i<=k;i++)
					for(int j=1;j<=k;j++){
						if(i<=m) a[i][j]=(1ll*f[i][j]*y%mod+f_[i][j])%mod;
						else a[i][j]=(1ll*f[i][j]*x%mod+f_[i][j])%mod;
					}
				val[x][y]=det(a,k);
			}
		}
		
		for(int i=0;i<=n;i++){
			F[i][0]=1;
			int val=1;
			for(int j=0;j<=n;j++){
				if(j==i) continue;
				for(int t=n;t>=0;t--){
					F[i][t]=1ll*(mod-j)*F[i][t]%mod;
					if(t) F[i][t]=(F[i][t]+F[i][t-1])%mod;
				}
				val=1ll*val*ksm(i+mod-j,mod-2)%mod;
			}
			for(int t=0;t<=n;t++) F[i][t]=1ll*F[i][t]*val%mod;
		}
		
		for(int i=0;i<=m;i++){
			G[i][0]=1;
			int val=1;
			for(int j=0;j<=m;j++){
				if(j==i) continue;
				for(int t=m;t>=0;t--){
					G[i][t]=1ll*(mod-j)*G[i][t]%mod;
					if(t) G[i][t]=(G[i][t]+G[i][t-1])%mod;
				}
				val=1ll*val*ksm(i+mod-j,mod-2)%mod;
			}
			for(int t=0;t<=m;t++) G[i][t]=1ll*G[i][t]*val%mod; 
		}
		
		for(int x=0;x<=n;x++){
			for(int y=0;y<=m;y++){
				for(int i=0;i<=n;i++){
					for(int j=0;j<=m;j++){
						S[i][j]=(S[i][j]+1ll*val[x][y]*F[x][i]%mod*G[y][j]%mod)%mod;
					}
				}
			}
		}
		
		for(int i=0;i<=n;i++){
			for(int j=0;j<=m;j++){
				if(__gcd(i,j)==1) ans=(ans+1ll*S[i][j]*ID(n*m-i*j)%mod)%mod;
			}
		}
		
		swap(n,m);
	}
	
	cout<<ans;
} 

Submission Info

Judge Result