QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#380719#7838. 往日之影LRC50 120ms3720kbC++203.5kb2024-04-07 09:30:082024-04-07 09:30:08

Judging History

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

  • [2024-04-07 09:30:08]
  • 评测
  • 测评结果：50
  • 用时：120ms
  • 内存：3720kb
查看
  • [2024-04-07 09:30:08]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll mod;
inline void md(ll &x){if(x>=mod) x-=mod;}
inline ll _md(ll x){return x>=mod?x-mod:x;}
inline ll qpow(ll x,ll y)
{
    ll res=1;while(y){if(y&1ll) res=res*x%mod; x=x*x%mod,y>>=1;} return res;
}
struct Com
{
    ll x,y;Com(ll _x=0,ll _y=0){x=_x,y=_y;}
    inline Com operator+(const Com &z)const{return Com(_md(x+z.x),_md(y+z.y));}
    inline Com operator-(const Com &z)const{return Com(_md(x+mod-z.x),_md(y+mod-z.y));}
    inline Com operator*(const Com &z)const{return Com((x*z.x+mod-y*z.y%mod)%mod,(x*z.y+y*z.x)%mod);}
    inline Com operator*(ll k)const{return Com(x*k%mod,y*k%mod);}
    inline Com conj()const{return Com(x,_md(mod-y));}
    inline Com operator/(const Com &z)const{return (*this)*z.conj()*qpow((z.x*z.x+z.y*z.y)%mod,mod-2);}
}rt[4];
inline Com qpow(Com x,ll y)
{
    Com res(1);while(y){if(y&1ll) res=res*x; x=x*x,y>>=1;} return res;
}
int ct[4],n,a[4][4],s[4];
inline void calc(Com &res,ll K)
{
    Com ans(1);
    for(int i=0;i<4;i++)
    {
        int sum=0;
        for(int j=0;j<4;j++)
        {
            if(a[j][i]<0) return;
            sum+=a[j][i];
        }   
        if(sum!=ct[i]) return;
    }
    for(int i=0;i<4;i++)
    {
        s[i]=0;int nws=0;
        for(int j=0;j<4;j++)
            nws+=a[i][j]*j,s[i]+=a[i][j];
        ans=ans/qpow(rt[i],nws);
        ans=ans*qpow(Com(1)+rt[i]*rt[i],1ll*s[i]*(s[i]-1)/2);
    }
    for(int i=0;i<4;i++)
        for(int j=i+1;j<4;j++)
            ans=ans*qpow(Com(1)+rt[i]*rt[j],1ll*s[i]*s[j]);
    res=res+ans*K;
}
inline void work()
{
    cin>>n>>ct[0]>>ct[1]>>ct[2]>>ct[3];
    Com ans(0,0);
    if(n<=2)
    {
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                for(int p1=0;p1<4;p1++)
                    for(int p2=0;p2<4;p2++)
                    {
                        if(!i&&p1) continue;
                        if(!j&&p2) continue;
                        memset(a,0,sizeof(a));
                        if(i) a[1][p1]++;
                        if(j) a[3][p2]++;
                        ll K=1;
                        if(i&&j) K=(p1==p2?2:1);
                        calc(ans,K);
                    }
    }
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                for(int p1=0;p1<4;p1++)
                    for(int p2=0;p2<4;p2++)
                    {
                        if(!j&&p1) continue;
                        if(!k&&p2) continue;
                        memset(a,0,sizeof(a));
                        for(int p=0;p<4;p++)
                            a[i?0:2][p]=ct[p];
                        if(j) a[1][p1]++,a[i?0:2][p1]--;
                        if(k) a[3][p2]++,a[i?0:2][p2]--;
                        int nws=0;
                        for(int p=0;p<4;p++)
                            nws+=a[i?0:2][p];
                        if(nws<=0) continue;
                        ll K=1;
                        if(j&&k) K=(p1==p2?1ll*ct[p1]*(ct[p1]-1)%mod:1ll*ct[p1]*ct[p2]%mod);
                        else if(j) K=ct[p1];
                        else if(k) K=ct[p2];
                        calc(ans,K);
                    }
    ans=ans*qpow(qpow(2,2ll*n+1ll*n*(n-1)/2ll),mod-2);
    cout<<ans.x<<"\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T;cin>>T>>mod;
    rt[0]=Com(1,0),rt[1]=Com(0,1);
    rt[2]=Com(mod-1,0),rt[3]=Com(0,mod-1);
    while(T--) work();


    return 0;
}
源文件, 语言: C++20

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 1ms
memory: 3636kb

input:

1 998244353
3
1 1 0 1

output:

0

result:

ok single line: '0'

Test #2:

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

input:

1 998244353
7
0 2 1 4

output:

998069185

result:

ok single line: '998069185'

Test #3:

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

input:

1 998244353
4
0 1 0 3

output:

0

result:

ok single line: '0'

Test #4:

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

input:

1 998244353
2
1 0 1 0

output:

0

result:

ok single line: '0'

Test #5:

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

input:

1 998244353
6
2 1 0 3

output:

997696001

result:

ok single line: '997696001'

Test #6:

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

input:

1 998244353
2
1 0 1 0

output:

0

result:

ok single line: '0'

Subtask #2:

score: 20
Accepted

Dependency #1:

100%
Accepted

Test #7:

score: 20
Accepted
time: 0ms
memory: 3600kb

input:

1 998244353
40
11 9 9 11

output:

855684614

result:

ok single line: '855684614'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3676kb

input:

1 998244353
39
12 8 7 12

output:

629648158

result:

ok single line: '629648158'

Test #9:

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

input:

1 998244353
38
13 8 9 8

output:

944107686

result:

ok single line: '944107686'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3656kb

input:

1 998244353
37
16 7 7 7

output:

393700837

result:

ok single line: '393700837'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

4 998244353
10
0 3 2 5
9
2 1 1 5
10
1 2 3 4
9
4 0 3 2

output:

124779131
998235309
124779131
998236023

result:

ok 4 lines

Test #12:

score: 0
Accepted
time: 1ms
memory: 3596kb

input:

4 998244353
10
2 1 4 3
9
1 2 4 2
10
3 2 5 0
9
3 2 2 2

output:

124779131
998239593
124778655
998236261

result:

ok 4 lines

Test #13:

score: 0
Accepted
time: 1ms
memory: 3596kb

input:

4 998244353
10
1 4 1 4
9
2 0 5 2
10
3 5 1 1
9
6 1 1 1

output:

623900891
998239355
374338940
998231025

result:

ok 4 lines

Test #14:

score: 0
Accepted
time: 1ms
memory: 3656kb

input:

8 998244353
4
2 1 0 1
4
0 2 0 2
5
0 1 1 3
4
0 1 0 3
5
1 1 0 3
5
0 3 1 1
4
2 2 0 0
5
1 1 2 1

output:

0
0
995319809
0
997269505
995319809
982646785
996294657

result:

ok 8 lines

Test #15:

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

input:

8 998244353
4
2 1 0 1
4
3 0 1 0
4
0 2 2 0
5
2 0 1 2
5
1 2 0 2
5
0 1 1 3
5
0 1 1 3
4
1 1 1 1

output:

0
0
967049217
997269505
0
995319809
995319809
0

result:

ok 8 lines

Test #16:

score: 0
Accepted
time: 1ms
memory: 3660kb

input:

3 998244353
30
1 10 7 12
8
0 3 0 5
2
0 1 0 1

output:

54137262
998208177
0

result:

ok 3 lines

Subtask #3:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #17:

score: 10
Accepted
time: 0ms
memory: 3600kb

input:

1 998244353
99
12 22 33 32
15 998244353
7
1 2 2 2
6
1 2 1 2
6
1 1 3 1
7
0 3 1 3
7
1 1 2 3
7
3 1 0 3
6
1 2 1 2
7
1 2 2 2
7
3 3 0 1
6
1 1 3 1
7
5 1 0 1
6
3 0 1 2
6
2 0 0 4
7
2 0 1 4
6
4 1 0 1

output:

940435798

result:

ok single line: '940435798'

Test #18:

score: 0
Accepted
time: 1ms
memory: 3716kb

input:

1 998244353
98
27 29 23 19
15 998244353
7
2 2 1 2
6
0 1 2 3
6
0 2 2 2
6
6 0 0 0
7
4 1 1 1
7
2 1 1 3
7
2 1 1 3
7
2 3 1 1
7
3 3 0 1
6
3 1 1 1
6
3 1 1 1
7
2 1 1 3
6
1 1 3 1
6
1 1 3 1
6
2 0 4 0

output:

147819391

result:

ok single line: '147819391'

Test #19:

score: 0
Accepted
time: 1ms
memory: 3660kb

input:

3 998244353
70
15 17 13 25
20
8 3 4 5
10
3 2 5 0
15 998244353
7
5 1 0 1
6
0 1 4 1
7
1 3 2 1
6
1 0 1 4
7
2 2 1 2
7
2 1 1 3
7
2 3 1 1
6
6 0 0 0
6
3 2 1 0
7
2 3 1 1
7
1 1 2 3
6
2 1 2 1
6
1 2 1 2
6
1 1 1 3
7
2 2 3 0

output:

300715311
500913543
124778655

result:

ok 3 lines

Test #20:

score: 0
Accepted
time: 1ms
memory: 3668kb

input:

3 998244353
70
21 23 11 15
20
5 4 3 8
10
5 1 1 3
15 998244353
6
1 0 3 2
7
3 1 0 3
6
2 2 0 2
7
1 3 0 3
7
2 2 3 0
6
3 0 3 0
6
1 0 3 2
7
1 1 2 3
6
1 1 1 3
7
1 2 0 4
7
2 1 1 3
6
4 0 0 2
6
2 2 2 0
6
2 2 0 2
6
0 1 2 3

output:

367385542
500913543
374339416

result:

ok 3 lines

Test #21:

score: 0
Accepted
time: 1ms
memory: 3660kb

input:

10 998244353
9
2 4 1 2
10
3 4 1 2
10
1 2 3 4
10
2 3 4 1
10
3 1 3 3
9
0 4 3 2
9
2 3 1 3
10
4 2 2 2
9
4 1 1 3
9
2 3 1 3
15 998244353
7
1 3 0 3
6
3 2 1 0
6
0 2 0 4
6
0 4 2 0
7
1 3 0 3
6
1 1 3 1
6
1 4 1 0
7
1 1 2 3
6
2 3 0 1
7
3 1 2 1
6
4 0 2 0
6
2 2 2 0
6
2 1 2 1
7
3 2 2 0
6
0 0 4 2

output:

998236023
124778179
124779131
124778655
374340011
998239355
998236261
374339535
998233643
998236261

result:

ok 10 lines

Test #22:

score: 0
Accepted
time: 1ms
memory: 3680kb

input:

15 998244353
7
3 2 2 0
7
2 2 3 0
6
1 3 1 1
7
1 1 2 3
6
1 3 1 1
7
3 3 0 1
6
2 1 2 1
6
1 2 1 2
6
1 1 1 3
6
4 1 0 1
7
3 2 2 0
6
1 3 1 1
6
0 2 2 2
7
1 3 0 3
7
2 2 1 2

output:

998191041
998191041
998061569
998069185
998061569
998160577
997939713
997939713
997574145
997939713
998191041
998061569
997574145
998145345
998145345

result:

ok 15 lines

Subtask #4:

score: 10
Accepted

Test #23:

score: 10
Accepted
time: 13ms
memory: 3684kb

input:

999 999999001
2
2 0 0 0
3
3 0 0 0
4
4 0 0 0
5
5 0 0 0
6
6 0 0 0
7
7 0 0 0
8
8 0 0 0
9
9 0 0 0
10
10 0 0 0
11
11 0 0 0
12
12 0 0 0
13
13 0 0 0
14
14 0 0 0
15
15 0 0 0
16
16 0 0 0
17
17 0 0 0
18
18 0 0 0
19
19 0 0 0
20
20 0 0 0
21
21 0 0 0
22
22 0 0 0
23
23 0 0 0
24
24 0 0 0
25
25 0 0 0
26
26 0 0 0
27...

output:

499999501
874999126
359374641
919920956
691222454
586081873
33512082
496961574
790501684
206445579
708073277
492142887
486007979
21786019
802052117
198521403
854660059
658779344
904643630
538486221
357736277
949763680
94144464
342842045
695164947
276856011
552666277
813428208
572457238
910726512
177...

result:

ok 999 lines

Test #24:

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

input:

1 1000000933
154579
154579 0 0 0

output:

657848365

result:

ok single line: '657848365'

Test #25:

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

input:

1 999999001
475343
475343 0 0 0

output:

619834045

result:

ok single line: '619834045'

Test #26:

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

input:

1 999999001
165629
165629 0 0 0

output:

753727723

result:

ok single line: '753727723'

Test #27:

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

input:

1 1000000933
348634
348634 0 0 0

output:

360252198

result:

ok single line: '360252198'

Test #28:

score: 0
Accepted
time: 120ms
memory: 3604kb

input:

10000 999999229
88
88 0 0 0
96
96 0 0 0
24
24 0 0 0
95
95 0 0 0
38
38 0 0 0
27
27 0 0 0
21
21 0 0 0
76
76 0 0 0
45
45 0 0 0
72
72 0 0 0
83
83 0 0 0
78
78 0 0 0
93
93 0 0 0
73
73 0 0 0
64
64 0 0 0
71
71 0 0 0
37
37 0 0 0
42
42 0 0 0
13
13 0 0 0
19
19 0 0 0
79
79 0 0 0
65
65 0 0 0
91
91 0 0 0
28
28 0 ...

output:

228919133
233057601
14414502
12124194
609308119
236040032
384632724
342725930
359253864
890419758
438100183
233688628
152725418
662705946
267680214
513058807
175872233
462495339
413457613
571184369
442694163
537658282
297765746
578699117
239095545
57659973
903105608
745160181
652441005
521182492
347...

result:

ok 10000 lines

Test #29:

score: 0
Accepted
time: 116ms
memory: 3600kb

input:

10000 999999937
53
53 0 0 0
81
81 0 0 0
12
12 0 0 0
19
19 0 0 0
32
32 0 0 0
43
43 0 0 0
54
54 0 0 0
70
70 0 0 0
50
50 0 0 0
86
86 0 0 0
31
31 0 0 0
33
33 0 0 0
85
85 0 0 0
54
54 0 0 0
39
39 0 0 0
90
90 0 0 0
75
75 0 0 0
37
37 0 0 0
84
84 0 0 0
68
68 0 0 0
98
98 0 0 0
73
73 0 0 0
45
45 0 0 0
71
71 0 ...

output:

315851314
404961058
478608220
872834111
278393486
518892420
770069569
110378716
660680499
726285336
810531197
451629260
668208879
770069569
948485799
58650663
417912486
382928062
769177073
530030150
665011673
960730579
766994694
452899566
414064316
5286677
960730579
155111507
110378716
582367338
872...

result:

ok 10000 lines

Test #30:

score: 0
Accepted
time: 118ms
memory: 3600kb

input:

10000 1000000933
94
94 0 0 0
33
33 0 0 0
79
79 0 0 0
11
11 0 0 0
25
25 0 0 0
99
99 0 0 0
12
12 0 0 0
13
13 0 0 0
97
97 0 0 0
70
70 0 0 0
23
23 0 0 0
62
62 0 0 0
29
29 0 0 0
50
50 0 0 0
58
58 0 0 0
96
96 0 0 0
49
49 0 0 0
23
23 0 0 0
94
94 0 0 0
81
81 0 0 0
52
52 0 0 0
27
27 0 0 0
48
48 0 0 0
35
35 0...

output:

302038132
324852455
712788007
51168171
665310026
719061662
642183435
960667161
525345109
829432052
887075946
622617369
92198574
962363993
672506569
207567890
342207626
887075946
302038132
792241276
216981867
23895508
903615878
834858306
749794882
224043056
834367334
962363993
244541137
140944214
712...

result:

ok 10000 lines

Test #31:

score: 0
Accepted
time: 120ms
memory: 3608kb

input:

10000 999999229
48
48 0 0 0
99
99 0 0 0
56
56 0 0 0
82
82 0 0 0
13
13 0 0 0
78
78 0 0 0
44
44 0 0 0
23
23 0 0 0
91
91 0 0 0
39
39 0 0 0
31
31 0 0 0
39
39 0 0 0
22
22 0 0 0
69
69 0 0 0
63
63 0 0 0
49
49 0 0 0
54
54 0 0 0
91
91 0 0 0
86
86 0 0 0
14
14 0 0 0
80
80 0 0 0
47
47 0 0 0
52
52 0 0 0
56
56 0 ...

output:

969254311
41258828
420816844
53150269
413457613
233688628
16329388
962253276
297765746
579341371
491021836
579341371
694633659
238365606
737049114
282048136
467787038
297765746
568729633
239095545
37731193
985694051
20197429
420816844
467787038
337283936
131320231
267680214
890419758
12124194
757560...

result:

ok 10000 lines

Test #32:

score: 0
Accepted
time: 119ms
memory: 3664kb

input:

10000 1000000097
47
47 0 0 0
32
32 0 0 0
67
67 0 0 0
29
29 0 0 0
47
47 0 0 0
24
24 0 0 0
62
62 0 0 0
34
34 0 0 0
69
69 0 0 0
90
90 0 0 0
48
48 0 0 0
33
33 0 0 0
70
70 0 0 0
27
27 0 0 0
93
93 0 0 0
37
37 0 0 0
59
59 0 0 0
95
95 0 0 0
83
83 0 0 0
58
58 0 0 0
91
91 0 0 0
93
93 0 0 0
54
54 0 0 0
87
87 0...

output:

722092697
288259246
443086249
346535444
722092697
96701722
589679036
496735762
287843437
134626935
367894801
88663770
85448149
843667949
156786538
440592027
933702679
516941035
418538470
518055305
804803263
156786538
107212544
806586057
107212544
256264258
107212544
810269380
343546929
426066064
144...

result:

ok 10000 lines

Subtask #5:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #33:

score: 50
Accepted
time: 90ms
memory: 3680kb

input:

999 1000000097
2
0 0 0 2
3
2 0 1 0
4
0 1 2 1
5
1 2 2 0
6
2 2 0 2
7
2 3 1 1
8
2 2 2 2
9
2 1 1 5
10
0 4 4 2
11
6 0 3 2
12
5 4 1 2
13
2 4 5 2
14
3 6 5 0
15
2 4 7 2
16
1 7 5 3
17
2 4 7 4
18
3 7 1 7
19
5 2 8 4
20
9 5 5 1
21
5 6 8 2
22
9 6 3 4
23
3 5 10 5
24
13 2 3 6
25
7 11 4 3
26
8 9 4 5
27
4 6 9 8
28
3...

output:

0
0
484375047
778320388
798645097
274604824
137302412
260870482
796911004
153103603
976723504
423019209
553202738
861418906
251527946
826500173
932083161
492049497
69044734
202003647
628743912
888734894
798739832
376180338
652733719
344738073
867062219
429725610
848050082
586973630
144578014
8392212...

result:

ok 999 lines

Test #34:

score: -50
Time Limit Exceeded

input:

100000 999999229
8
4 1 2 1
6
1 2 1 2
5
1 2 0 2
5
0 1 3 1
5
2 0 1 2
7
0 3 1 3
7
3 1 0 3
6
2 0 2 2
9
3 3 0 3
9
2 5 1 1
5
0 2 1 2
6
2 3 0 1
5
2 2 1 0
8
1 2 1 4
9
4 1 3 1
5
1 2 0 2
5
3 2 0 0
9
1 1 4 3
9
0 4 3 2
6
1 2 1 2
9
0 5 1 3
6
1 1 1 3
6
4 2 0 0
6
1 1 3 1
7
1 2 2 2
7
2 3 1 1
6
3 0 1 2
9
1 2 4 2
6
2...

output:

191255422
505309669
0
501952738
416991866
839225122
666083776
911681426
107994950
547813470
833983732
901061317
416991866
191255422
174359664
0
416991866
460633638
460633638
505309669
20815118
911681426
703185493
911681426
839225122
913428556
109558021
867269801
505309669
839225122
950530273
7031854...

result:
English 繁體中文 简体中文

伺服器時間: 2024-12-12 02:01:26 | 開源專案