QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #456904 | #4921. 匹配计数 | marher | 0 | 0ms | 0kb | C++17 | 1.5kb | 2024-06-28 16:48:48 | 2024-06-28 16:48:49 |
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4096,mod=998244353,inv2=(mod+1)/2;
int n,a[N],ans,res,vis[N],vi[N],T,f[N];
bitset<N>G[N];
void add(int i,int j)
{
G[i][j].flip();
G[j][i].flip();
}
void solve(int u)
{
if(u==n+1)return;
if(vi[u])return solve(u+1);
ans=ans*2%mod;
// cout<<"solve "<<' '<<u<<' '<<ans<<'\n';
int F=G[u][u];G[u][u]=0;
if(G[u].count()==0)return solve(u+1);
int v=u;
while(!G[u][v])v++;add(u,v);
if(G[v][v])
{
for(int i=1;i<=n;i++)if(G[u][i])add(i,i);
if(F)ans*=-1;
}
auto V=G[u];
for(int i=1;i<=n;i++)if(G[v][i])
{
for(int j=1;j<=n;j++)if(V[j])add(i,j);
if(F)add(i,i);
}
vi[u]=vi[v]=1;
solve(u+1);
}
signed main()
{
// freopen("in","r",stdin);
cin>>T;
f[0]=1;
for(int i=1;i<N;i++)f[i]=(f[i-1]+(i-1)*f[i-2]%mod)%mod;
while(T--)
{
cin>>n;ans=res=1;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(a[i]>a[j])add(i,j);
int rn=n;
for(int i=1;i<=n;i++)if(!vis[a[i]])
{
++rn;int cc=0;vis[a[i]]=1;
for(int j=i;j<=n;j++)if(a[i]==a[j])add(rn,j),cc++;
ans=ans*inv2%mod;res=res*f[cc]%mod;
}
n=rn;
solve(1);
cout<<(ans+res)*inv2%mod<<'\n';
for(int i=1;i<=n;i++)G[i].reset(),vis[i]=vi[i]=0;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
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:
8
result:
Test #2:
score: 0
Runtime Error
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:
result:
Test #3:
score: 0
Time Limit Exceeded
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:
result:
Test #4:
score: 0
Time Limit Exceeded
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:
result:
Test #5:
score: 0
Runtime Error
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:
result:
Test #6:
score: 0
Runtime Error
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:
result:
Test #7:
score: 0
Runtime Error
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:
result:
Test #8:
score: 0
Runtime Error
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:
result:
Test #9:
score: 0
Runtime Error
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:
result:
Test #10:
score: 0
Runtime Error
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:
result:
Test #11:
score: 0
Runtime Error
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:
109121189
result:
Test #12:
score: 0
Runtime Error
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:
813701005
result:
Test #13:
score: 0
Runtime Error
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:
929755209
result:
Test #14:
score: 0
Runtime Error
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:
987364361
result:
Test #15:
score: 0
Time Limit Exceeded
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:
result:
Test #16:
score: 0
Time Limit Exceeded
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:
result:
Test #17:
score: 0
Time Limit Exceeded
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:
result:
Test #18:
score: 0
Time Limit Exceeded
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:
result:
Test #19:
score: 0
Time Limit Exceeded
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:
result:
Test #20:
score: 0
Time Limit Exceeded
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...