QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#617#387238#59. Determinant of A+BzHanghangHanghangSuccess!2024-05-05 11:53:552024-05-05 11:53:56

Details

Extra Test:

Wrong Answer
time: 1ms
memory: 7760kb

input:

3
0 0 1
1 1 0
1 0 0
0 1 0
0 0 0
0 0 0

output:

0 0 0 0 

result:

wrong answer 1st numbers differ - expected: '998244352', found: '0'

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#387238#59. Determinant of A+BzHanghang97 830ms9592kbC++141.9kb2024-04-12 10:29:002024-05-05 12:06:46

answer

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=503,H=998244353;
ll n,w=1,dt,a[N][N],b[N][N],f[N][N];
ll Ksm(ll x,ll y)
{
	ll s=1;
	for(ll i=1;i<=y;i<<=1,x=x*x%H)if(i&y)s=s*x%H;
	return s;
}
void GuassB()
{
	for(int i=1;i<=n;++i)
	{
		int z=i;
		while(z<=n&&!b[z][i])z++;
		if(z<=n&&z>i)w=H-w,swap(a[z],a[i]),swap(b[z],b[i]);	
		for(;dt<=n&&!b[i][i];dt++)
		{
			for(int j=1;j<=n;j++)b[i][j]=a[i][j],a[i][j]=0;
			for(int j=1;j<i;j++)
			{
				ll d=b[i][j]*Ksm(b[j][j],H-2)%H;
				for(ll k=1;k<=n;k++)a[i][k]=(a[i][k]+(H-d)*a[j][k])%H,b[i][k]=(b[i][k]+(H-d)*b[j][k])%H;
			}
		}
		ll ivi=Ksm(b[i][i],H-2);
		for(ll j=1;j<=n;j++)if(j!=i)
		{
			ll d=b[j][i]*ivi%H;
			for(ll k=1;k<=n;k++)a[j][k]=(a[j][k]+(H-d)*a[i][k])%H,b[j][k]=(b[j][k]+(H-d)*b[i][k])%H;
		}
	}
	for(int i=1;i<=n;i++)
	{
		w=w*b[i][i]%H;ll ivi=Ksm(b[i][i],H-2);
		for(int j=1;j<=n;j++)a[i][j]=a[i][j]*ivi%H;
	}
}
void GuassA()
{
	for(int i=2;i<=n;i++)
	{
		int z=i;
		while(z<=n&&!a[z][i-1])z++;
		if(z>n)continue;
		swap(a[i],a[z]);
		for(int j=1;j<=n;j++)swap(a[j][i],a[j][z]);
		ll ivi=Ksm(a[i][i-1],H-2);
		for(int j=i+1;j<=n;j++)
		{
			ll kk=a[j][i-1]*ivi%H;
			for(int k=i-1;k<=n;k++)a[j][k]=(a[j][k]-kk*a[i][k]%H+H)%H;
			for(int k=1;k<=n;k++)a[k][i]=(a[k][i]+kk*a[k][j])%H; 
		}
	}
}
void Heisenberg()
{
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=(H-a[i][j])%H;
	f[0][0]=w;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)f[i][j]=f[i-1][j-1];
		for(int k=1;k<=i;k++)
		{
			ll s=1;
			for(int j=k+1;j<=i;j++)s=s*a[j][j-1]%H;
			for(int j=0;j<=n;j++)f[i][j]=(f[i][j]-a[k][i]*f[k-1][j]%H*s%H+H)%H;
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>b[i][j];
	GuassB();GuassA();Heisenberg();
	for(int i=0;i<=n;i++)cout<<(i+dt>n?0:f[n][i+dt])<<" ";
}