QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#718195#9611. 木桶效应Nesraychan100 ✓242ms4380kbC++142.5kb2024-11-06 19:56:162024-11-06 19:56:18

Judging History

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

  • [2024-11-06 19:56:18]
  • 评测
  • 测评结果:100
  • 用时:242ms
  • 内存:4380kb
  • [2024-11-06 19:56:16]
  • 提交

answer

#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 55
#define M (1<<10|5)
#define mod 998244353
IL int read()
{
    reg int x=0,f=0; reg char ch=getchar();
    while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}

IL int Add(reg int x,reg int y){return x+y<mod?x+y:x+y-mod;}
IL void Pls(reg int &x,reg int y){x=Add(x,y);}
IL int Mul(reg int x,reg int y){long long r=1ll*x*y; return r<mod?r:r%mod;}
IL int power(reg int x,reg int p){reg int r=1; for(;p;p>>=1,x=Mul(x,x))if(p&1)r=Mul(r,x); return r;}

int n,m,q,mn[N];

IL void cmin(reg int &x,reg int y){x>y?x=y:0;}

int f[N][M],nf[N][M],con[N],binom[N][N],pop[M];
bool col[N];
int p[N],tot,cnt,full;
std::map<int,int>id;
std::vector<std::pair<int,int>>vec[N];

main()
{
    n=read(),m=read(),q=read();
    for(reg int i=1;i<=n;++i)mn[i]=n;
    for(reg int x,y,k;q--;)
    {
        x=read(),y=read(),k=read();
        cmin(mn[y],k),col[y]=1;
        if(!id.count(x))id[x]=++cnt;
        vec[y].push_back({id[x],k});
    }
    for(reg int i=1;i<=n;++i)if(col[i])p[tot++]=i;
    full=1<<tot;
    for(reg int s=1;s<full;++s)pop[s]=pop[s>>1]+(s&1);
    for(reg int i=0;i<=n;++i)con[i]=power(i,m-cnt);
    for(reg int i=0;i<=n;++i)binom[i][0]=1;
    for(reg int i=1,j;i<=n;++i)for(j=1;j<=i;++j)
        binom[i][j]=Add(binom[i-1][j],binom[i-1][j-1]);
    f[0][0]=1;
    for(reg int i=n,s,j,k,w,o;i;--i)
    {
        for(j=0;j<=n;++j)for(s=full;s--;)if(w=f[j][s])
        {
            reg int x=n-j,y=i-1;
            if(m>cnt)
            {
                if(x>=y)w=Mul(w,con[x-y]);
                else w=0;    
            }            
            static int val[N];
            for(k=1;k<=cnt;++k)val[k]=x-y;
            for(o=tot;o--;)if(~s>>o&1)
                for(auto &[row,t]:vec[p[o]])
                    if(t>i)--val[row];
            for(o=tot;o--;)if(~s>>o&1)
                for(auto &[row,t]:vec[p[o]])
                    if(t==i)val[row]=1;
            for(k=1;k<=cnt&&w;++k)
                if(val[k]>0)w=Mul(w,val[k]);
                else w=0;
            f[j][s]=w;
        }
        for(o=tot;o--;)if(mn[p[o]]>=i)for(s=full;s--;)if(~s>>o&1)
            for(j=0;j<=n;++j)if(w=f[j][s])Pls(f[j+1][s|(1<<o)],w);
        for(j=0;j<=n;++j)for(s=full;s--;)if(w=f[j][s])for(k=0;j+k<=n;++k)
            Pls(nf[j+k][s],Mul(w,binom[n-tot-j+pop[s]][k]));
        for(j=0;j<=n;++j)for(s=full;s--;)f[j][s]=nf[j][s],nf[j][s]=0;
    }
    printf("%d\n",f[n][full-1]);
}

詳細信息

Subtask #1:

score: 4
Accepted

Test #1:

score: 4
Accepted
time: 0ms
memory: 3808kb

input:

5 3 0

output:

21412920

result:

ok single line: '21412920'

Test #2:

score: 4
Accepted
time: 0ms
memory: 3852kb

input:

5 3 2
3 4 4
2 5 3

output:

847674

result:

ok single line: '847674'

Test #3:

score: 4
Accepted
time: 0ms
memory: 4004kb

input:

5 3 3
3 5 5
1 2 5
2 5 3

output:

168780

result:

ok single line: '168780'

Subtask #2:

score: 8
Accepted

Dependency #1:

100%
Accepted

Test #4:

score: 8
Accepted
time: 0ms
memory: 3876kb

input:

7 3 0

output:

160221085

result:

ok single line: '160221085'

Test #5:

score: 8
Accepted
time: 0ms
memory: 3796kb

input:

7 3 2
1 1 5
1 6 2

output:

598007855

result:

ok single line: '598007855'

Test #6:

score: 8
Accepted
time: 0ms
memory: 3872kb

input:

7 3 3
1 1 5
2 6 3
2 1 7

output:

950880222

result:

ok single line: '950880222'

Subtask #3:

score: 8
Accepted

Test #7:

score: 8
Accepted
time: 1ms
memory: 4172kb

input:

50 1 0

output:

263941435

result:

ok single line: '263941435'

Test #8:

score: 8
Accepted
time: 0ms
memory: 4320kb

input:

43 2 0

output:

136378346

result:

ok single line: '136378346'

Test #9:

score: 8
Accepted
time: 1ms
memory: 4180kb

input:

50 2 0

output:

489087596

result:

ok single line: '489087596'

Subtask #4:

score: 12
Accepted

Dependency #3:

100%
Accepted

Test #10:

score: 12
Accepted
time: 1ms
memory: 4152kb

input:

50 292247015 0

output:

226872193

result:

ok single line: '226872193'

Test #11:

score: 12
Accepted
time: 1ms
memory: 4248kb

input:

50 873009728 0

output:

63648791

result:

ok single line: '63648791'

Subtask #5:

score: 16
Accepted

Dependency #2:

100%
Accepted

Dependency #4:

100%
Accepted

Test #12:

score: 16
Accepted
time: 0ms
memory: 4000kb

input:

20 728836785 5
248289571 15 16
439110385 8 15
339467267 12 7
585491339 7 9
605518440 4 1

output:

761275883

result:

ok single line: '761275883'

Test #13:

score: 16
Accepted
time: 0ms
memory: 3996kb

input:

20 288197925 5
31379347 9 1
222153278 1 1
24531748 20 1
106427339 18 1
212338331 17 1

output:

877851586

result:

ok single line: '877851586'

Test #14:

score: 16
Accepted
time: 1ms
memory: 3992kb

input:

20 880439688 5
563540321 17 20
395236367 3 20
300712779 6 20
121406689 18 20
25890496 9 20

output:

186649553

result:

ok single line: '186649553'

Test #15:

score: 16
Accepted
time: 1ms
memory: 3920kb

input:

20 311402369 5
311293636 14 13
306211116 19 19
36858994 5 11
36858994 19 10
306211116 14 18

output:

415461922

result:

ok single line: '415461922'

Test #16:

score: 16
Accepted
time: 1ms
memory: 3916kb

input:

20 98953332 5
1075868 12 5
31161114 8 12
46790018 9 10
39214697 15 7
46790018 8 8

output:

204149614

result:

ok single line: '204149614'

Subtask #6:

score: 12
Accepted

Dependency #5:

100%
Accepted

Test #17:

score: 12
Accepted
time: 3ms
memory: 4156kb

input:

50 915702052 5
541920465 39 16
833447607 49 14
326677362 14 34
412319566 10 36
206682128 46 28

output:

783441394

result:

ok single line: '783441394'

Test #18:

score: 12
Accepted
time: 1ms
memory: 4380kb

input:

50 47879239 5
30666754 20 1
23945845 17 1
27229141 25 1
40551703 9 1
15723198 18 1

output:

546399382

result:

ok single line: '546399382'

Test #19:

score: 12
Accepted
time: 5ms
memory: 4152kb

input:

50 334191703 5
167838076 19 50
95127599 33 50
221030062 4 50
89223523 36 50
40736662 39 50

output:

242104112

result:

ok single line: '242104112'

Test #20:

score: 12
Accepted
time: 1ms
memory: 4156kb

input:

50 33538004 5
1341436 40 26
19132404 4 13
22271562 24 25
19132404 40 18
19132404 24 38

output:

509216038

result:

ok single line: '509216038'

Test #21:

score: 12
Accepted
time: 2ms
memory: 4148kb

input:

50 453197583 5
304895210 17 41
450727109 33 20
129855576 4 24
214262208 12 46
214262208 4 27

output:

929330226

result:

ok single line: '929330226'

Subtask #7:

score: 20
Accepted

Dependency #6:

100%
Accepted

Test #22:

score: 20
Accepted
time: 14ms
memory: 4176kb

input:

50 733592974 7
204969642 20 32
532101473 38 22
428067108 29 19
699479674 23 35
403248947 11 33
523610998 39 50
207894041 37 47

output:

878602112

result:

ok single line: '878602112'

Test #23:

score: 20
Accepted
time: 2ms
memory: 4220kb

input:

50 363989184 7
275675456 32 1
14440487 41 1
84675645 18 1
112753584 7 1
259289962 30 1
244964889 42 1
34667760 27 1

output:

125183718

result:

ok single line: '125183718'

Test #24:

score: 20
Accepted
time: 22ms
memory: 4252kb

input:

50 987882639 7
17913003 22 50
440453368 26 50
849090802 8 50
106136773 13 50
491841612 34 50
131376512 15 50
231961452 39 50

output:

573542486

result:

ok single line: '573542486'

Test #25:

score: 20
Accepted
time: 1ms
memory: 4244kb

input:

50 739368354 7
163377222 20 27
192827369 29 10
688310083 50 13
20398047 27 45
688310083 29 11
192827369 20 5
688310083 27 27

output:

528550901

result:

ok single line: '528550901'

Test #26:

score: 20
Accepted
time: 2ms
memory: 4160kb

input:

50 691852384 7
552436456 27 11
103126750 8 13
122888842 49 34
306609066 7 11
553011271 38 32
553011271 27 47
553011271 49 50

output:

407673475

result:

ok single line: '407673475'

Test #27:

score: 20
Accepted
time: 4ms
memory: 4168kb

input:

50 828246844 7
528561184 35 4
15522388 43 35
679004541 17 20
161133582 6 20
289045078 32 49
705209075 24 38
705209075 17 44

output:

734432988

result:

ok single line: '734432988'

Subtask #8:

score: 12
Accepted

Dependency #7:

100%
Accepted

Test #28:

score: 12
Accepted
time: 51ms
memory: 4228kb

input:

50 818455715 9
460012830 5 33
118588510 47 47
281020207 23 25
175303600 1 18
234157803 48 32
256460906 19 46
287657461 24 13
81772046 14 22
114821805 44 41

output:

863394340

result:

ok single line: '863394340'

Test #29:

score: 12
Accepted
time: 4ms
memory: 4316kb

input:

50 24969517 9
23565097 13 1
11005666 43 1
21727790 47 1
12763778 6 1
6881701 34 1
2985794 23 1
13971040 15 1
13187518 29 1
1995154 12 1

output:

755357189

result:

ok single line: '755357189'

Test #30:

score: 12
Accepted
time: 111ms
memory: 4232kb

input:

50 429772980 9
414497820 4 50
141139445 19 50
407732495 7 50
83785413 1 50
164351908 8 50
213988430 26 50
52240611 50 50
352159955 27 50
279326344 29 50

output:

247413078

result:

ok single line: '247413078'

Test #31:

score: 12
Accepted
time: 4ms
memory: 4224kb

input:

50 919810726 9
403069670 48 3
193931638 39 28
821686776 22 11
432351038 8 49
466123383 14 34
254851369 2 48
193931638 48 38
821686776 8 19
254851369 8 20

output:

481094724

result:

ok single line: '481094724'

Test #32:

score: 12
Accepted
time: 3ms
memory: 4236kb

input:

50 619619808 9
140356219 25 31
289966305 18 15
308904151 23 44
530131662 15 2
174186843 35 5
452736627 42 7
12231110 21 2
308904151 18 33
140356219 18 30

output:

194056785

result:

ok single line: '194056785'

Test #33:

score: 12
Accepted
time: 3ms
memory: 4192kb

input:

50 405638475 9
189173757 25 33
313860932 22 8
196599730 26 6
273814431 3 2
52701532 15 14
335951766 19 3
313077524 29 13
349363426 7 15
313860932 19 19

output:

435209021

result:

ok single line: '435209021'

Subtask #9:

score: 8
Accepted

Dependency #8:

100%
Accepted

Test #34:

score: 8
Accepted
time: 50ms
memory: 4380kb

input:

50 946059042 10
160844820 11 40
246397981 49 28
373026730 1 18
602144414 9 9
284028279 39 44
22155194 16 2
851925494 6 17
862159117 27 32
773018252 10 20
462257810 48 19

output:

680391855

result:

ok single line: '680391855'

Test #35:

score: 8
Accepted
time: 3ms
memory: 4188kb

input:

50 260661857 10
70899239 47 1
248286199 34 1
49459370 23 1
110741847 3 1
13147285 19 1
75609139 10 1
16001621 49 1
258636033 17 1
41404092 36 1
259336018 9 1

output:

621578303

result:

ok single line: '621578303'

Test #36:

score: 8
Accepted
time: 242ms
memory: 4180kb

input:

50 444766827 10
138606634 2 50
356874907 48 50
186818234 44 50
328471606 8 50
57922803 45 50
442175507 50 50
45412871 41 50
111164719 24 50
278665393 39 50
49548102 15 50

output:

476500313

result:

ok single line: '476500313'

Test #37:

score: 8
Accepted
time: 2ms
memory: 4164kb

input:

50 471185620 10
330350191 32 46
19091103 17 9
383913632 38 25
125638511 4 13
227803510 12 49
140314389 27 34
97824926 22 46
19091103 27 16
140314389 38 4
97824926 12 1

output:

746959227

result:

ok single line: '746959227'

Test #38:

score: 8
Accepted
time: 17ms
memory: 4232kb

input:

50 534235345 10
505481965 11 39
325061903 12 35
443938537 40 20
144968487 29 31
292692014 18 39
423914803 14 36
221863124 46 41
413488879 5 39
413488879 14 5
325061903 11 42

output:

83413094

result:

ok single line: '83413094'

Test #39:

score: 8
Accepted
time: 26ms
memory: 4260kb

input:

50 268783055 10
164040236 5 3
77416439 15 8
215664484 32 34
84807773 8 44
242418459 20 43
132116147 31 13
11369559 50 23
264864429 6 42
153908131 3 27
132116147 20 50

output:

858392519

result:

ok single line: '858392519'

Test #40:

score: 8
Accepted
time: 0ms
memory: 4224kb

input:

50 680178330 10
381317639 8 3
97592656 22 6
66456445 4 9
277935856 2 13
629083753 35 33
86588466 7 25
86588466 8 6
66456445 22 11
97592656 8 23
277935856 7 24

output:

274256402

result:

ok single line: '274256402'