QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#387233#59. Determinant of A+BzHanghang0 767ms9584kbC++141.9kb2024-04-12 10:21:562024-04-12 10:21:58

Judging History

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

  • [2024-05-05 11:54:08]
  • hack成功,自动添加数据
  • (/hack/617)
  • [2024-05-05 11:38:15]
  • hack成功,自动添加数据
  • (/hack/616)
  • [2024-04-12 10:21:58]
  • 评测
  • 测评结果:0
  • 用时:767ms
  • 内存:9584kb
  • [2024-04-12 10:21:56]
  • 提交

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];
	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])<<" ";
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 7832kb

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:

713833274 744168154 146638164 490672697 735249291 712308250 937614213 25149792 294555072 606804685 547551445 990915563 636370430 424113348 381634762 227231946 825772645 898866851 510604708 562837046 700711809 810970705 203380450 330757311 620696056 371427100 12201002 830103127 423005440 79258709 359...

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #51:

score: 0
Wrong Answer
time: 767ms
memory: 9584kb

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:

174262236 550334199 113620143 579669686 23477324 187496237 863189030 776823420 109116001 347796514 480974249 415258302 158079931 631316049 943620508 876573585 507432974 772829009 553066907 920955020 552557478 900383427 27941327 102091804 243077121 645940469 746715790 874848564 461302820 649381045 10...

result:

wrong answer 1st numbers differ - expected: '197564738', found: '174262236'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%