#979156 (C++17) No.754 畳み込みの和

提出ソース
結果

問題	No.754 畳み込みの和
ユーザー	nonon
提出日時	2024-05-05 22:48:27
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	302 ms / 5,000 ms
コード長	13,355 bytes
コンパイル時間	3,431 ms
コンパイル使用メモリ	240,436 KB
実行使用メモリ	23,224 KB
最終ジャッジ日時	2024-11-28 00:06:58
合計ジャッジ時間	5,029 ms
ジャッジサーバーID （参考情報）	judge1 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	302 ms 23,224 KB
testcase_01	AC	285 ms 23,224 KB
testcase_02	AC	283 ms 23,224 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include<bits/stdc++.h>
using namespace std;
template<long long mod_>
struct modint
{
    modint():value(0){}
    modint(long long v)
    {
        long long x=(long long)(v%m());
        if(x<0)x+=m();
        value=x;
    }
    static constexpr long long mod()noexcept{return m();}
    long long val()const{return value;}
    modint& operator++()
    {
        value++;
        if(value==m())value=0;
        return *this;
    }
    modint& operator--()
    {
        if(value==0)value=m();
        value--;
        return *this;
    }
    modint operator++(int)
    {
        modint res=*this;
        ++*this;
        return res;
    }
    modint operator--(int)
    {
        modint res=*this;
        --*this;
        return res;
    }
    modint& operator+=(const modint& a)
    {
        value+=a.value;
        if(value>=m())value-=m();
        return *this;
    }
    modint& operator-=(const modint& a)
    {
        value-=a.value;
        if(value<0)value+=m();
        return *this;
    }
    modint& operator*=(const modint& a)
    {
        unsigned long long x=value;
        x*=a.value;
        x%=m();
        if(x<0)x+=m();
        value=x;
        return *this;
    }
    modint& operator/=(const modint& a)
    {
        return *this=(*this)*a.inv();
    }
    modint operator+()const{return *this;}
    modint operator-()const{return modint()-*this;}
    modint pow(long long n)const
    {
        modint x=*this,res=1;
        while(n)
        {
            if(n&1)res*=x;
            x*=x;
            n>>=1;
        }
        return res;
    }
    modint inv()const
    {
        long long a=value,b=m(),u=1,v=0;
        while(b)
        {
            long long t=a/b;
            a-=t*b;
            swap(a,b);
            u-=t*v;
            swap(u,v);
        }
        return modint(u);
    }
    friend modint operator+(const modint& a, const modint& b)
    {
        modint res=a;
        res+=b;
        return res;
    }
    friend modint operator-(const modint& a, const modint& b)
    {
        modint res=a;
        res-=b;
        return res;
    }
    friend modint operator*(const modint& a, const modint& b)
    {
        modint res=a;
        res*=b;
        return res;
    }
    friend modint operator/(const modint& a, const modint& b)
    {
        modint res=a;
        res/=b;
        return res;
    }
    friend bool operator==(const modint& a, const modint& b)
    {
        return a.value==b.value;
    }
    friend bool operator!=(const modint& a, const modint& b)
    {
        return a.value!=b.value;
    }
private:
    long long value;
    static constexpr long long m(){return mod_;}
};
template<typename mint>
struct Arbitrary_mod_Formal_Power_Series:vector<mint>
{
    using FPS=Arbitrary_mod_Formal_Power_Series;
    using vector<mint>::vector;
    using vector<mint>::operator=;
    FPS &operator+=(const mint&r)
    {
        if(this->empty())this->resize(1);
        (*this)[0]+=r;
        return *this;
    }
    FPS &operator-=(const mint&r)
    {
        if(this->empty())this->resize(1);
        (*this)[0]-=r;
        return *this;
    }
    FPS &operator*=(const mint&r)
    {
        for(mint &x:*this)x*=r;
        return *this;
    }
    FPS &operator/=(const mint&r)
    {
        mint r_=r.inv();
        for(mint &x:*this)x*=r_;
        return *this;
    }
    FPS operator+(const mint&r)const{return FPS(*this)+=r;}
    FPS operator-(const mint&r)const{return FPS(*this)-=r;}
    FPS operator*(const mint&r)const{return FPS(*this)*=r;}
    FPS operator/(const mint&r)const{return FPS(*this)/=r;}

    FPS operator+=(const FPS&r)
    {
        if(this->size()<r.size())this->resize(r.size());
        for(int i=0;i<(int)r.size();i++)(*this)[i]+=r[i];
        return *this;
    }
    FPS operator-=(const FPS&r)
    {
        if(this->size()<r.size())this->resize(r.size());
        for(int i=0;i<(int)r.size();i++)(*this)[i]-=r[i];
        return *this;
    }
    FPS operator*=(const FPS&r)
    {
        *this=arbitrary_mod_convolution(*this,r);
        return *this;
    }
    FPS operator/=(const FPS&r)
    {
        if(this->size()<r.size())
        {
            this->clear();
            return *this;
        }
        int n=this->size()-r.size()+1;
        return *this=(rev().pre(n)*r.rev().inv(n)).pre(n).rev(n);
    }
    FPS operator%=(const FPS&r)
    {
        *this-=*this/r*r;
        shrink();
        return *this;
    }
    FPS operator+(const FPS&r)const{return FPS(*this)+=r;}
    FPS operator-(const FPS&r)const{return FPS(*this)-=r;}
    FPS operator*(const FPS&r)const{return FPS(*this)*=r;}
    FPS operator/(const FPS&r)const{return FPS(*this)/=r;}
    FPS operator%(const FPS&r)const{return FPS(*this)%=r;}

    FPS pre(int n)const
    {
        return FPS(this->begin(),this->begin()+min((int)this->size(),n));
    }
    FPS rev(int n=-1)const
    {
        FPS res=*this;
        if(n!=-1)res.resize(n,0);
        return FPS(res.rbegin(),res.rend());
    }
    void shrink()
    {
        while(!this->empty()&&this->back()==0)this->pop_back();
    }
    
    FPS operator<<(int n)const
    {
        FPS res=*this;
        res.insert(res.begin(),n,0);
        return res;
    }
    FPS operator>>(int n)const
    {
        if((int)this->size()<=n)return{};
        FPS res=*this;
        res.erase(res.begin(),res.begin()+n);
        return res;
    }

    mint operator()(const mint&r)
    {
        mint r_=0,powr=1;
        for(int i=0;i<this->size();i++)
        {
            for(auto x:*this)
            {
                r_+=x*powr;
                powr*=r;
            }
            return r_;
        }
    }

    FPS inv(int n=-1)const
    {
        assert(!this->empty());
        assert((*this)[0]!=0);
        if(n==-1)n=this->size();
        FPS res={(*this)[0].inv()};
        for(int i=1;i<n;i<<=1)
        {
            res=(res+res-res*res*(pre(i<<1))).pre(i<<1);
        }
        return res.pre(n);
    }
    FPS exp(int n=-1)const
    {
        assert((*this)[0]==0);
        if(n==-1)n=this->size();
        FPS res={1};
        for(int i=1;i<n;i<<=1)
        {
            res=(res*(pre(i<<1)+mint(1)-res.log(i<<1))).pre(i<<1);
        }
        return res.pre(n);
    }
    FPS log(int n=-1)const
    {
        assert((*this)[0]==1);
        if(n==-1)n=this->size();
        return FPS((diff()*inv(n)).pre(n-1)).integral();
    }
    FPS pow(long long k, int n=-1)const
    {
        if(n==-1)n=this->size();
        if(k==0)
        {
            FPS res(n);
            res[0]=1;
            return res;
        }
        FPS res=*this;
        int cnt0=0;
        while(cnt0<(int)res.size()&&res[cnt0]==0)cnt0++;
        if (cnt0>(n-1)/k)
        {
            FPS res(n);
            return res;
        }
        res=res>>cnt0;
        n-=cnt0*k;
        res=((res/res[0]).log(n)*k).exp(n)*res[0].pow(k);
        res=res<<(cnt0*k);
        return res;
    }
    FPS diff()const
    {
        int n=this->size();
        FPS res(max(0,n-1));
        for(int i=1;i<=(int)res.size();i++)
        {
            res[i-1]=(*this)[i]*i;
        }
        return res;
    }
    FPS integral()const
    {
        FPS res(this->size()+1);
        res[0]=0;
        for(int i=0;i<(int)res.size()-1;i++)
        {
            res[i+1]=(*this)[i]/(i+1);
        }
        return res;
    }
    vector<mint>multipoint_evaluation(vector<mint>&x)
    {
        if(x.empty())return{};
        int m=x.size(),n=1;
        if(this->size()==0){return vector<mint>(m,0);}
        if(this->size()==1){return vector<mint>(m,(*this)[0]);}
        while(m>n)n<<=1;
        vector<FPS>f(n<<1,FPS({mint(1)}));
        for(int i=0;i<m;i++)f[i+n]=FPS({-x[i],mint(1)});
        for(int i=n-1;i>0;i--)f[i]=f[i<<1]*f[(i<<1)|1];
        f[1]=(*this)%f[1];
        for(int i=2;i<n+m;i++)f[i]=f[i>>1]%f[i];
        vector<mint>res(m);
        for(int i=0;i<m;i++)res[i]=(f[i+n].empty()?mint(0):f[i+n][0]);
        return res;
    }
private:
    long long modpow(long long a, long long n, long long mod)
    {
        long long res=1;
        while(n)
        {
            if(n&1)res=(res*a)%mod;
            a=(a*a)%mod;
            n>>=1;
        }
        return res%mod;
    }
    int get_primitive_root(int mod)
    {
        if(mod==2)return 1;
        if(mod==167772161)return 3;
        if(mod==469762049)return 3;
        if(mod==754974721)return 11;
        if(mod==998244353)return 3;
        if(mod==1224736769)return 3;
        int divs[20]={};
        divs[0]=2;
        int cnt=1;
        long long x=(mod-1)/2;
        while(x%2==0)x/=2;
        for(long long i=3;i*i<=x;i+=2)
        {
            if(x%i==0)
            {
                divs[cnt++]=i;
                while(x%i==0)x/=i;
            }
        }
        if(x>1)divs[cnt++]=x;
        for(int g=2;;g++)
        {
            bool ok=1;
            for(int i=0;i<cnt;i++)
            {
                if(modpow(g,(mod-1)/divs[i],mod)==1)ok=0;
            }
            if(ok)return g;
        }
    }
    template<typename T>
    void bit_rev(vector<T>&a)
    {
        int n=a.size();
        for(int i=0,j=1;j<n-1;j++)
        {
            for(int k=n>>1;k>(i^=k);k>>=1);
            if(i<j)swap(a[i],a[j]);
        }
    }
    template<typename T>
    void NTT(vector<T>&f, bool ordered=false)
    {
        constexpr int mod=T::mod();
        T primitive_root=get_primitive_root(mod);
        int n=f.size();
        for(int m=n;m>1;m>>=1)
        {
            T omega=primitive_root.pow((mod-1)/m);
            for(int s=0;s<n/m;s++)
            {
                T w=1;
                for(int i=0;i<m/2;i++)
                {
                    T l=f[s*m+i];
                    T r=f[s*m+i+m/2];
                    f[s*m+i]=l+r;
                    f[s*m+i+m/2]=(l-r)*w;
                    w*=omega;
                }
            }
        }
        if(ordered)bit_rev(f);
    }
    template<typename T>
    void INTT(vector<T>&f, bool ordered=false)
    {
        constexpr int mod=T::mod();
        T primitive_root=get_primitive_root(mod);
        if(ordered)bit_rev(f);
        int n=f.size();
        for(int m=2;m<=n;m<<=1)
        {
            T omega=primitive_root.pow((mod-1)/m).inv();
            for(int s=0;s<n/m;s++)
            {
                T w=1;
                for(int i=0;i<m/2;i++)
                {
                    T l=f[s*m+i];
                    T r=f[s*m+i+m/2]*w;
                    f[s*m+i]=l+r;
                    f[s*m+i+m/2]=l-r;
                    w*=omega;
                }
            }
        }
    }
    template<typename T>
    vector<T>convolution(vector<T>f, vector<T>g)
    {
        int n=f.size(),m=g.size();
        if(n==0||m==0)return {};
        int pow2=1;
        while(pow2<n+m-1)pow2<<=1;
        f.resize(pow2);
        g.resize(pow2);
        NTT(f);
        NTT(g);
        for(int i=0;i<pow2;i++)f[i]*=g[i];
        INTT(f);
        f.resize(n+m-1);
        T pow2_inv=T(pow2).inv();
        for(int i=0;i<n+m-1;i++)f[i]*=pow2_inv;
        return f;
    }
    long long mod_inv(long long n, long long mod)
    {
        long long a=n,b=mod,u=1,v=0;
        while(b)
        {
            long long t=a/b;
            a-=t*b;
            swap(a,b);
            u-=t*v;
            swap(u,v);
        }
        return u;
    }
    long long garner(vector<long long> v, vector<long long> MOD, long long mod)
    {
        MOD.push_back(mod);
        int n=MOD.size();
        vector<long long>c1(n,1),c2(n,0);
        for(int i=0;i<n-1;i++)
        {
            long long t=(v[i]-c2[i])*mod_inv(c1[i],MOD[i])%MOD[i];
            if(t<0)t+=MOD[i];
            for(int j=i+1;j<n;j++)
            {
                c2[j]=(c2[j]+t*c1[j])%MOD[j];
                c1[j]=c1[j]*MOD[i]%MOD[j];
            }
        }
        return c2.back();
    }
    vector<mint>arbitrary_mod_convolution(const vector<mint> f_, const vector<mint> g_)
    {
        vector<long long>MOD={167772161,469762049,754974721};
        vector<long long>f,g;
        const long long mod=mint::mod();
        for(mint a:f_)f.push_back(a.val());
        for(mint a:g_)g.push_back(a.val());
        using mint0=modint<167772161>;
        using mint1=modint<469762049>;
        using mint2=modint<754974721>;
        vector<mint0>f0(f.begin(),f.end()),g0(g.begin(),g.end());
        vector<mint1>f1(f.begin(),f.end()),g1(g.begin(),g.end());
        vector<mint2>f2(f.begin(),f.end()),g2(g.begin(),g.end());
        vector<mint0>h0=convolution(f0,g0);
        vector<mint1>h1=convolution(f1,g1);
        vector<mint2>h2=convolution(f2,g2);
        int n=h0.size();
        vector<mint>res(n);
        for(int i=0;i<n;i++)
        {
            vector<long long>v(3);
            v[0]=h0[i].val();
            v[1]=h1[i].val();
            v[2]=h2[i].val();
            res[i]=(mint)garner(v,MOD,mod);
        }
        return res;
    }
};
const long long mod=1000000007;
using mint=modint<mod>;
using FPS=Arbitrary_mod_Formal_Power_Series<mint>;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin>>N;
    FPS f(N+1),g(N+1);
    for(int i=0;i<=N;i++)
    {
        int a;
        cin>>a;
        f[i]=a;
    }
    for(int i=0;i<=N;i++)
    {
        int a;
        cin>>a;
        g[i]=a;
    }
    FPS h=f*g;
    mint ans=0;
    for(int i=0;i<=N;i++)ans+=h[i];
    cout<<ans.val()<<endl;
}
yukicoder

結果

テストケース

ソースコード
