QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#642384#622. 多项式多点求值Zhou_JK100 ✓5331ms345984kbC++2315.4kb2024-10-15 13:41:562024-10-15 14:10:17

Judging History

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

  • [2024-10-15 14:10:17]
  • 评测
  • 测评结果：100
  • 用时：5331ms
  • 内存：345984kb
查看
  • [2024-10-15 13:41:56]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cassert>
#include<ctime>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
using namespace std;
namespace Polynomial
{
constexpr int g=3;
constexpr int MOD=998244353;
int add(int a,int b)
{
    a+=b;
    return a>=MOD?a-MOD:a;
}
int sub(int a,int b)
{
    return a>=b?a-b:a+MOD-b;
}
int qpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=(long long)res*a%MOD;
        a=(long long)a*a%MOD,b>>=1;
    }
    return res;
}
int getinv(int x)
{
    return qpow(x,MOD-2);
}
typedef vector<int> Poly;
Poly operator+(const Poly &a,const Poly &b)
{
    Poly f=a,g=b;
    int n=max(a.size(),b.size());
    f.resize(n),g.resize(n);
    Poly c(n);
    for(int i=0;i<n;i++)
    {
        c[i]=f[i]+g[i];
        if(c[i]>=MOD) c[i]-=MOD;
    }
    return c;
}
Poly operator-(const Poly &a,const Poly &b)
{
    Poly f=a,g=b;
    int n=max(a.size(),b.size());
    f.resize(n),g.resize(n);
    Poly c(n);
    for(int i=0;i<n;i++)
    {
        c[i]=f[i]-g[i];
        if(c[i]<0) c[i]+=MOD;
    }
    return c;
}
Poly operator+(const Poly &F,const int &x)
{
    Poly f=F;
    f[0]+=x;
    if(f[0]>=MOD) f[0]-=MOD;
    return f;
}
Poly operator+(const int &x,const Poly &F)
{
    Poly f=F;
    f[0]+=x;
    if(f[0]>=MOD) f[0]-=MOD;
    return f;
}
Poly operator-(const Poly &F,const int &x)
{
    Poly f=F;
    f[0]-=x;
    if(f[0]<0) f[0]+=MOD;
    return f;
}
Poly operator-(const int &x,const Poly &F)
{
    Poly f=F;
    int n=f.size()-1;
    for(int i=0;i<=n;i++)
        f[i]=MOD-f[i];
    f[0]+=x;
    if(f[0]>=MOD) f[0]-=MOD;
    return f;
}
int gw[(1<<21)+1];
vector<int>inv;
void init(int _n)
{
    static int n=1;
    if(_n<n) return;
    int t=1;
    while((1<<t)<_n) t++;
    t=min(t-1,21);
    gw[0]=1,gw[1<<t]=qpow(31,1<<(21-t));
    for(int i=t;i>0;i--)
        gw[1<<(i-1)]=(long long)gw[1<<i]*gw[1<<i]%MOD;
    for(int i=1;i<(1<<t);i++)
        gw[i]=(long long)gw[i&(i-1)]*gw[i&-i]%MOD;
    inv.resize(_n+1);
    inv[1]=1;
    for(int i=2;i<=_n;i++)
        inv[i]=(long long)(MOD-MOD/i)*inv[MOD%i]%MOD;
    n=_n;
    return;
}
constexpr int BIT=10;
void dft(Poly &F,int _n)
{
    int n=1;
    while(n<_n) n<<=1;
    init(n);
    F.resize(n);
    vector<unsigned long long>f(n);
    for(int i=0;i<n;i++)
        f[i]=F[i];
    for(int len=n;len>1;len>>=1)
    {
        if((len>>BIT)&1)
        {
            for(int i=0;i<n;i++)
                f[i]%=MOD;
        }
        for(int i=0,*w=gw;i<n;i+=len,w++)
            for(int k=i;k<i+(len>>1);k++)
            {
                unsigned long long l=f[k];
                int r=(*w)*f[k+(len>>1)]%MOD;
                f[k]=l+r;
                f[k+(len>>1)]=l+MOD-r;
            }
    }
    for(int i=0;i<n;i++)
        F[i]=f[i]%MOD;
    return;
}
void idft(Poly &F,int _n)
{
    int n=1;
    while(n<_n) n<<=1;
    init(n);
    F.resize(n);
    vector<unsigned long long>f(n);
    for(int i=0;i<n;i++)
        f[i]=F[i];
    for(int len=2;len<=n;len<<=1)
    {
        if((len>>BIT)&1)
        {
            for(int i=0;i<n;i++)
                f[i]%=MOD;
        }
        for(int i=0,*w=gw;i<n;i+=len,w++)
            for(int k=i;k<i+(len>>1);k++)
            {
                unsigned long long l=f[k];
                int r=f[k+(len>>1)]%MOD;
                f[k]=l+r;
                f[k+(len>>1)]=(l+MOD-r)*(*w)%MOD;
            }
    }
    int invn=getinv(n);
    for(int i=0;i<n;i++)
        F[i]=f[i]%MOD*invn%MOD;
    reverse(F.begin()+1,F.end());
    return;
}
Poly ntt(const Poly &F,const Poly &G,const function<int(int,int)> &mul)
{
    Poly f=F,g=G;
    int n=f.size()-1,m=g.size()-1;
    m+=n,n=1;
    while(n<=m) n<<=1;
    f.resize(n);
    g.resize(n);
    dft(f,n);
    dft(g,n);
    for(int i=0;i<n;i++)
        f[i]=mul(f[i],g[i]);
    idft(f,n);
    f.resize(m+1);
    return f;
}
Poly operator*(const Poly &F,const Poly &G)
{
    Poly f=F,g=G;
    int n=f.size()-1,m=g.size()-1;
    m+=n,n=1;
    while(n<=m) n<<=1;
    f.resize(n);
    g.resize(n);
    dft(f,n);
    dft(g,n);
    for(int i=0;i<n;i++)
        f[i]=(long long)f[i]*g[i]%MOD;
    idft(f,n);
    f.resize(m+1);
    return f;
}
Poly operator*(const Poly &F,const int &x)
{
    Poly f=F;
    int n=f.size()-1;
    for(int i=0;i<=n;i++)
        f[i]=(long long)f[i]*x%MOD;
    return f; 
}
Poly operator*(const int &x,const Poly &F)
{
    Poly f=F;
    int n=f.size()-1;
    for(int i=0;i<=n;i++)
        f[i]=(long long)f[i]*x%MOD;
    return f; 
}
Poly getinv(const Poly &F)
{
    Poly f=F;
    int m=f.size()-1;
    int n=1;
    while(n<=m) n<<=1;
    f.resize(n);
    Poly g={getinv(f[0])};
    for(int m=2;m<=n;m<<=1)
    {
        Poly t(f.begin(),f.begin()+m);
        g=ntt(t,g,[&](const int &x,const int &y){return (2*y-(long long)y*y%MOD*x%MOD+MOD)%MOD;});
        g.resize(m);
    }
    g.resize(m+1);
    return g;
}
int w;
struct Complex
{
    int real,imag;
    bool operator ==(const Complex &b)const
    {
        return real==b.real&&imag==b.imag;
    }
    Complex operator *(const Complex &b)const
    {
        Complex res;
        res.real=((long long)real*b.real+(long long)w*imag%MOD*b.imag)%MOD;
        res.imag=((long long)real*b.imag+(long long)imag*b.real)%MOD;
        return res;
    }
    friend Complex qpow(Complex a,int b)
    {
        Complex res=(Complex){1,0};
        while(b)
        {
            if(b&1) res=res*a;
            a=a*a,b>>=1;
        }
        return res;
    }
};
int cipolla(int n)
{
    static mt19937 myrand(time(NULL));
    if(n==0) return 0;
    function<bool(int)>check=[&](const int &n){return qpow(n,(MOD-1)/2)==1;};
    if(!check(n)) return -1;
    int a=myrand()%(MOD-1)+1;
    while(check(((long long)a*a-n+MOD)%MOD)) a=myrand()%(MOD-1)+1;
    w=((long long)a*a-n+MOD)%MOD;
    Complex res=qpow((Complex){a,1},(MOD+1)/2);
    return res.real;
}
Poly sqrt(const Poly &F)
{
    Poly f=F;
    int m=f.size()-1;
    int n=1;
    while(n<=m) n<<=1;
    f.resize(n);
    int g0=cipolla(f[0]);
    Poly g={min(g0,MOD-g0)};
    int inv2=getinv(2);
    for(int m=2;m<=n;m<<=1)
    {
        Poly t(f.begin(),f.begin()+m);
        g.resize(m);
        g=g*inv2+ntt(t,getinv(g),[&](const int &x,const int &y){return (long long)inv2*x%MOD*y%MOD;});
        g.resize(m);
    }
    g.resize(m+1);
    return g;
}
Poly operator/(const Poly &F,const Poly &G)
{
    Poly f=F,g=G;
    int n=f.size()-1,m=g.size()-1;
    if(n<m) return Poly(n-m+1,0);
    reverse(f.begin(),f.end());
    reverse(g.begin(),g.end());
    f.resize(n-m+1);
    g.resize(n-m+1);
    Poly q=f*getinv(g);
    q.resize(n-m+1);
    reverse(q.begin(),q.end());
    return q;
}
Poly operator%(const Poly &F,const Poly &G)
{
    Poly f=F,g=G,q=f/g;
    int m=g.size()-1;
    g.resize(m);
    q.resize(m);
    Poly c=g*q;
    c.resize(m);
    f.resize(m);
    return f-c;
}
Poly diff_calc(const Poly &F)
{
    Poly f=F;
    int n=f.size()-1;
    Poly g(n);
    for(int i=1;i<=n;i++)
        g[i-1]=(long long)f[i]*i%MOD;
    return g;
}
Poly inte_calc(const Poly &G)
{
    Poly g=G;
    int n=g.size()-1;
    init(n+2);
    Poly f(n+2);
    for(int i=1;i<=n+1;i++)
        f[i]=(long long)g[i-1]*inv[i]%MOD;
    return f;
}
Poly ln(const Poly &F)
{
    Poly f=F;
    int n=f.size()-1;
    Poly g=diff_calc(f)*getinv(f);
    g.resize(n+1);
    g=inte_calc(g);
    g.resize(n+1);
    return g;
}
Poly exp(const Poly &F)
{
    Poly f=F;
    int m=f.size()-1;
    int n=1;
    while(n<=m) n<<=1;
    f.resize(n);
    Poly g={1};
    for(int m=2;m<=n;m<<=1)
    {
        Poly t(f.begin(),f.begin()+m);
        Poly s=g;
        g.resize(m);
        g=s*(t-ln(g)+(Poly){1});
        g.resize(m);
    }
    g.resize(m+1);
    return g;
}
Poly qpow(const Poly &F,const int &k)
{
    Poly f=F;
    int n=f.size()-1;
    Poly g(n+1);
    int pos=-1;
    for(int i=0;i<=n;i++)
        if(f[i]>0)
        {
            g[i]=f[i];
            pos=i;
            break;
        }
    if(pos==-1) return g;
    int mu=f[pos],invm=getinv(mu);
    for(int i=0;i<=n-pos;i++)
        f[i]=(long long)f[i+pos]*invm%MOD;
    for(int i=n-pos+1;i<=n;i++)
        f[i]=0;
    g[pos]=0;
    if((long long)pos*k<=n||pos==0) 
    {
        g=exp(k*ln(f));
        int v=qpow(mu,k);
        for(int i=n;i>=pos*k;i--)
            g[i]=(long long)g[i-pos*k]*v%MOD;
        for(int i=pos*k-1;i>=0;i--)
            g[i]=0;
    }
    return g;
}
int poly_calc(const Poly &F,const int &x)
{
    Poly f=F;
    int n=f.size()-1;
    int fc=1,res=0;
    for(int i=0;i<=n;i++)
        res=(res+(long long)f[i]*fc)%MOD,fc=(long long)fc*x%MOD;
    return res;
}
Poly or_convolution(const Poly &F,const Poly &G)
{
    Poly f=F,g=G;
    int m=max(f.size()-1,g.size()-1),n=1;
    while(n<=m) n<<=1;
    f.resize(n),g.resize(n);
    auto fwt=[&](Poly &F)
    {
        int n=F.size();
        for(int len=2;len<=n;len<<=1)
            for(int i=0;i<n;i+=len)
                for(int k=i;k<i+(len>>1);k++)
                    F[k+(len>>1)]=add(F[k+(len>>1)],F[k]);
        return;
    };
    fwt(f);
    fwt(g);
    for(int i=0;i<n;i++)
        f[i]=(long long)f[i]*g[i]%MOD;
    auto ifwt=[&](Poly &F)
    {
        int n=F.size();
        for(int len=2;len<=n;len<<=1)
            for(int i=0;i<n;i+=len)
                for(int k=i;k<i+(len>>1);k++)
                    F[k+(len>>1)]=sub(F[k+(len>>1)],F[k]);
        return;
    };
    ifwt(f);
    return f;
}
Poly and_convolution(const Poly &F,const Poly &G)
{
    Poly f=F,g=G;
    int m=max(f.size()-1,g.size()-1),n=1;
    while(n<=m) n<<=1;
    f.resize(n),g.resize(n);
    function<void(Poly &)> fwt=[&](Poly &F)
    {
        int n=F.size();
        for(int len=2;len<=n;len<<=1)
            for(int i=0;i<n;i+=len)
                for(int k=i;k<i+(len>>1);k++)
                    F[k]=add(F[k],F[k+(len>>1)]);
        return;
    };
    fwt(f);
    fwt(g);
    for(int i=0;i<n;i++)
        f[i]=(long long)f[i]*g[i]%MOD;
    function<void(Poly &)> ifwt=[&](Poly &F)
    {
        int n=F.size();
        for(int len=2;len<=n;len<<=1)
            for(int i=0;i<n;i+=len)
                for(int k=i;k<i+(len>>1);k++)
                    F[k]=sub(F[k],F[k+(len>>1)]);
        return;
    };
    ifwt(f);
    return f;
}
Poly xor_convolution(const Poly &F,const Poly &G)
{
    Poly f=F,g=G;
    int m=max(f.size()-1,g.size()-1),n=1;
    while(n<=m) n<<=1;
    f.resize(n),g.resize(n);
    function<void(Poly &)> fwt=[&](Poly &F)
    {
        int n=F.size();
        for(int len=2;len<=n;len<<=1)
            for(int i=0;i<n;i+=len)
                for(int k=i;k<i+(len>>1);k++)
                {
                    int l=F[k],r=F[k+(len>>1)];
                    F[k]=add(l,r);
                    F[k+(len>>1)]=sub(l,r);
                }
        return;
    };
    fwt(f);
    fwt(g);
    for(int i=0;i<n;i++)
        f[i]=(long long)f[i]*g[i]%MOD;
    function<void(Poly &)> ifwt=[&](Poly &F)
    {
        int n=F.size();
        for(int len=2;len<=n;len<<=1)
            for(int i=0;i<n;i+=len)
                for(int k=i;k<i+(len>>1);k++)
                {
                    int l=F[k],r=F[k+(len>>1)];
                    F[k]=add(l,r);
                    F[k+(len>>1)]=sub(l,r);
                }
        int invn=getinv(n);
        for(int i=0;i<(int)F.size();i++)
            F[i]=(long long)F[i]*invn%MOD;
        return;
    };
    ifwt(f);
    return f;
}
int &reduce(int &x)
{
    return x+=x>>31&MOD;
}
Poly subset_convolution(const Poly &F,const Poly &G)
{
    int m=max(F.size()-1,G.size()-1),n=1,c=1;
    while(n<=m) n<<=1,c++;
    vector<Poly> f(c+1,Poly(n,0)),g(c+1,Poly(n,0));
    for(int i=0;i<(int)F.size();i++)
        f[__builtin_popcount(i)][i]=F[i];
    for(int i=0;i<(int)G.size();i++)
        g[__builtin_popcount(i)][i]=G[i];
    function<void(Poly &)> fwt=[&](Poly &F)
    {
        int n=F.size();
        vector<unsigned long long>f(n);
        for(int i=0;i<n;i++)
            f[i]=F[i];
        for(int len=2;len<=n;len<<=1)
        {
            if((len>>BIT)&1)
            {
                for(int i=0;i<n;i++)
                    f[i]%=MOD;
            }
            for(int i=0;i<n;i+=len)
                for(int k=i;k<i+(len>>1);k++)
                {
                    unsigned long long l=F[k];
                    int r=F[k+(len>>1)]%MOD;
                    F[k]=l+r;
                    F[k+(len>>1)]=l+MOD-r;
                }
        }
        for(int i=0;i<n;i++)
            F[i]=f[i]%MOD;
        return;
    };
    for(int i=0;i<=c;i++)
        fwt(f[i]),fwt(g[i]);
    vector<Poly> h(c+1,Poly(n,0));
    for(int i=0;i<=c;i++)
        for(int j=0;j<=i;j++)
        {
            int k=i-j;
            for(int s=0;s<n;s++)
                h[i][s]=(h[i][s]+(long long)f[j][s]*g[k][s])%MOD;
        }
    function<void(Poly &)> ifwt=[&](Poly &F)
    {
        int n=F.size();
        for(int len=2;len<=n;len<<=1)
            for(int i=0;i<n;i+=len)
                for(int k=i;k<i+(len>>1);k++)
                {
                    int l=F[k],r=F[k+(len>>1)];
                    F[k]=add(l,r);
                    F[k+(len>>1)]=sub(l,r);
                }
        int invn=getinv(n);
        for(int i=0;i<(int)F.size();i++)
            F[i]=(long long)F[i]*invn%MOD;
        return;
    };
    for(int i=0;i<=c;i++)
        ifwt(h[i]);
    Poly res(n);
    for(int i=0;i<n;i++)
        res[i]=h[__builtin_popcount(i)][i];
    return res;
}
Poly cyclic_convolution(const Poly &a,const Poly &b)
{
    assert(a.size()==b.size());
    int n=a.size();
    Poly c=a*b;
    for(int i=n;i<(int)c.size();i++)
        c[i-n]=add(c[i],c[i-n]);
    c.resize(n);
    return c;
}
}
using namespace Polynomial;
vector<Poly>G;
Poly MulT(Poly a,Poly b)
{
    int n=a.size(),m=b.size(); 
    reverse(a.begin(),a.end());
    a=a*b;
    for(int i=0;i<m;i++)
        b[i]=a[i+n-1];
    return b;
}
void Multipoints(int k,int l,int r,Poly F,Poly &v)
{
    F.resize(r - l + 1);
    if(l==r)
    {
        v[l]=F[0];
        return;
    }
    int m=(l+r)/2;
    Multipoints(k*2,l,m,MulT(G[k*2+1],F),v);
    Multipoints(k*2+1,m+1,r,MulT(G[k*2],F),v);
    return;
}

Poly poly_multiple_point_evaluation(const Poly &F,const Poly &A)
{
    Poly f=F,a=A;
    int m=max(f.size()-1,a.size());
    f.resize(m+1),a.resize(m);
    G.resize(m<<2);
    function<void(int,int,int)> poly_multiple_point_evaluation_init=[&](int i,int l,int r)
    {
        if(l==r)
        {
            G[i]=(Poly){1,a[l]==0?0:MOD-a[l]};
            return;
        }
        int mid=(l+r)/2;
        poly_multiple_point_evaluation_init(i*2,l,mid);
        poly_multiple_point_evaluation_init(i*2+1,mid+1,r);
        G[i]=G[i*2]*G[i*2+1];
        return;
    };
    poly_multiple_point_evaluation_init(1,0,m-1);
    Poly v(m);
    Multipoints(1,0,m-1,MulT(getinv(G[1]),f),v);
    return v;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    Poly f(n);
    for(int i=0;i<n;i++)
        cin>>f[i];
    Poly g(m);
    for(int i=0;i<m;i++)
        cin>>g[i];
    Poly v(m);
    v=poly_multiple_point_evaluation(f,g);
    for(int i=0;i<m;i++)
        cout<<v[i]<<"\n";
    return 0;
}
源文件, 语言: C++23

详细


Pretests


Final Tests

Test #1:

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

input:

100 94
575336069 33153864 90977269 80162592 25195235 334936051 108161572 14050526 356949084 797375084 805865808 286113858 995555121 938794582 458465004 379862532 563357556 293989886 273730531 13531923 113366106 126368162 405344025 443053020 475686818 734878619 338356543 661401660 834651229 527993675...

output:

940122667
397187437
905033404
346709388
146347009
49596361
125616024
966474950
693596552
162411542
248699477
217639076
254290825
963991654
951375739
431661136
587466850
933820245
135676159
683994808
821695954
675479292
463904298
15085475
183389374
976945620
668527277
98940366
909505808
904450031
968...

result:

ok 94 numbers

Test #2:

score: 20
Accepted
time: 17ms
memory: 5192kb

input:

5000 4999
410683245 925831211 726803342 144364185 955318244 291646122 334752751 893945905 484134283 203760731 533867267 813509277 491860093 413174124 584582617 594704162 976489328 978500071 196938934 628117769 169796671 858963950 562124570 582491326 647830593 238623335 20782490 674939336 656529076 2...

output:

683038054
713408290
776843174
52275065
602085453
905088100
991748340
720305324
831850056
296147844
79380797
882313010
941965313
987314872
363655479
380838721
51243733
165728533
592641557
679475455
651115426
60492203
787012426
247557193
136399242
484592897
908383514
735275879
648228244
443933835
5504...

result:

ok 4999 numbers

Test #3:

score: 20
Accepted
time: 114ms
memory: 13072kb

input:

30000 29995
536696866 881441742 356233606 594487396 991820796 695996817 7219464 149265950 843761437 329761701 260625152 80366362 598729314 133794090 12808683 67477659 320740422 878134577 879383179 940923483 660160621 18082378 886078389 524050341 35092018 137623841 988429688 258507355 138475726 75726...

output:

319541931
71523627
374970852
25715597
36244629
300490421
920015579
97305810
949802809
507599156
733158280
569689405
234576135
266469534
141265915
989761030
221701009
895284489
707865101
547950933
844193939
688358883
642066256
113618699
877631874
804170817
455115375
47621629
66017800
747477619
281472...

result:

ok 29995 numbers

Test #4:

score: 20
Accepted
time: 496ms
memory: 40652kb

input:

100000 99989
703908936 826436271 431732352 607460686 960390248 897906950 506352459 662618885 172508812 713410533 704313866 156459539 879660919 98030681 46358006 400134234 121190289 498201666 616888945 210891377 39623412 687350951 269444705 980768130 381802923 553892268 644461704 287608268 554761733 ...

output:

135579851
646286631
74078131
432534100
405499800
291350098
736555983
833523488
132230969
377599489
208993791
503865639
149603681
279216057
477463117
247401241
643979698
478954375
436185030
471378650
234144621
390722547
788177217
69823556
516048238
562200936
507083023
201497639
482025143
173466674
95...

result:

ok 99989 numbers

Test #5:

score: 20
Accepted
time: 5331ms
memory: 345984kb

input:

1000000 999998
326289172 459965021 432610030 381274775 890620650 133203219 755508578 820410129 100497878 978894337 34545975 484258543 341383383 556328539 705716773 985485996 201697555 806763870 456757110 445252781 501965590 655584951 516373423 475444481 554722275 106826011 433893131 385018453 687541...

output:

606800783
817370938
237396973
847847757
644743839
247401674
83642110
430778992
481194348
734716471
284931123
740118779
149843259
354488296
948569346
267724213
148740992
487034502
874993826
268358083
945290837
793539526
571516423
380887985
556022428
430319434
939322
456132883
774969519
361006565
2390...

result:

ok 999998 numbers
English 繁體中文 简体中文

服务器时间: 2025-02-02 00:55:03 | 开源项目