QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#456961	#4921. 匹配计数	marher	40	34ms	5752kb	C++17	1.5kb	2024-06-28 19:01:20	2024-06-28 19:01:20

Judging History

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

[2024-06-28 19:01:20]
评测

测评结果：40
用时：34ms
内存：5752kb

查看

[2024-06-28 19:01:20]
提交

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]=G[j][i]=G[i][j]^1;
}

void solve(int u)
{
    if(u==n+1)return;
    if(vi[u])return solve(u+1);
    int F=G[u][u];G[u][u]=0;
    ans=ans*2%mod;
    if(G[u].count()==0)
    {
        if(F)ans=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],S=G[v];
    for(int i=1;i<=n;i++)if(S[i])
    {
        for(int j=1;j<=n;j++)if(V[j])add(i,j);
        if(F)add(i,i);
    }
    for(int i=1;i<=n;i++)G[i][u]=G[i][v]=0;
    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+mod)%mod*inv2%mod<<'\n';
        for(int i=1;i<=n;i++)G[i].reset(),vis[i]=vi[i]=0;
    }
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5

Accepted

time: 0ms

memory: 3608kb

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:

result:

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

Test #2:

score: 5

Accepted

time: 0ms

memory: 3648kb

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:

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

Test #3:

score: 5

Accepted

time: 21ms

memory: 4652kb

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:

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

Test #4:

score: 5

Accepted

time: 20ms

memory: 4736kb

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:

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

Test #5:

score: 0

Time Limit Exceeded

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

result:

Test #6:

score: 0

Time Limit Exceeded

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

result:

Test #7:

score: 0

Time Limit Exceeded

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

result:

Test #8:

score: 0

Time Limit Exceeded

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

result:

Test #9:

score: 0

Time Limit Exceeded

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

result:

Test #10:

score: 0

Time Limit Exceeded

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

result:

Test #11:

score: 5

Accepted

time: 29ms

memory: 3744kb

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:

result:

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

Test #12:

score: 5

Accepted

time: 34ms

memory: 3828kb

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:

result:

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

Test #13:

score: 5

Accepted

time: 30ms

memory: 3852kb

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:

result:

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

Test #14:

score: 5

Accepted

time: 29ms

memory: 5752kb

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:

result:

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

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:

332471774

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:

353685051

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:

476822210

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...