#523178 (C++17) No.1145 Sums of Powers

提出ソース
結果

問題	No.1145 Sums of Powers
ユーザー	37zigen
提出日時	2020-08-01 16:21:43
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	10,337 bytes
コンパイル時間	2,110 ms
コンパイル使用メモリ	136,248 KB
実行使用メモリ	28,568 KB
最終ジャッジ日時	2024-07-08 02:48:48
合計ジャッジ時間	5,047 ms
ジャッジサーバーID （参考情報）	judge4 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

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

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

constexpr long long     p=998244353;
constexpr long long  root=3;
constexpr long long iroot=332748118;
inline int ADD(const int a,const int b) {
  return a+b>=p?a+b-p:a+b;
}

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

void fail() {
  printf("-1\n");
  exit(0);
}

int deg(const 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,const int n) {
  int asize=a.size();
  a.resize(n);
  for (int i=asize;i<n;++i) a[i]=0;
  return a;
}

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

//f->fx^(shift)
std::vector<int> shift(std::vector<int> &a,const 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) {
  long long ret=1;
  for (;n>0;n>>=1,a=a*a%p) if(n%2==1) ret=ret*a%p;
  return ret;
}

inline int inv(int a) {
  a%=p;
  if (a<0) a+=p;
  int u=p;
  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);
  }
  return s>=0?s:s+p;
}

void monic(std::vector<int> &a) {
  norm(a);
  long long coe=inv(a.back());
  for (int i=0;i<(int)a.size();++i) {
    a[i]=(int)(coe*a[i]%p);
  }
}

std::vector<int> add(std::vector<int> a,std::vector<int> b) {
  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]);
  return a;
}

std::vector<int> subtract(std::vector<int> a,std::vector<int> b) {
  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-b[i]);
  return a;
}

std::vector<int> mul_naive(std::vector<int> &a,std::vector<int> &b) {
  std::vector<int> ret(a.size()+b.size()-1,0);
  if (a.size()<b.size()) {
    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);
      }
    }
  }else {
    for (int j=0;j<(int)b.size();++j) {
      for (int i=0;i<(int)a.size();++i) {
        ret[i+j]=(int)((ret[i+j]+1LL*a[i]*b[j])%p);
      }
    }
  }
  norm(ret);
  return ret;
}

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

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

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

//  (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) {
  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));
    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);
  mul_karatsuba(a1,b1,c+n*2,x1,n/2);
  for (int i=0;i<n/2;++i) {
    c0[i]=ADD(a0[i],a1[i]);
    c1[i]=ADD(b0[i],b1[i]);
  }
  mul_karatsuba(c0,c1,c+n*2,x2,n/2);
  for (int i=0;i<n;++i) {
    x2[i]=SUB(SUB(x2[i],x0[i]),x1[i]);
  }
  for (int i=0;i<n;++i) {
    res[i+n/2]=ADD(res[i+n/2],x2[i]);
  }
}

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

std::vector<int> karatsuba(std::vector<int> &a,std::vector<int> &b) {
  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);
  res.resize(a.size()+b.size()-1);
  return res;
}

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

std::vector<int> mul(std::vector<int> &a,int b) {
  int n=a.size();
  std::vector<int> c(n);
  for (int i=0;i<n;++i) c[i]=(int)(1LL*a[i]*(p+b)%p);
  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) {
  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) {
        std::vector<int> prd=mul(a[i][k],b[k][j]);
        if (ret[i][j].size()<prd.size()) ret[i][j].resize(prd.size());
        for (int l=0;l<(int)prd.size();++l) {
          ret[i][j][l]=ADD(ret[i][j][l],prd[l]);
        }
      }
    }
  }
  return ret;
}

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

std::vector<int> divide_naive(std::vector<int> a,std::vector<int> &b) {
  if (a.size()<b.size()) return {0};
  int n=a.size()-b.size()+1;
  std::vector<int> ret(n,0);
  norm(b);
  assert(deg(b)>=0);
  int ib=inv(b.back());
  for (int i=n-1;i>=0;--i) {
    if (a[i+b.size()-1]==0) continue;
    ret[i]=1LL*ib*a[i+b.size()-1]%p;
    for (int j=0;j<(int)b.size();++j) {
      a[i+j]=(a[i+j]+1LL*b[j]*(p-ret[i]))%p;
    }
  }
  return ret;
}

std::vector<int> divide_newton(std::vector<int> a,std::vector<int> b) {  
  if (a.size()<b.size()) return {0};
  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);
  b=inv(b);
  a=mul(a,b);
  a.resize(n);
  std::reverse(a.begin(),a.end());
  return a;
}

std::vector<int> divide(std::vector<int> &a,std::vector<int> &b) {
  norm(a);
  norm(b);
  if (a.size()<b.size()) {
    std::vector<int> ret(1,0);
    return ret;
  }
  
  if (a.size()==b.size()) {
    return {(int)(1LL*inv(b.back())*a.back()%p)};
  } else if (a.size()-b.size()<b.size()-1 && a.size()>=32) {
    int del=a.size()-2*(a.size()-b.size())-1;
    std::vector<int> na=shift(a,-del);
    std::vector<int> nb=shift(b,-del);
    return divide(na,nb);
  } else if (a.size()<32) {
    return divide_naive(a,b);
  } else {
    return divide_newton(a,b);
  }
}

std::vector<int> mod(std::vector<int> &a,std::vector<int> &b) {
  std::vector<int> q=divide(a,b);
  q=subtract(a,mul(b,q));
  norm(q);
  return q;
}

int main() {
    int n,m;
    std::cin>>n>>m;
    std::vector<int> a(n);
    for (int i=0;i<n;++i) std::cin>>a[i];
    std::deque<std::vector<int>> den;
    std::deque<std::vector<std::vector<int>>> num;
    for (int i=0;i<n;++i) {
        std::vector<int> f{1,(int)(p-a[i])};
        den.push_back(f);
    }
    for (int i=0;i<n;++i) {
        std::vector<int> f{1,(int)(p-a[i])};
        std::vector<int> g{1};
        std::vector<std::vector<int>> h{f,g};
        num.push_back(h);
    }

    while (den.size()>1) {
        std::vector<int> f=den.front();den.pop_front();        
        std::vector<int> g=den.front();den.pop_front();
        den.push_back(mul(f,g));
    }

    while (num.size()>1) {
        std::vector<std::vector<int>> f=num.front();num.pop_front();        
        std::vector<std::vector<int>> g=num.front();num.pop_front();
        std::vector<int> a=mul(f[0],g[0]);
        std::vector<int> b=add(mul(f[0],g[1]),mul(f[1],g[0]));
        std::vector<std::vector<int>> ret{a,b};
        num.push_back(ret);
    }
    std::vector<int> denominator=den.front();
    denominator.resize(m+1);
    denominator=inv(denominator);
    std::vector<int> ans=mul(num.front()[1],denominator);
    for (int i=1;i<=m;++i) {
        std::cout<<ans[i]<<std::endl;
    }
}
yukicoder

結果

テストケース

ソースコード
