QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#421669#619. 多项式求逆light_ink_dots100 ✓519ms114432kbC++143.0kb2024-05-26 00:31:112024-05-26 00:31:12

Judging History

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

  • [2024-05-26 00:31:12]
  • 评测
  • 测评结果:100
  • 用时:519ms
  • 内存:114432kb
  • [2024-05-26 00:31:11]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,g=3;
using ll = long long;
ll w[1<<21];
ll qpow(ll a,ll b){
    ll ret=1;
    while(b){
        if(b&1) ret=ret*a%mod;
        a=a*a%mod;b>>=1;
    }return ret;
}
void init(){
    for(int mid=1;mid<(1<<21);mid<<=1){
        ll wn=qpow(3,(mod-1)/(mid*2));
        w[mid]=1;
        for(int k=1;k<mid;k++) w[mid+k]=w[mid+k-1]*wn%mod;
    }
}
void upd(ll &x){
    x-=(x>=mod?mod:0);
}
struct poly{
    vector<ll>a;
    // size -> 最高项次数
    // resize -> mod x^{n+1}
    int size()const{return (int)(a.size())-1;}
    void resize(int n){a.resize(n+1);}
    void reduce(int n){
        if(size()>n) resize(n);
    }
    poly(){}
    poly(int n){resize(n);}
    poly(const vector<ll>&_a){a=_a;}
    ll&operator[](int n){return a[n];}

    void dif(int lim){
        a.resize(lim);
        for(int mid=1;mid<lim;mid<<=1){
            for(int j=0;j<lim;j+=(mid<<1)){
                ll x=a[j],y=a[j+mid];
                upd(a[j]=x+y);
                upd(a[j+mid]=x-y+mod);
                for(int k=1;k<mid;k++){
                    ll x=a[j+k],y=a[j+k+mid]*(mod-w[2*mid-k])%mod;
                    upd(a[j+k]=x+y);
                    upd(a[j+k+mid]=x-y+mod);
                }
            }
        }
        ll inv=qpow(lim,mod-2);
        for(int i=0;i<lim;i++)a[i]=a[i]*inv%mod;
    }
    void dit(int lim){
        a.resize(lim);        
        for(int mid=(lim>>1);mid>=1;mid>>=1){
            for(int j=0;j<lim;j+=(mid<<1)){
                for(int k=0;k<mid;k++){
                    ll x=a[j+k],y=a[j+k+mid];
                    upd(a[j+k]=x+y);
                    (a[j+k+mid]=(x-y+mod)*w[mid+k])%=mod;
                }
            }
        }
    }
    poly operator *(const poly &b)const{
        poly c=(*this),d=b;
        int len=c.size()+d.size(),lim=1;
        while(lim<=len) lim<<=1;
        c.dit(lim),d.dit(lim);
        for(int i=0;i<lim;i++) c[i]=c[i]*d[i]%mod;
        c.dif(lim);c.resize(len);
        return c;
    }
    poly operator +(const poly &b){
        poly c=(*this),d=b;int len=max(c.size(),d.size());
        c.resize(len),d.resize(len);
        for(int i=0;i<=len;i++)upd(c[i]+=d[i]);
        return c;
    }
    poly operator -(const poly &b){
        poly c=(*this),d=b;int len=max(c.size(),d.size());
        c.resize(len),d.resize(len);
        for(int i=0;i<=len;i++)upd(c[i]=c[i]-d[i]+mod);
        return c;
    }
    // mod x^{lim}
    poly inv(int lim){
        if(lim==1){
            return vector<ll>{qpow(a[0],mod-2)};
        }
        poly c=(*this),ans;
        c.a.resize(lim);
        int l=(lim+1)/2;
        poly inv=c.inv(l);
        ans=(inv+inv)-(inv*inv)*c;
        ans.a.resize(lim);
        return ans;
    }
};
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    init();
    int n;
    cin>>n;
    
    poly a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    a=a.inv(n);
    for(int i=0;i<n;i++) cout<<(a[i])<<" ";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 20
Accepted
time: 7ms
memory: 20244kb

input:

100
321704272 732147873 495950455 607498198 139258053 834073875 837326587 9642661 903437916 207412353 359180940 720085797 719290810 723076036 984279000 503225771 350175866 162829281 512559053 225874248 808881115 775602122 556705696 16814894 894905093 985867138 253650922 979472539 59109787 205995179 ...

output:

890391751 343178682 709950581 248573740 155003792 121063153 971739900 888240696 926095011 284929631 882976199 542279543 131651533 977789433 167757891 918195456 560856885 755976112 34039567 302980664 467112024 458903443 580863066 232408790 712746461 420666055 220260689 852614570 788749038 702552591 7...

result:

ok 100 numbers

Test #2:

score: 20
Accepted
time: 18ms
memory: 20568kb

input:

5000
895174753 48640370 621768187 544696442 266653647 800854366 993400253 180889611 259138834 922465819 237366500 134204023 882884556 962623362 906378209 783980105 385064692 526608265 306798389 492937123 600567928 363960265 499995507 901802313 322681104 915889147 191761221 168327309 250045818 379937...

output:

682334353 436976416 775272797 222487943 387482624 578444714 913440174 91807434 793656036 840531807 501588255 564297941 790458031 279039057 788782851 217732094 55414463 556674881 556372136 207469922 22960536 808480214 237927525 393440457 740345941 957397909 844601165 902029038 247139335 2283882 54979...

result:

ok 5000 numbers

Test #3:

score: 20
Accepted
time: 16ms
memory: 22668kb

input:

30000
433849057 26933151 94119735 348782922 994201565 286266085 253836562 391505281 561460922 76317536 151770395 626212470 835627785 278418333 560388198 586773695 43090005 450934659 716357773 746228248 47588293 745422420 131896260 923566007 275614901 981279191 966289868 111837778 850083076 346727100...

output:

357845866 278279787 282399673 535141130 667648994 63737517 190046919 326102148 662204122 372177710 538590284 867601509 319250982 253971547 418533239 965211653 475013466 104848869 679833017 632683281 154028567 253417158 839386097 24193741 852729812 320234422 132258378 976799786 627417267 278166273 69...

result:

ok 30000 numbers

Test #4:

score: 20
Accepted
time: 54ms
memory: 29560kb

input:

100000
299085935 896290047 664961463 798136437 284888760 805376081 754380153 982440654 523416648 618138054 639229548 946675552 216492659 801950754 591895463 409803161 734598818 262678735 505505080 132772037 241184558 549895828 778274609 60046418 766879997 555641192 925835147 535599922 727361907 2850...

output:

152663231 835829855 733898831 594740161 134406704 39940730 895052135 225966750 351630054 544215344 168586029 481785131 709831593 661056822 235154057 493601823 22230265 160367609 731879071 652142676 233990007 379664191 476172493 836696871 945774957 283346933 426801303 581100604 610982192 940304348 20...

result:

ok 100000 numbers

Test #5:

score: 20
Accepted
time: 519ms
memory: 114432kb

input:

1000000
737044976 941398691 939287417 273413335 175365852 377721127 3862986 176449650 791765055 129385383 433663518 447033570 279210233 157228851 130509370 963480863 130226624 349605390 600289609 890766355 577960206 537162643 776878360 951933771 688851169 624945579 212339598 106077966 426859950 6284...

output:

132989151 967059052 786729095 295714400 843866645 542289704 638143213 207481112 446873321 624453140 958686844 258794555 550695242 743692998 516890675 385380109 836809295 113229280 462660716 69696753 540082084 371436342 91926456 920757361 674622038 5073352 596619469 904942082 754387425 151809515 1285...

result:

ok 1000000 numbers