QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#402390 | #4921. 匹配计数 | Diu | 100 ✓ | 334ms | 5484kb | C++14 | 2.2kb | 2024-04-30 14:58:39 | 2024-04-30 14:58:40 |
Judging History
answer
#include<bits/stdc++.h>
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
using namespace std;
const int N=4010,p=998244353,inv2=p+1>>1;
int T,n,a[N],t[N],c[N];
int fac[N],ifac[N],h[N];
bitset<N> g[N],del;
int qpow(int x,int y=p-2){
int m=1;
for(;y;y>>=1,x=1ll*x*x%p)if(y&1)m=1ll*m*x%p;
return m;
}
int C(int n,int m){
return 1ll*fac[n]*ifac[m]%p*ifac[n-m]%p;
}
void init(int n){
fac[0]=1;
for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%p;
ifac[n]=qpow(fac[n]);
for(int i=n-1;i>=0;i--)ifac[i]=1ll*ifac[i+1]*(i+1)%p;
for(int i=0;i<=n;i++){
int mul=1;
for(int j=0;j<=i;j+=2)h[i]=(h[i]+1ll*C(i,j)*mul%p)%p,mul=1ll*mul*(j+1)%p;
}
}
void add(int &x,int y){x+=y;if(x>=p)x-=p;}
int calc(int n){
int res=1;
for(;;){
int x=1;
for(;x<=n;x++)if(!del[x])break;
if(x>n)return res;
int y=x+1;
for(;y<=n;y++)if(!del[y]&&g[x][y])break;
if(y>n){
if(g[x][x])return 0;
res=2ll*res%p;
del[x]=1;
continue;
}
for(int i=1;i<=n;i++)if(i!=x&&i!=y)g[i].reset(x),g[i].reset(y);
del[x]=del[y]=1;res=2ll*res%p;
g[x].reset(y),g[y].reset(x);
if(g[x][x]){
for(int i=1;i<=n;i++)if(i!=y&&g[y][i])g[i].flip(i);
}
if(g[y][y]){
for(int i=1;i<=n;i++)if(i!=x&&g[x][i])g[i].flip(i);
}
if(g[x][x]&&g[y][y])res=p-res;
g[x].reset(x),g[y].reset(y);
for(int i=1;i<=n;i++)if(g[x][i])g[i]^=g[y];
for(int i=1;i<=n;i++)if(g[y][i])g[i]^=g[x];
for(int i=1;i<=n;i++)if(g[x][i]&&g[y][i])g[i].flip(i);
}
}
signed main(){
// file("match");
scanf("%d",&T);
init(N-10);
for(;T--;){
scanf("%d",&n);
for(int i=1;i<=n;i++)c[i]=0;
for(int i=1;i<=n;i++)scanf("%d",&a[i]),t[i]=a[i],c[a[i]]++;
if(n==1){puts("1");continue;}
int all=1,res=0;
for(int i=1;i<=n;i++)all=1ll*all*h[c[i]]%p;
sort(t+1,t+n+1);
int m=unique(t+1,t+n+1)-t-1;
for(int i=1;i<=n;i++)a[i]=lower_bound(t+1,t+m+1,a[i])-t;
for(int i=1;i<=n+m;i++)g[i].reset(),del[i]=0;
for(int i=1;i<=n;i++){
g[i][n+a[i]]=g[n+a[i]][i]=1;
for(int j=i+1;j<=n;j++)if(a[i]<a[j])g[i][j]=g[j][i]=1;
}
// printf("%d %d\n",f[0][0],f[0][1]);
res=calc(n+m);
res=1ll*res*qpow(inv2,m)%p;
// printf("%d %d\n",all,res);
printf("%lld\n",1ll*(res+all)*inv2%p);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 19ms
memory: 3956kb
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: 23ms
memory: 3956kb
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: 49ms
memory: 4900kb
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: 47ms
memory: 5020kb
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: 213ms
memory: 4912kb
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: 217ms
memory: 4968kb
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: 213ms
memory: 5028kb
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: 215ms
memory: 4948kb
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: 214ms
memory: 4880kb
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: 213ms
memory: 4836kb
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: 28ms
memory: 4160kb
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: 30ms
memory: 4244kb
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: 29ms
memory: 4144kb
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: 28ms
memory: 4096kb
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: 266ms
memory: 5264kb
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: 259ms
memory: 5076kb
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: 322ms
memory: 5484kb
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: 270ms
memory: 5296kb
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: 334ms
memory: 5460kb
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: 280ms
memory: 5260kb
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"