QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#822807#9906. 乘积的期望zjy00010 781ms12184kbC++172.0kb2024-12-20 16:45:322024-12-20 16:45:32

Judging History

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

  • [2024-12-20 16:45:32]
  • 评测
  • 测评结果:0
  • 用时:781ms
  • 内存:12184kb
  • [2024-12-20 16:45:32]
  • 提交

answer

#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=55,M=16,Mod=998244353;
int n,m,c,L,sb,ans=1;
int b[N],frc[N],ivf[N],pw[N][N],pwb[N][N],F[N],f[N][N][1<<M];
inline int qpow(int x,int y,int z=1){
	for(;y;(y>>=1)&&(x=(LL)x*x%Mod))if(y&1)z=(LL)z*x%Mod;return z;
}
inline int Langrange(int* F,int n,int x){
    if(x<=n)return F[x];
    int z=0;
    for(int i=0;i<=n+1;++i){
        int v=1,w=F[i];
        for(int j=0;j<=n+1;++j)if(i!=j)v=(LL)v*(i-j)%Mod,w=(LL)w*(x-j)%Mod;
        z=(z+qpow(v,Mod-2,w))%Mod;
    }
    return z<0?z+Mod:z;
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m>>c,L=n+1;
    for(int i=0;i<=n-m;++i)cin>>b[i],sb+=b[i];
    while(n<m+m)ans=1ll*ans*c%Mod,--n,--m;
    sb=qpow(sb,Mod-2);
    for(int i=0;i<=n-m;++i)b[i]=(LL)b[i]*sb%Mod;
    for(int i=0;i<=n-m;++i){
        pwb[i][0]=1;
        for(int j=1;j<=L;++j)pwb[i][j]=(LL)pwb[i][j-1]*b[i]%Mod;
    }
    for(int i=0;i<=L;++i){
        pw[i][0]=1;
        for(int j=1;j<=n;++j)pw[i][j]=(LL)pw[i][j-1]*i%Mod;
    }
    frc[0]=1,ivf[0]=1;
    for(int i=1;i<=L;++i)
        frc[i]=(LL)frc[i-1]*i%Mod,ivf[i]=qpow(frc[i],Mod-2);
    // if(m+m+m<=n){
    if(m<=16){
        f[0][0][1]=1;
        for(int i=0;i<=n-m;++i)
            for(int S=1;S<(1<<m);S+=2)
                for(int U=(1<<m)-1-(S>>1),T=U;;T=(T-1)&U){
                    for(int j=0;j<=L;++j)if(f[i][j][S])
                        for(int k=0;j+k<=L;++k)
                            f[i+1][j+k][S>>1|T]=(f[i+1][j+k][S>>1|T]+(LL)f[i][j][S]*pw[k][__builtin_popcount(T)]%Mod*ivf[k]%Mod*pwb[i][k])%Mod;
                    if(!T)break;
                }
        for(int i=0;i<=L;++i)F[i]=(LL)f[n-m+1][i][(1<<m)-1]*frc[i]%Mod,cout<<F[i]<<" \n"[i==L];
        cout<<(LL)Langrange(F,L,c)*ans%Mod<<'\n';
    }
    else{

    }
    return 0;
}
/*
1 1 1 1 1 1 1 1 1 1 1 1
                1 1 1 1 1 1 1 1 1 1 1 1
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 781ms
memory: 12184kb

input:

50 8 538603133
67980 83398 26783 9496 18845 44534 25751 12189 79555 49066 87559 96963 11358 39078 24880 28212 34282 24882 137 65957 82361 13906 96900 98969 84165 18398 39061 3819 69062 26508 50351 14635 53121 29490 50901 32530 6748 40834 98869 30306 21857 78350 4599

output:

0 0 0 0 0 0 0 294201924 404139367 695653975 602317773 646300437 354397740 329449138 159048693 49384961 301738134 53921150 244644754 505423869 233202523 975021736 537150759 451315658 762406212 497394602 752544005 84991837 796522293 22792274 942125701 163914645 861479735 592118983 153550709 209123183 ...

result:

wrong answer 1st words differ - expected: '780535604', found: '0'

Subtask #2:

score: 0
Time Limit Exceeded

Test #3:

score: 0
Time Limit Exceeded

input:

50 16 741556017
69810 78288 21013 9835 661 55545 30670 5295 93027 2280 84775 68841 409 27907 27934 30629 4727 72420 32399 56614 387 66084 24179 58626 65756 40652 2761 38442 35627 60928 38003 70482 82058 80740 76968

output:


result:


Subtask #3:

score: 0
Wrong Answer

Test #5:

score: 0
Wrong Answer
time: 2ms
memory: 4868kb

input:

20 2 20
15733 41504 1298 31206 29251 80612 23096 62011 53587 93432 61688 29933 49923 56050 48077 18165 94224 89994 73376

output:

0 0 0 0 0 0 0 0 0 0 734393546 157727219 448288867 863586210 926071813 286584580 945066468 136280184 870854217 39603726 462941922 260854512
462941922

result:

wrong answer 1st words differ - expected: '462941922', found: '0'

Subtask #4:

score: 0
Wrong Answer

Test #16:

score: 0
Wrong Answer
time: 0ms
memory: 6676kb

input:

30 2 30
63840 50413 47135 89472 59483 28187 26327 20630 9120 5935 35689 11933 65347 7807 67870 97007 98326 57595 38213 70182 28242 45443 98275 17795 64068 90290 77827 40552 52025

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 680307478 627091345 830170977 992431160 674291494 431247190 246995575 723622108 533646738 472401996 118258744 888041902 670384505 967724908 795859193 325631710 907204525
325631710

result:

wrong answer 1st words differ - expected: '325631710', found: '0'

Subtask #5:

score: 0
Wrong Answer

Test #35:

score: 0
Wrong Answer
time: 0ms
memory: 8844kb

input:

40 2 40
35138 42435 44437 707 7353 69441 86322 53577 70023 6596 29411 46831 24261 46551 61944 37823 76356 70071 2125 29889 42261 75504 48476 73665 40836 83539 15019 32 70786 23007 75297 39802 45176 74888 64949 65975 20791 74909 3174

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 909689933 777519957 197070830 143534777 340292920 99245757 182449549 865941572 475452767 192723502 836855615 922798369 883151166 787954638 213374314 354093289 462675227 198307147 627595051 415912367 272092213 873060797
272092213

result:

wrong answer 1st words differ - expected: '272092213', found: '0'

Subtask #6:

score: 0
Wrong Answer

Test #60:

score: 0
Wrong Answer
time: 3ms
memory: 11424kb

input:

50 2 50
53029 77661 89821 96796 28335 72369 90651 95802 13374 29886 81635 88365 51184 98387 7102 32265 60561 23222 99406 30927 59740 76150 85630 96176 10160 70769 19803 42511 26180 40659 21813 44505 37884 93565 75651 24071 59735 21876 92814 23825 99659 86324 3121 57736 47497 42211 19049 28386 62614

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 800436502 195393334 781303092 313737081 437926236 664279388 57992288 92609854 41498640 121900183 611662206 795969249 182726039 841867660 213537869 907535433 528168580 752269992 886648193 400821832 387437534 452091143 295566309 439140799 384675857 966...

result:

wrong answer 1st words differ - expected: '966860170', found: '0'

Subtask #7:

score: 0
Wrong Answer

Test #91:

score: 0
Wrong Answer
time: 3ms
memory: 11428kb

input:

50 2 803148095
69632 6145 90266 98714 33652 25290 13413 24460 73968 20427 63478 45461 84799 58528 32781 71127 95223 49585 47134 68284 92786 64910 46840 90501 28361 70029 52269 71032 64637 4223 74513 31660 86876 17066 76967 7309 69967 29448 90148 51876 85305 47798 57822 85122 5026 11764 59061 42974 3...

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 254633553 20167056 968445462 628405263 314544200 724358381 977375101 967047573 801455404 424505299 447491901 417515786 477354538 41794425 180682172 133538852 402826011 9593905 651517297 233454640 102830106 448774089 86616653 158910669 797987466 94800...

result:

wrong answer 1st words differ - expected: '76793352', found: '0'