QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#18583#59. Determinant of A+BzBinDir0#0 380ms8376kbC++142.6kb2022-01-20 20:51:492022-05-06 01:47:28

Judging History

你现在查看的是测评时间为 2022-05-06 01:47:28 的历史记录

  • [2024-05-05 11:54:08]
  • hack成功,自动添加数据
  • (/hack/617)
  • [2024-05-05 11:38:15]
  • hack成功,自动添加数据
  • (/hack/616)
  • [2024-03-04 04:43:11]
  • 管理员手动重测本题所有提交记录
  • 测评结果:0
  • 用时:276ms
  • 内存:11072kb
  • [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-06 01:47:28]
  • 评测
  • 测评结果:0
  • 用时:380ms
  • 内存:8376kb
  • [2022-01-20 20:51:49]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
char buf[100001],*p1=buf,*p2=buf;
int n , tst;
const int mod = 998244353;
long long a[550][550] , b[550][550] , coe[550];
void swap_row( int x , int y )
{
	swap(a[x] , a[y]);
}
void swap_col( int x , int y )
{
	for(int i = 1 ; i <= n ; i++ ) swap(a[i][x] , a[i][y]);
}
void trans_row( int x , int y , long long k ) 
{
	for(int i = 1 ; i <= n ; i++ ) (a[y][i] += a[x][i] * k) %= mod;
}
void trans_col( int x , int y , long long k ) 
{
	for(int i = 1 ; i <= n ; i++ ) (a[i][y] += a[i][x] * k) %= mod;
}
struct poly
{
	long long a[550]; int siz;
	poly operator * ( const poly &x ) const
	{
		poly ans; memset(ans.a , 0 , sizeof(ans.a)); ans.siz = siz + x.siz;
		for(int i = 0 ; i <= siz ; i++ )
			for(int j = 0 ; j <= x.siz ; j++ )
				(ans.a[i + j] += a[i] * x.a[j]) %= mod;
		return ans;
	}
	poly operator + ( const poly &x ) const
	{
		poly ans; memset(ans.a , 0 , sizeof(ans.a)); ans.siz = max(siz , x.siz);
		for(int i = 0 ; i <= ans.siz ; i++ ) ans.a[i] = (a[i] + x.a[i]) % mod;
		return ans;
	}
} d[550] , e0 , e1 , ef , e;
long long exp( int a , int b )
{
	long long ans = 1 , t = a;
	while(b)
	{
		if(b & 1) ans = ans * t % mod;
		t = t * t % mod; b >>= 1;
	}
	return ans;
}
inline int read()
{
    char ch=gc(); int x=0;
    while (!(ch>='0'&&ch<='9')) ch=gc();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=gc();
    return x;
}
int main()
{
//	freopen("1.in" , "r" , stdin);
//	freopen("1.out" , "w" , stdout);
	n = read();
	for(int i = 1 ; i <= n ; i++ )
		for(int j = 1 ; j <= n ; j++ ) a[i][j] = read();
	for(int i = 2 ; i <= n ; i++ )
	{
		int id = 0;
		for(int j = i ; j <= n ; j++ )
			if(a[j][i - 1]) id = j;
		if(!id) continue;
		swap_row(i , id); swap_col(i , id);
		for(int j = i + 1 ; j <= n ; j++ )
		{
			coe[j] = exp(a[i][i - 1] , mod - 2) * a[j][i - 1] % mod;
			trans_row(i , j , mod - coe[j]); trans_col(j , i , coe[j]);
		}
	}
	d[0].siz = 0; d[0].a[0] = 1; e0 = d[0]; 
	e1.siz = 1; e1.a[1] = 1;
	ef.siz = 0; ef.a[0] = mod - 1;
	for(int i = 1 ; i <= n ; i++ )
	{
		poly noww = d[0] , las = e;
		for(int j = i ; j >= 1 ; j-- )
		{
			las.siz = 0; las.a[0] = (mod - a[j][i]) % mod;
			if(i == j) las = las + e1;
			d[i] = d[i] + ((i - j) % 2 ? ef : e0) * noww * d[j - 1] * las;
//			cerr << i << ' ' << j << ' ' << d[j - 1].a[2] << ' ' << las.a[1] << endl;
			las.siz = 0; las.a[0] = (mod - a[j][j - 1]) % mod;
			noww = noww * las;
		}
	}
	for(int i = 0 ; i <= n ; i++ ) printf("%lld " , d[n].a[i]);
	return 0;
}
/*
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 5ms
memory: 6052kb

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 647021267 447263216 768645434 364074584 660206819 843010708 519456064 777059677 598041320 646982063 988524593 234737665 453477360 618479952 410822656 963829582 100371438 708131034 268034956 686289833 481795528 61715194 180054790 351744773 484864463 772189511 927975323 827106950 428594845 401939964...

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #51:

score: 0
Wrong Answer
time: 380ms
memory: 8376kb

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%