結果
問題 | No.754 畳み込みの和 |
ユーザー |
![]() |
提出日時 | 2024-05-05 22:48:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 310 ms / 5,000 ms |
コード長 | 13,355 bytes |
コンパイル時間 | 3,065 ms |
コンパイル使用メモリ | 232,968 KB |
最終ジャッジ日時 | 2025-02-21 11:06:18 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 3 |
ソースコード
#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;}