QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#182744#4921. 匹配计数Crysfly100 ✓228ms7900kbC++203.5kb2023-09-18 14:57:522023-09-18 14:57:52

Judging History

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

  • [2023-09-18 14:57:52]
  • 评测
  • 测评结果:100
  • 用时:228ms
  • 内存:7900kb
  • [2023-09-18 14:57:52]
  • 提交

answer

// what is matter? never mind. 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}
 
#define mod 998244353
struct modint{
	int x;
	modint(int o=0){x=o;}
	modint &operator = (int o){return x=o,*this;}
	modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
	modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
	modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
	modint &operator ^=(int b){
		modint a=*this,c=1;
		for(;b;b>>=1,a*=a)if(b&1)c*=a;
		return x=c.x,*this;
	}
	modint &operator /=(modint o){return *this *=o^=mod-2;}
	friend modint operator +(modint a,modint b){return a+=b;}
	friend modint operator -(modint a,modint b){return a-=b;}
	friend modint operator *(modint a,modint b){return a*=b;}
	friend modint operator /(modint a,modint b){return a/=b;}
	friend modint operator ^(modint a,int b){return a^=b;}
	friend bool operator ==(modint a,int b){return a.x==b;}
	friend bool operator !=(modint a,int b){return a.x!=b;}
	bool operator ! () {return !x;}
	modint operator - () {return x?mod-x:0;}
	bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}

vector<modint> fac,ifac,iv;
inline void initC(int n)
{
	if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
	int m=iv.size(); ++n;
	if(m>=n)return;
	iv.resize(n),fac.resize(n),ifac.resize(n);
	For(i,m,n-1){
		iv[i]=iv[mod%i]*(mod-mod/i);
		fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
	}
}
inline modint C(int n,int m){
	if(m<0||n<m)return 0;
	return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 200005
#define inf 0x3f3f3f3f

int n,c[maxn],a[maxn];
modint f[maxn];

bitset<4005>bs[4005],tmp,tmp1;
bool del[4005];
modint solve(int n)
{
	modint res=1;
	For(i,1,n)del[i]=0;
	For(i,1,n){
		if(del[i])continue;
		tmp.reset();
		int v=0,o=0;
		For(j,i+1,n)
			if(bs[i][j]&&!del[j]){
				if(!v)v=j;
				o+=bs[i][j],tmp[j]=1;
			}
		if(!o){
			if(bs[i][i])return 0;
			res*=2;
			continue;
		}
		res*=2;
		tmp1.reset();
		tmp[v]=tmp[i]=0;
		if(bs[v][v]){
			if(bs[i][i]) res=-res;
			For(j,i+1,n) if(bs[i][j] && j!=v) bs[j][j]=bs[j][j]^1;
		}
		For(j,i+1,n){
			if(bs[v][j]){
				if(j!=v && !del[j]) tmp1[j]=1;
				if(bs[v][j]&&bs[i][i]) bs[j][j]=bs[j][j]^1;
			}
		}
		For(j,1,n)if(tmp1[j]) bs[j]^=tmp;
		For(j,1,n)if(tmp[j]) bs[j]^=tmp1;
		For(j,1,n)if(tmp[j]&&tmp1[j]) bs[j][j]=bs[j][j]^1;
		del[v]=1;
	}
	return res;
}

void work()
{
	n=read();
	For(i,1,n+n)bs[i].reset(),c[i]=0;
	For(i,1,n)a[i]=read(),++c[a[i]],bs[a[i]+n][i]=bs[i][a[i]+n]=1;
	For(i,1,n)For(j,i+1,n)bs[i][j]=bs[j][i]=(a[i]>a[j]);
	modint res=solve(n+n);
	res*=qpow((mod+1)/2,n);
	modint sum=1;
	For(i,1,n)sum*=f[c[i]];
	res=(res+sum)*((mod+1)/2);
	cout<<res.x<<"\n";
}

signed main()
{
	f[0]=f[1]=1;
	For(i,2,4000)f[i]=f[i-1]+f[i-2]*(i-1);
	int T=read();
	while(T--)work();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5
Accepted
time: 1ms
memory: 5692kb

input:

5
11
4 1 9 11 7 10 6 9 11 6 5
13
2 2 1 2 1 2 1 1 2 1 1 2 1
12
6 1 6 1 4 5 6 2 2 1 6 4
12
2 1 2 4 2 1 4 1 3 2 2 4
13
2 3 1 4 3 3 1 3 1 3 1 1 3

output:

4
8880
88
224
1020

result:

ok 5 number(s): "4 8880 88 224 1020"

Test #2:

score: 5
Accepted
time: 1ms
memory: 6032kb

input:

5
13
4 4 5 2 3 2 2 5 1 3 4 1 5
11
1 1 1 1 1 1 1 1 1 1 1
13
1 1 2 2 2 1 1 2 2 2 2 1 2
11
3 3 3 1 2 3 2 1 1 2 2
12
2 5 6 1 5 6 1 4 5 6 4 3

output:

160
18360
10188
232
28

result:

ok 5 number(s): "160 18360 10188 232 28"

Test #3:

score: 5
Accepted
time: 45ms
memory: 6940kb

input:

5
1986
286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 286 2...

output:

319366059
289574279
419748641
495397644
522687460

result:

ok 5 number(s): "319366059 289574279 419748641 495397644 522687460"

Test #4:

score: 5
Accepted
time: 44ms
memory: 7300kb

input:

5
1987
989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 989 9...

output:

355799162
110832579
987068911
987068911
355799162

result:

ok 5 number(s): "355799162 110832579 987068911 987068911 355799162"

Test #5:

score: 5
Accepted
time: 175ms
memory: 6784kb

input:

5
2000
9 7 5 10 3 5 6 10 2 5 6 7 10 7 5 5 10 9 4 4 5 1 2 10 7 5 6 1 2 4 8 3 1 1 2 6 4 5 1 7 3 4 3 2 9 9 5 6 4 4 5 10 1 6 6 2 8 6 6 8 10 2 8 7 2 6 3 5 2 3 6 5 4 2 7 3 2 5 1 3 10 10 8 7 1 7 2 7 2 3 8 4 4 8 6 1 8 7 1 4 6 5 6 5 4 7 4 9 2 1 1 1 3 4 6 6 8 6 7 1 8 6 10 4 6 7 10 6 8 8 9 5 9 7 3 10 2 9 9 6 3...

output:

16972030
189898805
510912000
524622063
20658656

result:

ok 5 number(s): "16972030 189898805 510912000 524622063 20658656"

Test #6:

score: 5
Accepted
time: 174ms
memory: 6320kb

input:

5
1987
9 10 3 9 1 9 2 8 2 1 9 9 6 9 1 2 10 10 8 7 5 6 2 5 1 7 10 4 4 3 6 2 2 6 3 8 9 8 9 3 2 6 5 9 2 5 6 6 1 6 1 9 8 6 9 10 10 5 8 3 5 4 4 6 6 7 4 2 2 10 9 8 10 4 8 7 9 8 7 3 6 3 9 4 3 6 9 2 10 4 2 4 3 5 7 8 10 5 6 3 7 5 6 5 7 1 10 4 6 5 6 1 1 10 9 8 10 3 5 7 10 2 5 2 9 7 3 9 6 2 9 6 9 4 6 7 7 5 5 3...

output:

354126359
394980261
163057634
618360435
187546371

result:

ok 5 number(s): "354126359 394980261 163057634 618360435 187546371"

Test #7:

score: 5
Accepted
time: 171ms
memory: 6392kb

input:

5
1996
9 3 3 1 9 1 5 9 7 2 9 6 2 9 10 6 6 10 2 8 10 8 3 3 7 3 10 8 5 4 6 7 5 4 1 8 5 3 7 6 4 8 7 10 6 10 10 9 4 7 6 8 1 8 8 9 9 5 4 5 5 1 9 7 10 9 4 4 2 3 4 8 6 5 2 9 6 7 8 9 10 2 5 8 9 1 5 5 9 4 9 6 3 5 1 7 5 8 8 1 1 7 4 10 9 3 1 8 4 4 6 3 1 5 2 5 9 3 1 2 10 3 9 10 10 2 4 3 7 9 9 6 2 6 8 9 6 1 10 8...

output:

523274896
830856351
906370846
831611294
878000734

result:

ok 5 number(s): "523274896 830856351 906370846 831611294 878000734"

Test #8:

score: 5
Accepted
time: 171ms
memory: 6936kb

input:

5
1992
6 6 6 4 6 2 9 10 4 3 9 1 3 6 6 4 1 9 4 10 1 1 6 1 1 2 8 3 1 4 10 4 7 4 4 8 1 7 4 8 5 10 1 10 3 9 5 10 7 3 2 7 10 2 6 3 5 9 3 9 4 9 3 9 8 10 3 6 1 4 7 6 3 5 4 10 5 5 9 1 6 10 8 3 5 4 7 7 10 5 4 8 2 4 3 8 9 8 9 4 2 4 10 5 1 2 2 6 3 2 2 2 2 6 9 6 5 1 9 2 4 8 10 7 9 8 10 7 7 10 5 9 3 5 8 4 10 6 7...

output:

645261509
178269024
685114384
599620392
756516475

result:

ok 5 number(s): "645261509 178269024 685114384 599620392 756516475"

Test #9:

score: 5
Accepted
time: 172ms
memory: 6484kb

input:

5
1993
4 4 10 7 3 6 7 2 7 3 7 8 1 9 4 7 5 7 9 10 10 4 2 1 10 4 2 8 3 4 5 1 9 6 1 5 2 8 6 6 8 3 3 1 4 8 1 10 4 6 7 10 8 9 6 5 9 10 7 3 9 10 6 6 2 1 5 8 6 8 8 8 5 1 5 9 7 7 7 6 10 8 7 7 10 4 3 5 1 1 8 8 6 5 8 6 8 2 6 7 5 6 9 7 4 5 3 10 8 9 7 2 1 5 8 9 4 4 3 7 4 4 6 9 10 4 7 7 6 8 9 1 9 9 10 2 10 5 6 8...

output:

118938038
105647701
267019695
435628826
169460547

result:

ok 5 number(s): "118938038 105647701 267019695 435628826 169460547"

Test #10:

score: 5
Accepted
time: 170ms
memory: 6996kb

input:

5
1982
2 1 2 6 9 5 5 2 10 10 3 8 10 3 2 6 9 5 7 4 5 3 10 3 2 6 3 5 9 9 1 5 3 7 1 10 10 8 6 9 7 6 1 9 4 10 5 1 5 4 3 7 2 4 6 2 10 2 10 8 7 8 2 6 2 3 5 6 4 10 2 10 5 3 9 8 3 2 1 8 9 2 5 8 9 4 10 7 3 1 5 2 9 8 7 6 1 4 4 10 4 1 8 8 9 10 8 10 3 4 9 3 8 2 2 1 10 4 8 2 1 6 2 3 6 8 2 3 2 10 1 6 5 3 3 1 8 3 ...

output:

157217016
538678496
670551229
776297105
313163408

result:

ok 5 number(s): "157217016 538678496 670551229 776297105 313163408"

Test #11:

score: 5
Accepted
time: 5ms
memory: 5960kb

input:

5
280
9 9 3 15 12 18 8 2 18 18 8 3 15 14 7 3 18 16 11 13 1 12 14 14 2 15 15 14 2 6 5 3 9 10 9 2 3 7 18 3 12 1 4 16 5 18 2 4 14 13 1 14 5 2 16 18 12 13 11 15 14 13 15 8 2 14 16 17 17 13 8 9 7 2 8 9 6 13 11 8 16 1 16 4 5 17 17 5 10 16 15 15 13 8 4 18 6 18 8 14 4 15 11 12 17 18 12 3 8 10 12 15 6 16 17 ...

output:

753377949
111970904
625095825
514722636
367155906

result:

ok 5 number(s): "753377949 111970904 625095825 514722636 367155906"

Test #12:

score: 5
Accepted
time: 6ms
memory: 5928kb

input:

5
288
19 10 7 10 2 8 17 2 15 11 1 9 16 20 7 2 9 14 4 7 8 1 1 11 4 1 6 12 10 5 17 4 8 16 3 8 16 20 17 18 10 5 11 14 9 8 9 11 19 13 18 20 2 1 10 11 17 12 3 12 4 6 20 14 15 16 12 9 5 17 9 7 11 18 8 4 6 19 7 16 15 12 14 16 2 19 2 15 9 13 11 19 10 6 7 14 18 4 4 14 11 5 18 16 8 2 17 20 11 11 18 10 16 15 1...

output:

877401013
715909111
782807293
432070196
983664732

result:

ok 5 number(s): "877401013 715909111 782807293 432070196 983664732"

Test #13:

score: 5
Accepted
time: 6ms
memory: 5960kb

input:

5
281
15 1 5 13 10 9 9 5 12 2 12 15 6 15 9 10 10 4 3 1 6 13 5 2 16 3 8 16 2 11 8 6 8 15 9 14 7 1 5 1 16 12 10 15 6 13 2 1 13 3 3 13 3 3 8 9 3 15 15 4 7 8 5 2 14 1 15 6 15 6 10 5 13 13 5 8 11 11 13 2 2 10 9 3 16 10 8 12 3 6 8 4 7 8 8 11 12 15 16 13 11 16 15 9 10 11 5 2 15 16 3 5 1 2 15 12 5 10 12 3 8...

output:

271415502
830431537
408103586
598881343
564923875

result:

ok 5 number(s): "271415502 830431537 408103586 598881343 564923875"

Test #14:

score: 5
Accepted
time: 5ms
memory: 5916kb

input:

5
282
8 10 3 15 14 5 13 12 2 17 12 2 3 3 3 3 5 10 4 4 5 6 12 12 16 12 14 5 6 5 10 13 8 6 5 9 13 11 3 4 10 17 3 15 3 16 3 4 3 15 14 8 17 6 9 4 14 3 2 12 1 8 13 10 10 9 13 3 7 14 17 6 3 7 6 6 3 14 8 12 15 6 2 3 4 14 16 9 10 16 4 2 14 10 3 5 13 5 11 15 16 9 1 13 9 13 4 9 13 10 5 5 15 5 13 8 14 7 17 11 ...

output:

22603617
541522535
902092879
743001293
518833861

result:

ok 5 number(s): "22603617 541522535 902092879 743001293 518833861"

Test #15:

score: 5
Accepted
time: 197ms
memory: 7396kb

input:

5
1900
41 13 29 21 31 26 37 32 8 24 27 24 2 20 33 33 18 40 38 44 21 40 30 45 31 39 32 41 34 13 6 38 36 39 47 14 26 27 14 35 9 23 7 15 4 26 39 44 16 24 44 36 46 14 32 43 32 22 6 28 11 16 43 10 10 2 24 12 9 26 16 25 30 33 9 7 44 32 46 31 41 23 10 38 37 31 36 18 41 11 20 14 18 30 27 32 31 13 31 40 39 4...

output:

332471774
388529708
88551220
829016826
22653333

result:

ok 5 number(s): "332471774 388529708 88551220 829016826 22653333"

Test #16:

score: 5
Accepted
time: 190ms
memory: 6456kb

input:

5
1999
21 14 5 7 15 10 31 16 12 30 43 41 27 38 19 37 15 27 25 25 16 41 35 8 14 27 22 14 24 8 2 34 12 19 31 38 47 29 6 16 31 13 3 30 39 19 26 21 35 9 7 11 37 11 10 22 39 9 19 36 2 10 27 28 14 19 3 21 43 41 32 22 48 3 40 30 17 3 22 37 6 39 20 18 42 11 25 14 34 33 1 40 47 20 29 27 37 41 42 46 12 22 22 ...

output:

353685051
823956386
662614759
870109968
88551220

result:

ok 5 number(s): "353685051 823956386 662614759 870109968 88551220"

Test #17:

score: 5
Accepted
time: 228ms
memory: 6324kb

input:

5
1925
1118 1447 1229 694 1207 106 826 856 1352 1116 434 549 667 564 613 340 380 476 45 835 623 505 1536 593 1345 931 842 1518 1512 1244 648 527 1386 52 813 441 664 694 1455 893 381 136 1553 7 236 907 824 795 233 768 1489 551 431 932 1366 608 1290 1337 473 521 1386 849 970 1287 711 1505 1199 1176 29...

output:

741937234
88551220
305246165
512372913
249620932

result:

ok 5 number(s): "741937234 88551220 305246165 512372913 249620932"

Test #18:

score: 5
Accepted
time: 201ms
memory: 6792kb

input:

5
1998
31 21 6 18 5 11 10 38 43 46 1 27 5 11 43 31 29 41 12 10 28 19 14 31 35 14 6 46 34 38 18 21 14 45 34 15 30 25 41 19 40 21 20 26 30 11 3 35 18 24 42 4 35 4 1 42 3 13 19 12 19 41 43 36 15 38 46 39 28 9 34 46 19 24 46 45 4 27 37 1 46 43 7 4 46 6 46 44 9 39 24 15 14 46 26 39 14 6 10 1 31 22 21 46 ...

output:

141403204
72083046
440573186
880980549
527162143

result:

ok 5 number(s): "141403204 72083046 440573186 880980549 527162143"

Test #19:

score: 5
Accepted
time: 220ms
memory: 7900kb

input:

5
1952
24 36 19 25 33 24 1 39 4 39 9 38 13 4 21 37 24 29 32 2 7 17 25 14 38 27 12 39 3 6 25 14 9 34 33 19 7 6 30 37 5 6 34 6 31 31 35 7 29 24 37 40 25 28 1 34 18 37 37 40 33 3 3 35 35 13 7 14 15 31 3 26 24 12 29 11 12 14 19 10 6 5 22 11 25 12 13 18 6 26 35 34 24 23 4 38 22 5 12 36 9 2 16 14 22 35 1 ...

output:

476822210
218601714
409229461
88551220
569386196

result:

ok 5 number(s): "476822210 218601714 409229461 88551220 569386196"

Test #20:

score: 5
Accepted
time: 204ms
memory: 7744kb

input:

5
2000
500 499 498 497 496 495 494 493 492 491 490 489 488 487 486 485 484 483 482 481 480 479 478 477 476 475 474 473 472 471 470 469 468 467 466 465 464 463 462 461 460 459 458 457 456 455 454 453 452 451 450 449 448 447 446 445 444 443 442 441 440 439 438 437 436 435 434 433 432 431 430 429 428 4...

output:

88551220
88551220
88551220
88551220
88551220

result:

ok 5 number(s): "88551220 88551220 88551220 88551220 88551220"