QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#18012#59. Determinant of A+BzY25t#0 0ms0kbC++202.3kb2022-01-15 18:09:592022-05-04 16:40:28

Judging History

你现在查看的是测评时间为 2022-05-04 16:40:28 的历史记录

  • [2024-05-05 11:54:08]
  • hack成功,自动添加数据
  • (/hack/617)
  • [2024-05-05 11:38:15]
  • hack成功,自动添加数据
  • (/hack/616)
  • [2024-03-04 04:41:37]
  • 管理员手动重测本题所有提交记录
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [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.
  • [2022-05-04 16:40:28]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2022-01-15 18:09:59]
  • 提交

answer

#include<bits/stdc++.h>
#define P 998244353
#define N 505

inline int fmo(int x){
	return x+((x>>31)&P);
}
inline int fp(int x,int k=P-2){
	int res=1;
	for(;k;k>>=1,x=1ll*x*x%P)
		if(k&1)
			res=1ll*res*x%P;
	return res;
}

int n,a[N][N],b[N][N];

int f[N][N];

int main(){
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
	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]);
	int flg=1,t=0;
	for(int i=1;i<=n;i++){
		if(!b[i][i])
			for(int j=i+1;j<=n;j++)
				if(b[j][i]){
					flg=fmo(-flg);
					std::swap(a[i],a[j]),std::swap(b[i],b[j]);
					break;
				}
		if(!b[i][i])
			for(int j=i+1;j<=n;j++)
				if(b[i][j]){
					flg=fmo(-flg);
					for(int k=1;k<=n;k++)
						std::swap(a[k][i],a[k][j]),std::swap(b[k][i],b[k][j]);
					break;
				}
		for(;!b[i][i]&&t<n;t++){
			for(int j=1;j<=n;j++)
				b[i][j]=a[i][j],a[i][j]=0;
			for(int j=1;j<i;j++){
				int tmp=1ll*b[i][j]*fp(b[j][j])%P;
				for(int k=1;k<=n;k++){
					a[i][k]=fmo(a[i][k]-1ll*tmp*a[j][k]%P);
					b[i][k]=fmo(b[i][k]-1ll*tmp*b[j][k]%P);
				}
			}
		}
		int inv=fp(b[i][i]);
		for(int j=1;j<=n;j++) if(j!=i){
			int tmp=1ll*b[j][i]*inv%P;
			for(int k=1;k<=n;k++){
				a[j][k]=fmo(a[j][k]-1ll*tmp*a[i][k]%P);
				b[j][k]=fmo(b[j][k]-1ll*tmp*b[i][k]%P);
			}
		}
	}
	for(int i=1;i<=n;i++){
		flg=1ll*flg*b[i][i]%P;
		int inv=fp(b[i][i]);
		for(int j=1;j<=n;j++)
			a[i][j]=1ll*a[i][j]*inv%P;
	}
	for(int i=1;i<n;i++){
		if(!a[i+1][i])
			for(int j=i+2;j<=n;j++)
				if(a[j][i]){
					std::swap(a[i+1],a[j]);
					for(int k=1;k<=n;k++)
						std::swap(a[k][i+1],a[k][j]);
					break;
				}
		int inv=fp(a[i+1][i]);
		for(int j=i+2;j<=n;j++){
			int tmp=1ll*a[j][i]*inv%P;
			for(int k=1;k<=n;k++)
				a[j][k]=fmo(a[j][k]-1ll*tmp*a[i+1][k]%P);
			for(int k=1;k<=n;k++)
				a[k][i+1]=fmo(a[k][i+1]+1ll*tmp*a[k][j]%P-P);
		}
	}
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		int tmp=1;
		for(int j=i;j;j--){
			for(int k=0;k<=n;k++)
				f[i][k]=fmo(f[i][k]+1ll*((i-j)&1?fmo(-1):1)*f[j-1][k]%P*a[j][i]%P*tmp%P-P);
			tmp=1ll*tmp*a[j][j-1]%P;
		}
		for(int k=0;k<n;k++)
			f[i][k+1]=fmo(f[i][k+1]+f[i-1][k]-P);
	}
	for(int i=0;i<=n;i++)
		printf("%d ",i+t>n?0:int(1ll*flg*f[n][i+t]%P));
	puts("");
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

input:

50
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 179093706 0 0 0 0 0 873235003 0 873022990 0 0 0 0 150372208 0 0 0 0 0 0 0 0
540031202 441544333 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 30490606 0 23238599 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:


result:


Subtask #2:

score: 0
Dangerous Syscalls

Test #51:

score: 0
Dangerous Syscalls

input:

500
0 0 0 0 0 482890969 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1077401 0 0 210804413 0 508044994 0 0 0 398405351 0 0 0 0 0 0 0 171917316 0 0 0 0 0 0 0 0 0 0 0 429230725 0 0 0 0 0 45665526 0 0 0 925078893 0 0 396149045 0 0 0 595858405 0 0 0 0 0 57208...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #1:

0%