QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#792161#9278. Linear Algebra Intensifiesbulijiojiodibuliduo#AC ✓595ms85576kbC++175.1kb2024-11-29 02:13:082024-11-29 02:13:08

Judging History

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

  • [2024-11-29 02:13:08]
  • 评测
  • 测评结果:AC
  • 用时:595ms
  • 内存:85576kb
  • [2024-11-29 02:13:08]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

template<int MOD, int RT> struct mint {
	static const int mod = MOD;
	static constexpr mint rt() { return RT; } // primitive root for FFT
	int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
	mint():v(0) {}
	mint(ll _v) { v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD);
		if (v < 0) v += MOD; }
	bool operator==(const mint& o) const {
		return v == o.v; }
	friend bool operator!=(const mint& a, const mint& b) { 
		return !(a == b); }
	friend bool operator<(const mint& a, const mint& b) { 
		return a.v < b.v; }
   
	mint& operator+=(const mint& o) { 
		if ((v += o.v) >= MOD) v -= MOD; 
		return *this; }
	mint& operator-=(const mint& o) { 
		if ((v -= o.v) < 0) v += MOD; 
		return *this; }
	mint& operator*=(const mint& o) { 
		v = int((ll)v*o.v%MOD); return *this; }
	mint& operator/=(const mint& o) { return (*this) *= inv(o); }
	friend mint pow(mint a, ll p) {
		mint ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans; }
	friend mint inv(const mint& a) { assert(a.v != 0); 
		return pow(a,MOD-2); }
		
	mint operator-() const { return mint(-v); }
	mint& operator++() { return *this += 1; }
	mint& operator--() { return *this -= 1; }
	friend mint operator+(mint a, const mint& b) { return a += b; }
	friend mint operator-(mint a, const mint& b) { return a -= b; }
	friend mint operator*(mint a, const mint& b) { return a *= b; }
	friend mint operator/(mint a, const mint& b) { return a /= b; }
};

const int MOD=998244353; 
using mi = mint<MOD,5>; // 5 is primitive root for both common mods

namespace simp {
	vector<mi> fac,ifac,invn;
	void check(int x) {
		if (fac.empty()) {
			fac={mi(1),mi(1)};
			ifac={mi(1),mi(1)};
			invn={mi(0),mi(1)};
		}
		while (SZ(fac)<=x) {
			int n=SZ(fac),m=SZ(fac)*2;
			fac.resize(m);
			ifac.resize(m);
			invn.resize(m);
			for (int i=n;i<m;i++) {
				fac[i]=fac[i-1]*mi(i);
				invn[i]=mi(MOD-MOD/i)*invn[MOD%i];
				ifac[i]=ifac[i-1]*invn[i];
			}
		}
	}
	mi gfac(int x) {
		assert(x>=0);
		check(x); return fac[x];
	}
	mi ginv(int x) {
		assert(x>0);
		check(x); return invn[x];
	}
	mi gifac(int x) {
		assert(x>=0);
		check(x); return ifac[x];
	}
	mi binom(int n,int m) {
		if (m < 0 || m > n) return mi(0);
		return gfac(n)*gifac(m)*gifac(n - m);
	}
	mi binombf(int n,int m) {
		if (m < 0 || m > n) return mi(0);
		if (m>n-m) m=n-m;
		mi p=1,q=1;
		for (int i=1;i<=m;i++) p=p*(n+1-i),q=q*i;
		return p/q;
	}
}


const int N=501000;
int f[N],n,m,id[N];
set<PII> e[N];
mi g[1111][1111];

mi det(vector<vector<mi>> f) {
	int n=SZ(f);
	mi ans=1;
	rep(i,0,n) {
		bool fg=0;
		rep(j,i,n) {
			if (f[j][i]!=0) {
				rep(k,i,n) swap(f[i][k],f[j][k]);
				if (j!=i) ans*=-1;
				fg=1;
				break;
			}
		}
		if (!fg) return 0;
		mi v=1/(-f[i][i]);
		rep(j,i+1,n) {
			mi tmp=f[j][i]*v;
			rep(k,i,n) f[j][k]=(f[j][k]+tmp*f[i][k]);
		}
	}
	rep(i,0,n) ans=ans*f[i][i];
	return ans;
}

int find(int x) {
	return f[x]==x?x:f[x]=find(f[x]);
}
int main() {
	scanf("%d%d",&n,&m);
	rep(i,0,n+1) f[i]=i;
	rep(i,0,m) {
		int u,v;
		scanf("%d%d",&u,&v);
		--u;
		f[find(u)]=find(v);
		e[u].insert(mp(v,i));
		e[v].insert(mp(u,i));
	}
	rep(i,0,n+1) if (find(i)!=find(0)) {
		puts("0");
		return 0;
	}
	if (m==n) {
		puts("1");
		return 0;
	}
	queue<int> q;
	rep(i,0,n+1) {
		if (SZ(e[i])==1) q.push(i);
	}
	while (!q.empty()) {
		auto u=q.front(); q.pop();
		auto [v,w]=*e[u].begin();
		assert(e[v].count(mp(u,w)));
		e[v].erase(mp(u,w));
		e[u].clear();
		if (SZ(e[v])==1) {
			q.push(v);
		}
	}
	VI pv;
	int c2=0;
	rep(i,0,n+1) {
		if (SZ(e[i])>=3) {
			pv.pb(i);
			id[i]=SZ(pv);
		}
		if (SZ(e[i])==2) c2++;
	}
	if (pv.empty()) {
		printf("%d\n",c2);
		return 0;
	}
	mi ans=1;
	VI selfv;
	auto addeg=[&](int u,int v,int w) {
		u=id[u]-1; v=id[v]-1;
		selfv.pb(w);
		if (u==v) return;
		mi iw=mi(1)/mi(w);
		g[u][u]+=iw;
		g[u][v]-=iw;
	};
	function<void(int,int,int,int)> dfs=[&](int u,int par,int dep,int rt) {
		if (dep>0&&id[u]) {
			addeg(rt,u,dep);
			return;
		}
		for (auto [v,w]:e[u]) if (w!=par) {
			dfs(v,w,dep+1,rt);
		}
	};
	for (auto u:pv) dfs(u,-1,0,u);
	vector<vector<mi>> ff;
	rep(i,1,SZ(pv)) ff.pb(vector<mi>(g[i]+1,g[i]+SZ(pv)));
	ans=ans*det(ff);
	sort(all(selfv));
	for (int i=0;i<SZ(selfv);i+=2) ans=ans*selfv[i];
	printf("%d\n",(int)ans);
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 6ms
memory: 34708kb

input:

3 4
1 2
2 3
1 2
3 3

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 8ms
memory: 34692kb

input:

1 1
1 1

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 4ms
memory: 34540kb

input:

1 10
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1

output:

10

result:

ok 1 number(s): "10"

Test #4:

score: 0
Accepted
time: 0ms
memory: 35164kb

input:

2 1
1 2

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 0ms
memory: 35116kb

input:

2 2
1 2
1 1

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 4ms
memory: 35848kb

input:

2 3
1 1
2 2
1 2

output:

3

result:

ok 1 number(s): "3"

Test #7:

score: 0
Accepted
time: 0ms
memory: 34808kb

input:

12 23
10 12
6 12
3 6
3 4
5 12
10 10
10 11
9 9
8 12
4 12
1 9
4 9
2 2
10 11
5 12
8 12
9 9
1 9
6 12
10 10
2 2
3 6
3 4

output:

3072

result:

ok 1 number(s): "3072"

Test #8:

score: 0
Accepted
time: 0ms
memory: 35712kb

input:

2 10
1 2
2 2
1 1
1 1
1 2
1 1
1 2
2 2
2 2
1 2

output:

33

result:

ok 1 number(s): "33"

Test #9:

score: 0
Accepted
time: 0ms
memory: 35324kb

input:

9 20
4 6
9 9
8 9
3 3
2 8
6 8
9 9
2 6
2 8
1 1
2 4
1 2
5 9
1 3
2 7
1 3
1 6
2 3
2 8
2 6

output:

3696

result:

ok 1 number(s): "3696"

Test #10:

score: 0
Accepted
time: 0ms
memory: 36252kb

input:

109 245
6 57
29 81
21 76
21 76
36 44
53 71
29 29
43 78
1 12
26 50
3 100
8 84
30 103
1 21
61 76
19 78
37 55
78 79
15 64
18 53
40 82
28 66
14 40
30 63
53 85
64 106
1 95
87 106
14 36
8 84
30 64
40 82
9 62
29 50
68 87
48 64
63 105
1 17
15 66
26 50
1 48
50 75
52 75
10 10
74 106
9 75
65 102
91 103
12 83
6...

output:

589921054

result:

ok 1 number(s): "589921054"

Test #11:

score: 0
Accepted
time: 0ms
memory: 34820kb

input:

100 100
46 100
45 92
86 97
72 78
44 79
35 97
31 92
88 93
49 89
12 56
7 63
58 86
51 70
81 100
33 37
29 94
12 38
31 53
26 90
77 96
10 88
26 69
44 90
6 48
37 47
60 77
32 42
40 41
50 83
83 90
95 100
21 33
17 62
12 91
59 68
63 82
11 60
48 98
5 47
56 60
1 95
38 52
25 66
51 59
4 33
95 96
55 74
26 93
25 68
...

output:

1

result:

ok 1 number(s): "1"

Test #12:

score: 0
Accepted
time: 4ms
memory: 35156kb

input:

122 123
4 37
48 73
21 96
68 84
43 94
11 36
38 113
40 108
65 81
10 111
6 19
80 92
37 40
40 122
60 113
2 19
29 31
26 75
33 68
27 69
51 65
17 90
88 112
56 68
46 46
83 110
25 80
14 38
101 108
16 41
64 89
19 88
76 87
26 79
51 90
107 119
7 17
71 100
17 59
14 105
15 26
22 95
113 117
22 91
19 99
57 119
42 5...

output:

123

result:

ok 1 number(s): "123"

Test #13:

score: 0
Accepted
time: 9ms
memory: 34688kb

input:

99 200
53 74
10 80
6 73
73 81
7 37
81 93
12 55
6 40
24 96
86 89
48 89
17 75
20 65
18 52
36 89
8 24
29 33
53 72
28 45
27 35
38 73
11 41
74 76
73 86
87 93
11 73
4 19
80 88
11 80
12 21
13 86
69 78
3 18
32 47
3 49
50 93
30 60
8 19
26 70
1 62
9 96
58 94
25 35
42 91
61 70
13 96
10 44
57 73
19 85
16 37
81 ...

output:

560526429

result:

ok 1 number(s): "560526429"

Test #14:

score: 0
Accepted
time: 32ms
memory: 35692kb

input:

3000 3300
203 2193
755 2277
2141 2736
1115 1127
82 1944
573 2600
1063 1949
375 1712
395 999
950 1690
52 1226
560 2924
83 1464
1504 2104
10 986
64 1331
1631 1755
573 2344
1615 1737
2414 2804
480 2113
2174 2909
666 2914
156 1588
611 1533
528 1285
1004 2763
19 80
73 1954
777 1297
2116 2117
186 847
1056...

output:

855511535

result:

ok 1 number(s): "855511535"

Test #15:

score: 0
Accepted
time: 291ms
memory: 82736kb

input:

500000 500000
106843 246711
220148 499250
169638 287414
348384 439218
464123 485715
242531 404366
304063 470177
158965 188123
11671 470956
441213 450178
229736 319036
393409 440552
204883 324026
476519 481812
444616 468853
65586 178690
234265 263137
434457 470186
391493 410684
329022 357803
139095 4...

output:

1

result:

ok 1 number(s): "1"

Test #16:

score: 0
Accepted
time: 0ms
memory: 35856kb

input:

500000 1
301721 361047

output:

0

result:

ok 1 number(s): "0"

Test #17:

score: 0
Accepted
time: 289ms
memory: 82844kb

input:

500000 500000
98619 388571
341253 371055
201469 217888
92958 138959
14275 185016
76593 118908
448437 499659
101559 211959
162147 291039
114239 445451
218665 248802
3153 359183
256945 314214
393034 477015
204725 291777
421118 494553
439455 467768
71748 416919
203928 245846
430083 470965
354933 476142...

output:

0

result:

ok 1 number(s): "0"

Test #18:

score: 0
Accepted
time: 257ms
memory: 82688kb

input:

500000 500000
177093 360397
302589 367660
85299 288630
199827 242302
141963 328163
135504 138139
198476 308433
228887 382116
168447 190268
5588 231484
281079 307027
195125 362060
185089 293372
22610 208438
69594 330179
146715 479740
200305 464094
307384 448176
298448 439901
116418 402473
219948 4371...

output:

1

result:

ok 1 number(s): "1"

Test #19:

score: 0
Accepted
time: 293ms
memory: 82796kb

input:

499700 500000
199312 363387
28170 45801
218790 419838
88326 324416
118422 432158
153235 242162
11579 25299
223249 486090
163817 497246
187168 389868
95567 450717
6783 57079
266046 342045
426586 484374
31227 41797
53367 462151
221528 339573
183106 374349
99554 405978
191158 417963
215600 248217
16628...

output:

0

result:

ok 1 number(s): "0"

Test #20:

score: 0
Accepted
time: 583ms
memory: 83532kb

input:

499700 500000
21935 291497
3024 478103
245079 313731
289382 445058
7336 28195
78312 277188
1478 444596
110770 303251
305814 488077
392299 458444
49934 365673
98804 210611
284717 482990
169781 473469
80921 280809
2832 31209
117964 355575
80469 280739
120148 145950
99614 451361
139980 305651
273769 47...

output:

780759157

result:

ok 1 number(s): "780759157"

Test #21:

score: 0
Accepted
time: 244ms
memory: 82904kb

input:

499999 500000
337206 367714
166297 312794
307170 414738
110332 372626
212936 344573
168963 205236
160790 386652
365877 467290
72766 300544
174237 422273
101731 241073
398746 416888
456126 491059
210317 263195
109345 295637
231932 408374
52853 329207
334163 388929
125157 486076
197084 206788
292973 3...

output:

500000

result:

ok 1 number(s): "500000"

Test #22:

score: 0
Accepted
time: 384ms
memory: 74140kb

input:

400025 400325
347626 347915
4781 209476
30074 115935
143154 195884
3575 344617
247862 261061
135176 255423
178268 222368
247067 286708
340084 343728
188171 281733
41990 240994
255351 374129
165903 171225
9259 185918
137286 212423
126850 376328
62992 189751
34847 36098
8890 163372
106962 373854
44874...

output:

539971491

result:

ok 1 number(s): "539971491"

Test #23:

score: 0
Accepted
time: 284ms
memory: 64588kb

input:

300109 300400
6455 97886
125279 267449
21281 149096
216607 281358
46405 175071
12597 165532
10905 37179
125605 180980
120823 167319
90076 114751
190919 266219
107082 251302
109232 140660
128428 290381
42195 272858
131018 164771
22552 238723
229759 290134
55034 182192
37207 108904
4740 23439
20378 18...

output:

882836819

result:

ok 1 number(s): "882836819"

Test #24:

score: 0
Accepted
time: 500ms
memory: 83664kb

input:

499999 500000
47849 283106
16634 475213
1354 212127
123209 162917
271573 285753
338710 487415
160493 268905
237678 347030
132405 308987
130542 314305
343555 386154
142357 300413
100571 197171
43107 62217
142052 435822
86940 157935
202074 254928
39505 184155
55872 351366
42763 363981
182118 360911
68...

output:

2

result:

ok 1 number(s): "2"

Test #25:

score: 0
Accepted
time: 491ms
memory: 82844kb

input:

490100 490400
156712 369932
385830 470289
422686 451652
211899 262956
147118 481327
122259 164629
334205 483114
163904 402960
338978 484787
283943 460768
57259 267931
75630 163562
178413 449536
357293 395320
107150 197041
82435 265012
379336 474275
389629 468275
297678 336271
101433 247320
18671 170...

output:

418567388

result:

ok 1 number(s): "418567388"

Test #26:

score: 0
Accepted
time: 438ms
memory: 79200kb

input:

450004 450304
32697 266011
425030 429101
316811 401885
31452 257565
35162 192946
30486 291145
35013 345381
345937 399617
147064 304884
234469 347087
104761 122260
73712 324726
118741 271448
29319 57779
120877 341625
234063 274395
35730 154243
25603 208972
256148 381349
155824 206927
25196 56453
1763...

output:

620981594

result:

ok 1 number(s): "620981594"

Test #27:

score: 0
Accepted
time: 486ms
memory: 82892kb

input:

490009 490309
134383 158561
156596 248554
191181 207375
39398 414704
31355 371571
240548 438664
165053 318372
10295 107721
182673 223226
159451 448204
71681 113596
172222 405158
144438 339534
101556 358403
29436 350332
32362 84576
57221 112349
108311 202303
11882 476684
484463 489184
224724 282924
2...

output:

566276003

result:

ok 1 number(s): "566276003"

Test #28:

score: 0
Accepted
time: 490ms
memory: 84076kb

input:

490298 490598
210225 404229
2951 362841
331483 485378
6529 480859
167203 226530
1488 177457
316845 346894
103830 163223
150926 194319
201991 252388
133043 370380
245639 248027
116641 417488
121251 311507
75808 241313
1348 331818
89022 181089
339919 446073
169128 200082
57271 59144
64237 424354
55042...

output:

343584604

result:

ok 1 number(s): "343584604"

Test #29:

score: 0
Accepted
time: 559ms
memory: 82928kb

input:

494866 495166
99825 232759
23420 274946
118866 338316
31631 397272
63794 348843
252078 420375
268070 449517
49092 417443
101604 162354
131228 170520
162201 369566
151474 439659
138548 402129
263855 444394
294741 440276
99438 212690
307 417110
405833 410540
299797 300068
70745 259694
287090 287906
86...

output:

23165905

result:

ok 1 number(s): "23165905"

Test #30:

score: 0
Accepted
time: 569ms
memory: 82616kb

input:

469734 470032
24842 37234
179928 432668
310523 336074
207102 290436
144971 226528
239653 437703
196160 405776
25708 266051
156570 443810
87313 314748
83805 175806
282070 381371
218911 243720
74897 80691
103233 276556
116766 172090
24668 272161
6529 98246
123656 378790
241432 446852
191128 324209
163...

output:

195465029

result:

ok 1 number(s): "195465029"

Test #31:

score: 0
Accepted
time: 488ms
memory: 81208kb

input:

469635 469935
333845 352288
199361 346371
129944 208644
61813 329773
139360 242410
253496 406352
43353 412465
130631 192408
192634 423222
130374 322955
83713 441275
270897 464813
412276 467854
412007 469177
185122 261975
111619 180110
292090 415208
36210 447557
15978 348190
58491 405604
154543 34094...

output:

760746584

result:

ok 1 number(s): "760746584"

Test #32:

score: 0
Accepted
time: 595ms
memory: 85576kb

input:

499700 500000
358992 469294
340849 470072
189441 384117
172296 337350
131713 272631
67378 370126
79109 92814
98012 268753
232750 389178
136053 489605
57409 59870
90630 101473
206752 447545
58837 344696
249290 256036
99843 216684
339015 429470
432 35563
8275 436125
122868 401278
264824 324538
310668 ...

output:

253203006

result:

ok 1 number(s): "253203006"

Test #33:

score: 0
Accepted
time: 501ms
memory: 84612kb

input:

499039 499339
159987 251448
124976 310641
106470 220204
362424 484869
340457 433213
21659 102293
273684 325859
116000 360085
42835 443988
110794 227293
175656 495481
72767 188171
110287 123811
201406 239266
34357 220978
117450 172353
215053 259162
360436 469884
110074 277892
120457 342858
141315 171...

output:

71926140

result:

ok 1 number(s): "71926140"

Extra Test:

score: 0
Extra Test Passed