QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#387213#59. Determinant of A+BzHanghang0 700ms9532kbC++141.8kb2024-04-12 09:46:412024-04-12 09:46:43

Judging History

你现在查看的是最新测评结果

  • [2024-05-05 11:54:08]
  • hack成功,自动添加数据
  • (/hack/617)
  • [2024-05-05 11:38:15]
  • hack成功,自动添加数据
  • (/hack/616)
  • [2024-04-12 09:46:43]
  • 评测
  • 测评结果:0
  • 用时:700ms
  • 内存:9532kb
  • [2024-04-12 09:46:41]
  • 提交

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++)for(ll k=1,d=b[i][j]*Ksm(b[j][j],H-2);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;
		}
		for(ll j=1,ivi=Ksm(b[i][i],H-2);j<=n;j++)if(j!=i)for(ll k=1,d=b[j][i]*ivi%H;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()
{
	f[0][0]=w;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;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<=i;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])<<" ";
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 7808kb

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:

0 562160817 175535903 443284469 223039496 939899989 587204040 942943536 397840744 842731377 415872342 520505487 352386530 945001753 485943331 858810352 914586784 453357017 464494428 598270861 144143987 473246236 938746522 906380732 401839366 164729860 170911469 365645719 939655150 483037434 82556429...

result:

wrong answer 2nd numbers differ - expected: '436083536', found: '562160817'

Subtask #2:

score: 0
Wrong Answer

Test #51:

score: 0
Wrong Answer
time: 700ms
memory: 9532kb

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:

197564738 221906216 450758758 912143361 615937344 439080439 131406243 596624366 648971457 84873458 305548921 604958391 915689006 392822469 878026660 423815308 573319599 633753244 147359659 721178504 558700076 392507268 416281513 294228377 726983797 792811621 98536178 184387414 885823882 819054346 66...

result:

wrong answer 2nd numbers differ - expected: '776338137', found: '221906216'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%