QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#126666#620. 多项式对数函数SoyTony#100 ✓554ms120512kbC++144.1kb2023-07-18 21:10:122023-07-18 21:10:16

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-18 21:10:16]
  • 评测
  • 测评结果:100
  • 用时:554ms
  • 内存:120512kb
  • [2023-07-18 21:10:12]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const int maxn=(1<<21)+10;
const int lim=(1<<21);
const int mod=998244353;

inline int read(){
    int x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}

inline int q_pow(int A,int B,int P){
    int res=1;
    while(B){
        if(B&1) res=1ll*res*A%P;
        A=1ll*A*A%P;
        B>>=1;
    }
    return res;
}

int inv[maxn];
int rev[maxn];
int base,w[maxn];
struct Poly{
    const static int g=3;
    int deg;
    vector<ull> f;
    ull &operator[](const int &i){return f[i];}
    ull operator[](const int &i)const{return f[i];}
    inline void set(int L){deg=L;f.resize(L);}
    inline void clear(int L,int R){for(int i=L;i<=R;++i)f[i]=0;}
    inline void output(int L){for(int i=0;i<L;++i)printf("%llu ",f[i]);printf("\n");}
    inline void NTT(int L,bool type){
        set(L);
        for(int i=1;i<L;++i){
            rev[i]=(rev[i>>1]>>1)+(i&1?L>>1:0);
            if(i<rev[i]) swap(f[i],f[rev[i]]);
        }
        for(int d=1;d<L;d<<=1){
            base=q_pow(type?g:q_pow(g,mod-2,mod),(mod-1)/(2*d),mod);
            w[0]=1;
            for(int i=1;i<d;++i) w[i]=1ll*w[i-1]*base%mod;
            for(int i=0;i<L;i+=d<<1){
                for(int j=0;j<d;++j){
                    ull x=f[i+j],y=f[i+d+j]*w[j]%mod;
                    f[i+j]=x+y,f[i+d+j]=x-y+mod;
                }
            }
        }
        for(int i=0;i<L;++i) f[i]%=mod;
        if(!type){
            int inv_L=q_pow(L,mod-2,mod);
            for(int i=0;i<L;++i) f[i]=f[i]*inv_L%mod;
        }
    }
    inline Poly Differntial(int n){
        Poly F;
        F.set(n);
        for(int i=1;i<n;++i) F[i-1]=f[i]*i%mod;
        return F;
    } 
    inline Poly Integral(int n){
        Poly F;
        F.set(n+1);
        for(int i=0;i<n;++i) F[i+1]=f[i]*inv[i+1]%mod;
        return F;
    }
    inline Poly Inv(int n){
        Poly F,G;
        G.set(1);
        G[0]=q_pow(f[0],mod-2,mod);
        for(int L=2;L<2*n;L<<=1){
            F.set(2*L),G.set(2*L);
            F.clear(0,2*L-1);
            for(int i=0;i<L;++i) F[i]=f[i];
            F.NTT(2*L,1),G.NTT(2*L,1);
            for(int i=0;i<2*L;++i) G[i]=1ll*(int)G[i]*(2ll-1ll*(int)G[i]*(int)F[i]%mod+mod)%mod;
            G.NTT(2*L,0);
            G.clear(min(n,L),2*L-1);
        }
        return G;
    }
    inline Poly Sqrt(int n){
        Poly F,G,invG,H;
        G.set(1);
        G[0]=1;
        for(int L=2;L<2*n;L<<=1){
            F.set(2*L),G.set(2*L),H.set(2*L);
            F.clear(0,2*L-1);
            for(int i=0;i<L;++i) F[i]=f[i];
            invG=G.Inv(L);
            F.NTT(2*L,1),invG.NTT(2*L,1);
            for(int i=0;i<2*L;++i) H[i]=F[i]*invG[i]%mod*inv[2]%mod;
            H.NTT(2*L,0);
            for(int i=0;i<2*L;++i) G[i]=(H[i]+G[i]*inv[2]%mod)%mod;
            G.clear(min(n,L),2*L-1);
        }
        return G;
    }
    inline Poly Ln(int n){
        Poly dF,invF,G,H;
        dF=Differntial(n),invF=Inv(n);
        int L=1;
        while(L<2*n) L<<=1;
        dF.set(L),invF.set(L),G.set(L);
        dF.NTT(L,1),invF.NTT(L,1);
        for(int i=0;i<L;++i) G[i]=dF[i]*invF[i]%mod;
        G.NTT(L,0);
        H=G.Integral(L);
        H.clear(n,L);
        return H;
    }
    inline Poly Exp(int n){
        Poly F,G,lnG;
        G.set(1);
        G[0]=1;
        for(int L=2;L<2*n;L<<=1){
            F.set(2*L),G.set(2*L);
            F.clear(0,2*L-1);
            for(int i=0;i<L;++i) F[i]=f[i];
            lnG=G.Ln(L);
            F.NTT(2*L,1),G.NTT(2*L,1),lnG.NTT(2*L,1);
            for(int i=0;i<2*L;++i) G[i]=G[i]*(1ull-lnG[i]+F[i]+mod)%mod;
            G.NTT(2*L,0);
            G.clear(min(n,L),2*L-1);
        }
        return G;
    }
}F,G;

int n;

int main(){
    inv[1]=1;
    for(int i=2;i<=lim+1;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    n=read();
    F.set(4*n);
    for(int i=0;i<n;++i) F[i]=read();
    G=F.Ln(n);
    G.output(n);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 20
Accepted
time: 12ms
memory: 13152kb

input:

100
1 961880754 72654790 829592288 646635609 311233105 453229378 664750040 147019368 89089702 319123224 785184513 130058112 232462250 915136660 400585378 710632575 470300421 785452776 22895339 267215672 816821438 688384368 814593296 401856501 121390605 474566074 229876909 179995671 479480781 1150666...

output:

0 961880754 109050820 910057683 452181005 796593970 362074759 53194053 540144365 291711835 996774416 338261551 172006522 156841252 598600919 311016398 440325847 20403335 269495509 528824266 723093435 143651758 274603604 232097861 366573798 240410404 263548039 813262296 718323828 688147861 784480664 ...

result:

ok 100 numbers

Test #2:

score: 20
Accepted
time: 11ms
memory: 13624kb

input:

5000
1 18893689 800248942 590834626 422952919 370806502 832521768 157416021 449498617 50268466 481346733 588328257 836431005 172279377 701248316 688081741 641390799 971605524 529682685 15073211 370474889 330708737 461612260 427248257 124799236 2295287 579063610 911278897 850964373 680664511 61289593...

output:

0 18893689 649428805 738833568 120891255 19670140 608054187 781421921 559764661 292759237 202235517 465634637 516704148 737098204 892179011 495729143 603364788 154939005 564276135 247402588 951327329 502706506 503981602 661783358 672492854 55298928 349262035 379325690 748797260 36812211 286288663 84...

result:

ok 5000 numbers

Test #3:

score: 20
Accepted
time: 24ms
memory: 15724kb

input:

30000
1 970882639 503981013 404846066 863588691 801944716 361233000 107564825 85420624 950377978 209112662 646496760 470328364 139325904 593853922 301851602 265141963 464762654 225023703 474139631 555855644 900153878 865682768 387642831 292054593 592453364 468382456 907565611 122026085 280142449 472...

output:

0 970882639 457403585 873878370 318261289 5420793 914065224 347039061 368768664 63992668 817003966 398719209 868368828 188152960 579963976 211917006 499838248 97901028 786777661 15634701 242132107 434131354 537665508 126497027 873212165 645988134 766323255 611262222 83799227 780873982 171681961 5453...

result:

ok 30000 numbers

Test #4:

score: 20
Accepted
time: 66ms
memory: 25032kb

input:

100000
1 636749537 301358055 13535739 884134558 389669951 669242330 226185280 157140037 941409936 290390837 486338369 9840834 587277544 277161163 427234947 202859695 898077735 682355257 509533156 571238511 227077530 100718382 191992899 462596953 832899262 101253983 596098985 595161513 259772722 4995...

output:

0 636749537 893745725 208856897 833356726 645101318 331081085 674809362 376515893 529729696 159424368 64304300 38260664 651978624 757150457 656660176 981816671 482124761 664996997 340575888 544387934 224993025 630282066 889077734 595392417 65927703 145196506 381507561 80669600 779290852 657316164 76...

result:

ok 100000 numbers

Test #5:

score: 20
Accepted
time: 554ms
memory: 120512kb

input:

1000000
1 785396418 410648986 62677121 16031158 710742216 677635002 789886669 737278658 655583592 459342332 542680522 553715144 799887527 99957827 533567330 838324845 788131790 637348498 428285164 429527739 233116765 772393666 138968071 917779658 494447494 910763455 642522636 855227115 698468466 219...

output:

0 785396418 121390930 573141379 208264134 820348528 437016261 369027464 119111821 432492474 342634043 694859972 192041833 336177730 969184881 829638906 173117766 779517533 982980311 517238274 459092122 579250908 924006190 697936237 885177047 350279990 695355377 923665009 83389011 582391001 956169113...

result:

ok 1000000 numbers