QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#104580#59. Determinant of A+BzieeJudging//C++142.1kb2023-05-11 09:19:202024-03-04 04:40:49

Judging History

你现在查看的是测评时间为 2024-03-04 04:40:49 的历史记录

  • [2024-05-05 12:01:03]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:97
  • 用时:611ms
  • 内存:6928kb
  • [2024-05-05 11:54:08]
  • hack成功,自动添加数据
  • (/hack/617)
  • [2024-05-05 11:44:40]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:601ms
  • 内存:6928kb
  • [2024-05-05 11:38:15]
  • hack成功,自动添加数据
  • (/hack/616)
  • [2024-03-04 04:44:57]
  • 管理员手动重测本题所有提交记录
  • 测评结果:100
  • 用时:576ms
  • 内存:7020kb
  • [2024-03-04 04:40:49]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:Judging
  • 用时:734ms
  • 内存:6752kb
  • [2024-03-04 04:35:40]
  • hack成功,自动添加数据
  • (/hack/552)
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-11 09:19:25]
  • 评测
  • 测评结果:100
  • 用时:734ms
  • 内存:6752kb
  • [2023-05-11 09:19:20]
  • 提交

answer

//https://qoj.ac/submission/69597
//https://www.cnblogs.com/Y25t/p/15808634.html
#include<cstdio>
#include<iostream>
using namespace std;
const int o=510,MOD=998244353;
inline int qp(int b,int f){int res=1;for(;f;f>>=1,b=b*1ll*b%MOD) if(f&1) res=res*1ll*b%MOD;return res;}
int n,a[o][o],b[o][o],f[o][o],delt,coef=1;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) scanf("%d",&a[i][j]);
	for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) scanf("%d",&b[i][j]);
	for(int i=1,j;i<=n;++i){
		for(j=i;j<=n;++j) if(b[j][i]) break;
		if(j<=n&&j>i){coef=MOD-coef;for(int k=1;k<=n;++k) swap(a[i][k],a[j][k]),swap(b[i][k],b[j][k]);}
//		for(j=i;j<=n;++j) if(b[i][j]) break;
//		if(j<=n&&j>i){coef=MOD-coef;for(int k=1;k<=n;++k) swap(a[k][i],a[k][j]),swap(b[k][i],b[k][j]);}
		for(;delt<=n&&!b[i][i];++delt){
			for(j=1;j<=n;++j) b[i][j]=a[i][j],a[i][j]=0;
			for(j=1;j<i;++j) for(int k=1,v=b[i][j]*1ll*qp(b[j][j],MOD-2)%MOD;k<=n;++k)
				a[i][k]=(a[i][k]+(MOD-v)*1ll*a[j][k])%MOD,b[i][k]=(b[i][k]+(MOD-v)*1ll*b[j][k])%MOD;
		}
		if(b[i][i]) for(j=1;j<=n;++j) if(j^i) for(int k=1,v=b[j][i]*1ll*qp(b[i][i],MOD-2)%MOD;k<=n;++k)
			a[j][k]=(a[j][k]+(MOD-v)*1ll*a[i][k])%MOD,b[j][k]=(b[j][k]+(MOD-v)*1ll*b[i][k])%MOD;
	}
	for(int i=1;i<=n;++i){
		coef=coef*1ll*b[i][i]%MOD;
		for(int j=1,v=qp(b[i][i],MOD-2);j<=n;++j) a[i][j]=a[i][j]*1ll*v%MOD;
	}
	for(int i=1,j,v;i<n;++i){
		for(j=i+1;j<=n;++j) if(a[j][i]) break;
		if(j>n) continue;
		if(j>i+1){
			for(int k=1;k<=n;++k) swap(a[i+1][k],a[j][k]);
			for(int k=1;k<=n;++k) swap(a[k][i+1],a[k][j]);
		}
		for(j=i+2;j<=n;++j){
			v=a[j][i]*1ll*qp(a[i+1][i],MOD-2)%MOD;
			for(int k=1;k<=n;++k) a[j][k]=(a[j][k]+(MOD-v)*1ll*a[i+1][k])%MOD;
			for(int k=1;k<=n;++k) a[k][i+1]=(a[k][i+1]+v*1ll*a[k][j])%MOD;
		}
	}
	f[0][0]=coef;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j) f[i][j]=f[i-1][j-1];
		for(int j=i,v=1;j;v=MOD-a[j][j-1]*1ll*v%MOD,--j) for(int k=0;k<=n;++k) f[i][k]=(f[i][k]+a[j][i]*1ll*v%MOD*f[j-1][k])%MOD;
	}
	for(int i=0;i<=n;++i) printf("%d ",((i+delt)>n)?0:f[n][i+delt]);
	return 0;
}