QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#68223#4944. 假面hleternity100 ✓637ms3976kbC++142.9kb2022-12-15 11:34:212022-12-15 11:34:24

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-15 11:34:24]
  • 评测
  • 测评结果:100
  • 用时:637ms
  • 内存:3976kb
  • [2022-12-15 11:34:21]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define N 209
#define mod 998244353
#define int long long
inline int read()
{
    register int x=0;
    register char ch=cin.get();
    register bool op=0;
    while(!isdigit(ch)) {if(ch=='-')op=1;ch=cin.get();}
    while(isdigit(ch)) {(x*=10)+=(ch^48);ch=cin.get();}
    return op? -x:x;
}
inline int qpow(register int base,register int power)
{
    long long res=1;
    while (power)
    {
        if(power&1) res=1ll*res*base%mod;
        power>>=1;
        base=1ll*base*base%mod;
    }
    return res%mod;
}
long long inv[N];
long long a[N];
long long f[N][109]/*第i个人剩下j点血的概率*/;
long long id[N],g[N]/*任意i个人活着的概率*/,alive[N],dead[N],h[N]/*除i以外还有j个人活着的概率*/;
signed main()
{
    ios::sync_with_stdio(0);
    //freopen("4564.out","w",stdout);
    int n=read();
    for(register int i(1);i<=n;++i) inv[i]=qpow(i,mod-2);
    for(register int i(1);i<=n;++i) a[i]=read(),f[i][a[i]]=1;
    int m=read();
    for(register int k(1),op;k<=m;++k) 
    {
        op=read();
        if(op==0) 
        {
            int id=read(),u=read(),v=read();
            int p=1ll*u*qpow(v,mod-2)%mod;
            for(register int i(0);i<=a[id];++i) 
            {
                if(!i) f[id][i]=(f[id][i]+f[id][i+1]*p%mod)%mod;
                else f[id][i]=(f[id][i+1]*p%mod+1ll*f[id][i]*(1-p+mod)%mod)%mod;
            }
        }
        if(op==1) 
        {
            int k=read();
            memset(g,0,sizeof(g));g[0]=1;
            for(register int i(1);i<=k;++i) 
            {
                id[i]=read();
                alive[id[i]]=(1-f[id[i]][0]+mod)%mod;
                dead[id[i]]=f[id[i]][0];
                for(register int j(i);j>=0;--j) 
                {
                    if(!j) g[j]=g[j]*dead[id[i]]%mod;
                    else g[j]=(g[j-1]*alive[id[i]]%mod+g[j]*dead[id[i]]%mod)%mod;
                }
            }
            for(register int i(1);i<=k;++i) 
            {
                memset(h,0,sizeof(h));
                if(alive[id[i]]!=1) 
                {
                    int INV=qpow(dead[id[i]],mod-2);
                    h[0]=g[0]*INV%mod;
                    for(register int j(1);j<k;++j) 
                    h[j]=(g[j]-alive[id[i]]*h[j-1]%mod+mod)%mod*INV%mod;
                }
                else 
                {
                    for(register int j(0);j<=k;++j) 
                    h[j]=g[j+1];
                }
                long long ans=0;
                for(register int j(0);j<k;++j) 
                ans=(ans+h[j]*inv[j+1]%mod)%mod; 
                ans=ans*alive[id[i]]%mod;
                printf("%lld ",ans);
            }
            printf("\n");
        }
    }
    for(register int i(1);i<=n;++i) 
    {
        int ans=0;
        for(register int j(1);j<=a[i];++j) ans=(ans+f[i][j]*j%mod)%mod;
        printf("%d ",ans);
    }
    return 0;
}

詳細信息

Test #1:

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

input:

5
3 2 3 5 2
21
0 4 57200194 62560282
0 1 146714842 190677962
0 3 421682737 866825565
0 2 147205019 326165492
0 5 43044930 174129591
0 5 471737667 946078665
0 1 67470072 85631701
0 3 424723162 491392606
0 1 161738068 214618699
0 2 167409685 828201389
1 5 2 1 4 5 3
0 1 15605041 17495347
0 5 185545979 ...

output:

107368698 189599100 687600238 324320433 687600238 
606654499 906006418 648113700 648113700 185844743 
856212861 253665492 395756888 490853466 
720424385 963622540 990903428 277019498 42763209 
720424385 277019498 990903428 42763209 963622540 
458983827 545373647 251091757 468284676 272754800 
340362...

result:

ok 34 numbers

Test #2:

score: 10
Accepted
time: 139ms
memory: 3584kb

input:

60
93 22 28 60 27 27 37 69 30 31 24 36 3 59 68 57 43 74 20 38 25 71 27 81 74 71 82 26 28 6 30 58 96 46 68 65 51 9 79 85 52 100 61 69 13 87 40 71 79 2 3 93 57 100 87 66 45 41 32 98
199992
0 9 444583729 889658122
0 28 444583729 889658122
0 11 444583729 889658122
0 35 444583729 889658122
0 39 444583729...

output:

764196322 518700730 489720477 267683315 944759499 489706246 810974269 848295414 958825009 769587032 100148014 509434560 232856289 2353109 212130067 129459833 409889791 142582698 58894087 707314398 178109019 761720055 518483857 248114660 919049978 86715058 22798800 63432291 307970379 715642039 548359...

result:

ok 23057 numbers

Test #3:

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

input:

60
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
23
0 59 89817677 237987517
0 45 9286825 11937381
0 6 186458289 659261035
0 10 357086956 553050724
0 5 475088880 805335745
0 47 400707619 741220104
0 2 195821006 203870958
0 5 14...

output:

304278377 304278377 304278377 450544203 304278377 304278377 304278377 637957920 341116069 865590646 304278377 304278377 304278377 304278377 366627363 304278377 304278377 304278377 304278377 485008584 853044587 977460394 304278377 304278377 304278377 304278377 304278377 304278377 304278377 304278377 ...

result:

ok 339 numbers

Test #4:

score: 10
Accepted
time: 108ms
memory: 3680kb

input:

60
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
199994
0 13 601080363 879374736
0 41 13604970 620358714
0 4 474749303 543941493
0 11 204080001 233457854
0 58 438081964 812786834
0 23 884507813 995739274
0 53 148575990 2570380...

output:

603671434 346307002 472937431 420751207 126823661 436769552 525776156 504666874 886609578 97379102 44433317 490965368 588872603 205364900 764004244 581616782 121073920 606101615 383989028 659316281 311182521 375247790 393444793 704852419 861322040 638325251 427096039 140931152 394672817 201550761 87...

result:

ok 23287 numbers

Test #5:

score: 10
Accepted
time: 146ms
memory: 3588kb

input:

60
93 22 28 60 27 27 37 69 30 31 24 36 3 59 68 57 43 74 20 38 25 71 27 81 74 71 82 26 28 6 30 58 96 46 68 65 51 9 79 85 52 100 61 69 13 87 40 71 79 2 3 93 57 100 87 66 45 41 32 98
199995
0 41 13604970 620358714
0 4 474749303 543941493
0 11 204080001 233457854
0 58 438081964 812786834
0 23 884507813 ...

output:

880925494 290653588 521390872 861342120 187391714 904328230 690519955 527946830 35021728 836362841 191560014 791376646 461144894 548639684 586467108 818063632 59033652 43706329 886954774 14312194 291313471 818481148 150874524 885699229 215410211 792329674 164791319 136544870 429441970 976795291 7851...

result:

ok 22904 numbers

Test #6:

score: 10
Accepted
time: 125ms
memory: 3864kb

input:

60
93 22 28 60 27 27 37 69 30 31 24 36 3 59 68 57 43 74 20 38 25 71 27 81 74 71 82 26 28 6 30 58 96 46 68 65 51 9 79 85 52 100 61 69 13 87 40 71 79 2 3 93 57 100 87 66 45 41 32 98
199996
0 41 13604970 620358714
0 4 474749303 543941493
0 11 204080001 233457854
0 58 438081964 812786834
0 23 884507813 ...

output:

31311934 458218831 612517627 520630081 834524568 735573278 602359531 185925983 117136700 16578877 668810973 149004438 695957963 757993180 756227637 877038225 676747765 747833842 422848272 590332056 36037874 559204662 863781697 453196603 254777940 641553045 491620260 317701301 731946951 649095760 437...

result:

ok 60 numbers

Test #7:

score: 10
Accepted
time: 113ms
memory: 3632kb

input:

60
93 22 28 60 27 27 37 69 30 31 24 36 3 59 68 57 43 74 20 38 25 71 27 81 74 71 82 26 28 6 30 58 96 46 68 65 51 9 79 85 52 100 61 69 13 87 40 71 79 2 3 93 57 100 87 66 45 41 32 98
199997
0 4 233 233
0 11 233 233
0 58 233 233
0 23 233 233
0 53 233 233
0 45 233 233
0 11 233 233
0 31 233 233
0 55 233 2...

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0...

result:

ok 23920 numbers

Test #8:

score: 10
Accepted
time: 617ms
memory: 3976kb

input:

200
93 22 28 60 27 27 37 69 30 31 24 36 3 59 68 57 43 74 20 38 25 71 27 81 74 71 82 26 28 6 30 58 96 46 68 65 51 9 79 85 52 100 61 69 13 87 40 71 79 2 3 93 57 100 87 66 45 41 32 98 82 10 68 98 87 7 20 29 33 4 71 9 41 97 19 47 22 80 65 42 94 100 65 15 57 92 66 37 52 29 8 22 96 38 94 29 12 30 5 64 39 ...

output:

421737305 105292341 240215808 749028261 224707095 93242760 928065947 239801839 517199786 687760868 502022091 392955495 428053444 330907240 46885553 106112751 310527975 817173654 494622743 596118073 669502125 58629348 711659348 400846887 327935833 706923295 618782995 423968818 359158511 58441258 5456...

result:

ok 163965 numbers

Test #9:

score: 10
Accepted
time: 608ms
memory: 3692kb

input:

200
93 22 28 60 27 27 37 69 30 31 24 36 3 59 68 57 43 74 20 38 25 71 27 81 74 71 82 26 28 6 30 58 96 46 68 65 51 9 79 85 52 100 61 69 13 87 40 71 79 2 3 93 57 100 87 66 45 41 32 98 82 10 68 98 87 7 20 29 33 4 71 9 41 97 19 47 22 80 65 42 94 100 65 15 57 92 66 37 52 29 8 22 96 38 94 29 12 30 5 64 39 ...

output:

971043096 868722851 875635361 215247791 785440837 377902251 150714744 697444982 662790052 480498888 32043015 575549872 572526454 895731814 92926758 88615559 758602780 772570474 275781091 206233514 342346690 686852273 954370168 704585237 604704513 946450840 247809365 55607264 381837037 942535798 2564...

result:

ok 163028 numbers

Test #10:

score: 10
Accepted
time: 637ms
memory: 3752kb

input:

200
93 22 28 60 27 27 37 69 30 31 24 36 3 59 68 57 43 74 20 38 25 71 27 81 74 71 82 26 28 6 30 58 96 46 68 65 51 9 79 85 52 100 61 69 13 87 40 71 79 2 3 93 57 100 87 66 45 41 32 98 82 10 68 98 87 7 20 29 33 4 71 9 41 97 19 47 22 80 65 42 94 100 65 15 57 92 66 37 52 29 8 22 96 38 94 29 12 30 5 64 39 ...

output:

358072467 98740040 682265210 735560556 457058322 39866355 946464972 789839555 765587358 240203502 617891630 455352073 421639136 607704397 754616177 78679522 136934614 763982442 92646916 50664698 763385610 866570195 724772491 607964748 12163419 722087145 453872135 442277078 756643760 869905047 316910...

result:

ok 165924 numbers

Extra Test:

score: 0
Extra Test Passed