結果

問題 No.754 畳み込みの和
ユーザー 37zigen37zigen
提出日時 2020-05-14 00:22:30
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 9,551 bytes
コンパイル時間 1,722 ms
コンパイル使用メモリ 122,456 KB
実行使用メモリ 14,132 KB
最終ジャッジ日時 2023-10-12 17:12:10
合計ジャッジ時間 3,969 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <string>
#include <iostream>
#include <vector>
#include <cassert>
#include <random>
#include <algorithm>
#include <deque>
#include <cstring>
#include <time.h>
#include <cstdio>

template<typename T=int>inline T get(){
  char c=getchar(); bool neg=(c=='-');
  T res=neg?0:c-'0'; while(isdigit(c=getchar()))res=res*10+(c-'0');
  return neg?-res:res;
}

template<typename T=int>inline void put(T x,char c='\n'){
  if(x==0)putchar('0');
  else{
    if(x<0) std::putchar('-'),x*=-1;
    int d[20],i=0;
    while(x)d[i++]=x%10,x/=10;
    while(i--) std::putchar('0'+d[i]);
  } putchar(c);
}

constexpr long long p[3]={998244353,924844033,897581057};
constexpr long long g[3]={3,5,3};

inline long long ADD(long long a,long long b,int id) {
  return a+b>=p[id]?a+b-p[id]:a+b;
}

inline int SUB(int a,int b,int id) {
  return a-b<0?a-b+p[id]:a-b;
}

int deg(std::vector<int> a){
  int ret=a.size()-1;
  while (ret>=0 && a[ret]==0) --ret;
  return ret;
}

std::vector<int> trim(std::vector<int> a,int n) {
  int asize=a.size();
  a.resize(n);
  for (int i=asize;i<n;++i) a[i]=0;
  return a;
}

std::vector<int> norm(std::vector<int> a) {
  while (a.size()>1 && a.back()==0) a.pop_back();
  return a;
}

//f->fx^(shift)
std::vector<int> shift(std::vector<int> &a,int shift) {
  std::vector<int> b(std::max(0,(int)a.size()+shift),0);
  for (int i=0;i<(int)b.size();++i) b[i]=(0<=i-shift&&i-shift<(int)a.size())?a[i-shift]:0;
  return b;
}

inline long long pow_mod(long long a,long long n,int id) {
  long long ret=1;
  for (;n>0;n>>=1,a=a*a%p[id]) if(n%2==1) ret=ret*a%p[id];
  return ret;
}

inline int inv(int a,int id) {
  a%=p[id];
  if (a<0) a+=p[id];
  int u=p[id];
  int v=a;
  int s=0;
  int t=1;
  // sa=u
  // ta=v
  while (v!=0) {
    int q=u/v;
    s-=q*t;u-=q*v;
    std::swap(s,t);
    std::swap(u,v);
  }
  assert((long long)a*(s+p[id])%p[id]==1);
  return s>=0?s:s+p[id];
}

std::vector<int> monic(std::vector<int> a,int id) {
  if (deg(a)==-1) return a;
  a.resize(deg(a)+1);
  long long coe=inv(a[a.size()-1],id);
  for (int i=0;i<(int)a.size();++i) {
    a[i]=(int)(coe*a[i]%p[id]);
  }
  return a;
}

std::vector<int> add(std::vector<int> a,std::vector<int> b,int id) {
  int n=std::max(a.size(),b.size());
  a.resize(n);b.resize(n);
  for (int i=0;i<n;++i) a[i]=ADD(a[i],b[i],id);
  return a;
}

std::vector<int> subtract(std::vector<int> a,std::vector<int> b,int id) {
  int n=std::max(a.size(),b.size());
  a.resize(n);b.resize(n);
  for (int i=0;i<n;++i) a[i]=ADD(a[i],p[id]-b[i],id);
  return a;
}

std::vector<int> mul_naive(std::vector<int> a,std::vector<int> b,int id) {
  std::vector<int> ret(a.size()+b.size()-1,0);
  for (int i=0;i<(int)a.size();++i) {
    for (int j=0;j<(int)b.size();++j) {
      ret[i+j]=(int)((ret[i+j]+1LL*a[i]*b[j])%p[id]);
    }
  }
  ret=norm(ret);
  return ret;
}

void fft_(int n,int g,int stride,std::vector<int> &from,std::vector<int> &to,bool flag,int id){
  if (n==1) {
    if (flag) for (int i=0;i<stride;++i) to[i]=from[i];
    return;
  } else {
    int w=pow_mod(g,(p[id]-1)/n,id);
    int mul=1;
    for (int i=0;i<n/2;++i) {
      for (int src=0;src<stride;++src) {
        const int A=from[src+stride*(i+  0)];
        const int B=from[src+stride*(i+n/2)];
        to[src+stride*(2*i+0)]=ADD(A,B,id);
        to[src+stride*(2*i+1)]=1LL*ADD(A,p[id]-B,id)*mul%p[id];
      }
      mul=1LL*mul*w%p[id];
    }
    fft_(n/2,g,2*stride,to,from,!flag,id);
  }
}

void fft4_(int n,int g,int j,int stride,std::vector<int> &from,std::vector<int> &to,bool flag,int id){
  int w=pow_mod(g,(p[id]-1)/n,id);
  long long w1,w2,w3;
  int i,src,n0,n1,n2,n3,A,B,C,D,apc,amc,bpd,jbmd;
  
  while (n>2) {
    n0=0;
    n1=n/4;
    n2=n1+n1;
    n3=n1+n2;
    w1=1;
    for (i=0;i<n1;++i) {
      w2=w1*w1%p[id];
      w3=w1*w2%p[id];
      for (src=0;src<stride;++src) {
        A=from[src+stride*(i+n0)];
        B=from[src+stride*(i+n1)];
        C=from[src+stride*(i+n2)];
        D=from[src+stride*(i+n3)];
        apc=ADD(A,C,id);
        amc=SUB(A,C,id);
        bpd=ADD(B,D,id);
        jbmd=1LL*j*SUB(B,D,id)%p[id];
        to[src+stride*(4*i+0)]=ADD(apc,bpd,id);
        to[src+stride*(4*i+1)]=w1*(amc+p[id]-jbmd)%p[id];
        to[src+stride*(4*i+2)]=w2*(A+C+p[id]-bpd)%p[id];
        to[src+stride*(4*i+3)]=w3*(A+p[id]-C+jbmd)%p[id];
      }
      w1=1LL*w1*w%p[id];
    }
    n/=4;
    stride*=4;
    flag=!flag;
    w=1LL*w*w%p[id];
    w=1LL*w*w%p[id];
    std::swap(to,from);
  }
  if (n<=2) fft_(n,g,stride,from,to,flag,id);
  if (from.size()>to.size()) std::swap(from,to);
}



std::vector<int> tmp_fft(1<<20);
void fft(std::vector<int> &a,int g,int id) {
  fft4_(a.size(),g,pow_mod(g,(p[id]-1)/4*3,id),1,a,tmp_fft,false,id);

}

//  (sx^p+u)(tx^p+v)
// =stx^(2p)+(sv+ut)x^p+uv
// =stx^(2p)+((s+u)(t+v)-(st-uv))x^p+uv
void mul_karatsuba(int a[],int b[],int c[],int res[],int n,int id) {
  if (n<=8) {
    for (int i=0;i<2*n;++i) res[i]=0;
    for (int i=0;i<n;++i) for(int j=0;j<n;++j) res[i+j]=ADD(res[i+j],(int)(1LL*a[i]*b[j]%p[id]),id);
    return;
  }
  int *x0=res;
  int *x1=res+n;
  int *x2=res+n*2;
  int *a0=a;
  int *a1=a+n/2;
  int *b0=b;
  int *b1=b+n/2;
  int *c0=c;
  int *c1=c+n/2;
  mul_karatsuba(a0,b0,c+n*2,x0,n/2,id);
  mul_karatsuba(a1,b1,c+n*2,x1,n/2,id);
  for (int i=0;i<n/2;++i) {
    c0[i]=ADD(a0[i],a1[i],id);
    c1[i]=ADD(b0[i],b1[i],id);
  }
  mul_karatsuba(c0,c1,c+n*2,x2,n/2,id);
  for (int i=0;i<n;++i) {
    x2[i]=ADD(ADD(x2[i],p[id]-x0[i],id),p[id]-x1[i],id);
  }
  for (int i=0;i<n;++i) {
    res[i+n/2]=ADD(res[i+n/2],x2[i],id);
  }
}

std::vector<int> mul_fft(std::vector<int> a,std::vector<int> b,int id) {
  int n=1;
  int need=a.size()+b.size()-1;
  while (n<need) n*=2;
  a.resize(n);
  b.resize(n);
  fft(a,g[id],id);
  fft(b,g[id],id);
  int inv_n=inv(n,id);
  for (int i=0;i<n;++i) a[i]=(int)(1LL*a[i]*b[i]%p[id]*inv_n%p[id]);
  fft(a,inv(g[id],id),id);
  a.resize(need);
  return a;
}

std::vector<int> karatsuba(std::vector<int> a,std::vector<int> b,int id) {
  int need=std::max(a.size(),b.size());
  int n=1;
  while (n<need) n*=2;
  std::vector<int> a_=trim(a,n);
  std::vector<int> b_=trim(b,n);
  std::vector<int> c(4*n);
  std::vector<int> res(4*n);
  mul_karatsuba(a_.data(),b_.data(),c.data(),res.data(),n,id);
  res.resize(a.size()+b.size()-1);
  return res;
}

std::vector<int> mul(std::vector<int> a,std::vector<int> b,int id) {
  if (std::max(a.size(),b.size())<=64) {
    return karatsuba(a,b,id);
  } else {
    std::vector<int> ret=mul_fft(a,b,id);
    ret=norm(ret);
    return ret;
  } 
}

std::vector<int> mul(std::vector<int> a,std::vector<int> b,long long mod) {
  int n=3;
  std::vector<int> f[n];
  for (int i=0;i<n;++i) {
    f[i]=mul(a,b,i);
  }
  for (int i=0;i<(int)f[0].size();++i) {
    long long coe[n];
    for (int j=0;j<n;++j) {
      long long cur=0;
      long long prd=1;
      for (int k=0;k<j;++k) {
        cur=(cur+coe[k]*prd)%p[j];
        prd=prd*p[k]%p[j];
      }
      coe[j]=inv(prd,j)*(f[j][i]-cur)%p[j];
    }
    long long prd=1;
    long long v=0;
    for (int j=0;j<n;++j) {
      v=(v+coe[j]*prd)%mod;
      prd=prd*p[j]%mod;
    }
    f[0][i]=(v+mod)%mod;
  }
  return f[0];
}

std::vector<int> mul(std::vector<int> a,int b,int id) {
  int n=a.size();
  std::vector<int> c(n);
  for (int i=0;i<n;++i) c[i]=(int)(1LL*a[i]*(p[id]+b)%p[id]);
  return c;
}

std::vector<std::vector<std::vector<int>>> mul(std::vector<std::vector<std::vector<int>>> a,std::vector<std::vector<std::vector<int>>> b,int id) {
  std::vector<std::vector<std::vector<int>>> ret(a.size(),std::vector<std::vector<int>>(b[0].size(),std::vector<int>()));
  for (int i=0;i<(int)a.size();++i) {
    for (int j=0;j<(int)b[i].size();++j) {
      for (int k=0;k<(int)a[i].size();++k) {
        ret[i][j]=add(ret[i][j],mul(a[i][k],b[k][j],id),id);
      }
    }
  }
  return ret;
}

// f  <- -f(fh-1)+f
std::vector<int> inv(std::vector<int> h,int id) {
  int n=h.size();
  std::vector<int> f={inv(h[0],id)};
  long long root=g[id];
  long long iroot=inv(g[id],id);
  for (int len=1;len<n;len*=2) {
    std::vector<int> f_fft=trim(f,2*len);
    std::vector<int> h_fft=trim(h,2*len);
    fft(f_fft,root,id);
    fft(h_fft,root,id);
    long long isize=inv(2*len,id);
    for (int i=0;i<2*len;++i) h_fft[i]=(int)(1LL*h_fft[i]*f_fft[i]%p[id]*isize%p[id]);
    fft(h_fft,iroot,id);
    for (int i=0;i<len;++i) h_fft[i]=0;
    
    fft(h_fft,root,id);
    for (int i=0;i<2*len;++i) h_fft[i]=(int)(1LL*h_fft[i]*f_fft[i]%p[id]*isize%p[id]);
    fft(h_fft,iroot,id);
    for (int i=0;i<len;++i) h_fft[i]=0;
    f.resize(std::min(n,2*len));
    for (int i=0;i<2*len;++i) {
      f[i]=ADD(f[i],p[id]-h_fft[i],id);
    }
  }
  return f;
}

std::vector<int> divide(std::vector<int> a,std::vector<int> b,int id) {
  a=norm(a);
  b=norm(b);
  if (a.size()<b.size()) {
    std::vector<int> ret(1,0);
    return ret;
  }
  std::reverse(a.begin(),a.end());
  std::reverse(b.begin(),b.end());
  int n=a.size()-b.size()+1;
  a.resize(n);
  b.resize(n);
  a=mul(a,inv(b,id),id);
  a.resize(n);
  std::reverse(a.begin(),a.end());
  return a;
}

std::vector<int> mod(std::vector<int> a,std::vector<int> b,int id) {
  return subtract(a,mul(b,divide(a,b,id),id),id);
}

int main() {
  long long mod=(long long)1e9+7;
  int n=get()+1;
  int m=n;
  //int m=get();
  std::vector<int> a(n);
  std::vector<int> b(m);
  for (int i=0;i<n;++i) a[i]=get();
  for (int i=0;i<m;++i) b[i]=get();
  a=mul(a,b,mod);
  long long sum=0;
  for (int i=0;i<n;++i) sum=(sum+a[i])%mod;
  std::cout<<sum<<std::endl;
  //for (int i=0;i<n+m-1;++i) {
    //put(a[i]);
  //}
}
0