QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#18580#495. 特征多项式BinDir0#0 563ms8196kbC++142.7kb2022-01-20 20:31:012022-05-06 01:47:12

Judging History

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

  • [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:12]
  • 评测
  • 测评结果:0
  • 用时:563ms
  • 内存:8196kb
  • [2022-01-20 20:31:01]
  • 提交

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] , 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) %= 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) %= 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) %= 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 - 1 ; 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]); 
		}
		for(int j = i + 1 ; j <= n ; 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;
}
/*
*/

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

input:

50
266912498 835091017 452080669 685381424 269707314 292908762 277505221 781233421 510658789 799543577 844885899 736245256 651479261 844896506 567470542 729489183 865380130 158739155 271515176 36971482 560309217 933384827 499620370 303835488 898526954 987576590 241842859 41182893 341293849 605213418...

output:

223946444 555485025 663027584 721806207 316659808 59280796 289972345 846204107 49650325 56466036 408088281 773622246 981113242 669778202 28623552 533497148 2576909 962325552 562404394 400126626 811129906 411883422 186902852 133887702 880811687 450241457 330027307 850259672 448337209 156449304 563545...

result:

wrong answer 1st numbers differ - expected: '488909123', found: '223946444'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 563ms
memory: 8196kb

input:

500
912067299 560421914 613266377 676357217 299801919 277177164 278302771 810389156 943836886 639998245 855554810 784105751 403876660 750427762 374514286 219539473 45338811 881611774 125191025 37880987 91597910 672490636 695938784 118178926 898788752 890452808 971253057 929997223 751058722 706074011...

output:

185323537 978703987 255534351 498329715 183907962 885961522 386300595 190354027 927437597 193901394 32470124 927979132 164285466 273926778 735516562 483197383 596008596 636539116 513899951 717356540 816385270 243796633 604916137 823490383 377757694 745481079 918812368 883451229 425851299 352061580 2...

result:

wrong answer 1st numbers differ - expected: '411952917', found: '185323537'