結果
| 問題 |
No.1145 Sums of Powers
|
| ユーザー |
 37zigen
|
| 提出日時 | 2020-08-01 16:23:38 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 804 ms / 2,000 ms |
| コード長 | 10,426 bytes |
| コンパイル時間 | 2,340 ms |
| コンパイル使用メモリ | 132,072 KB |
| 最終ジャッジ日時 | 2025-01-12 12:42:15 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 6 |
ソースコード
#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];
if (i!=m) {
std::cout<<" ";
} else {
std::cout<<"\n";
}
}
}