結果

問題 No.3414 Aperiodic Sequence
コンテスト
ユーザー tau1235
提出日時 2025-12-21 18:02:12
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 1,754 ms / 3,000 ms
コード長 6,424 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,525 ms
コンパイル使用メモリ 310,672 KB
実行使用メモリ 23,592 KB
最終ジャッジ日時 2025-12-21 18:02:32
合計ジャッジ時間 18,151 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
#include<atcoder/modint>
using mint=atcoder::modint998244353;
struct FPS:vector<mint>{
  using vector<mint>::vector;
  static constexpr ll mod=998244353;
  static FPS NTT(FPS &a,bool inverse=false){
    const mint pr=3;
    int n=a.size();
    int log=0;
    while (n>1<<log) log++;
    FPS ret(n);
    for (int i=0;i<n;i++){
      int rev=0;
      for (int k=0;k<log;k++) rev|=((i>>k)&1)<<(log-k-1);
      ret[rev]=a[i];
    }
    for (int k=1;k<=log;k++){
      int len=1<<k;
      mint zeta=pr.pow((mod-1)>>k);
      if (inverse) zeta=zeta.inv();
      mint x=1;
      for (int i=0;i<len/2;i++){
        for (int j=i;j<n;j+=len){
          mint r1=ret[j],r2=x*ret[j+len/2];
          ret[j]=r1+r2;
          ret[j+len/2]=r1-r2;
        }
        x*=zeta;
      }
    }
    if (inverse){
      mint ninv=mint(n).inv();
      for (int i=0;i<n;i++) ret[i]*=ninv;
    }
    return ret;
  }
  static FPS convolution(FPS a,FPS b){
    int na=a.size(),nb=b.size();
    int nc=na+nb-1;
    int n=1;
    while (n<nc) n<<=1;
    while ((int)a.size()<n) a.push_back(0);
    while ((int)b.size()<n) b.push_back(0);
    a=NTT(a);b=NTT(b);
    for (int i=0;i<n;i++) a[i]*=b[i];
    a=NTT(a,true);
    a.resize(nc);
    return a;
  }
  void shrink(){while((*this).size()&&(*this).back()==0)(*this).pop_back();}
  FPS rev()const{
    FPS ret(*this);
    reverse(ret.begin(),ret.end());
    return ret;
  }
  FPS pre(int sz)const{
    FPS ret(min((int)(*this).size(),sz));
    for (int i=0;i<min((int)(*this).size(),sz);i++) ret[i]=(*this)[i];
    if ((int)ret.size()<sz) ret.resize(sz);
    return ret;
  }

  FPS operator+=(const FPS &r){
    if ((*this).empty()) (*this).resize(1);
    for (int i=0;i<(int)r.size();i++) (*this)[i]+=r[i];
    return *this;
  }
  FPS operator+=(const mint &r){
    if ((*this).empty()) (*this).resize(1);
    (*this)[0]+=r;
    return *this;
  }
  FPS operator-=(const FPS &r){
    if ((*this).empty()) (*this).resize(1);
    for (int i=0;i<(int)r.size();i++) (*this)[i]-=r[i];
    return *this;
  }
  FPS operator-=(const mint &r){
    if ((*this).empty()) (*this).resize(1);
    (*this)[0]-=r;
    return *this;
  }
  FPS operator*=(const FPS &r){
    if ((*this).empty()||r.empty()){
      (*this).clear();
      return *this;
    }
    return *this=convolution(*this,r);
  }
  FPS operator*=(const mint &r){
    for (int i=0;i<(int)(*this).size();i++) (*this)[i]*=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=((*this).rev().pre(n)*r.rev().inv(n)).pre(n).rev();
  }
  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 mint &r)const{return FPS(*this)+=r;}
  FPS operator-(const FPS &r)const{return FPS(*this)-=r;}
  FPS operator-(const mint &r)const{return FPS(*this)-=r;}
  FPS operator*(const FPS &r)const{return FPS(*this)*=r;}
  FPS operator*(const mint &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 inv(int deg=-1)const{
    assert((*this)[0]!=mint(0));
    if (deg==-1) deg=(*this).size();
    FPS ret(deg);
    ret[0]=(*this)[0].inv();
    for (int d=1;d<deg;d<<=1){
      FPS f(2*d),g(2*d);
      for (int i=0;i<min((int)(*this).size(),2*d);i++) f[i]=(*this)[i];
      for (int i=0;i<d;i++) g[i]=ret[i];
      f=NTT(f);g=NTT(g);
      for (int i=0;i<2*d;i++) f[i]*=g[i];
      f=NTT(f,true);
      for (int i=0;i<d;i++) f[i]=0;
      f=NTT(f);
      for (int i=0;i<2*d;i++) f[i]*=g[i];
      f=NTT(f,true);
      for (int i=d;i<min(2*d,deg);i++) ret[i]=-f[i];
    }
    return ret.pre(deg);
  }
  FPS diff()const{
    int n=(*this).size();
    FPS ret(max(0,n-1));
    for (int i=1;i<n;i++) ret[i-1]=(*this)[i]*i;
    return ret;
  }
  FPS integral()const{
    int n=(*this).size();
    FPS ret(n+1);
    ret[0]=0;
    for (int i=1;i<=n;i++) ret[i]=(*this)[i-1]/i;
    return ret;
  }
  FPS log(int deg=-1)const{
    assert((*this)[0]==1);
    if (deg==-1) deg=(*this).size();
    return ((*this).diff()*(*this).inv(deg)).pre(deg-1).integral();
  }
  FPS exp(int deg=-1)const{
    assert((*this)[0]==0);
    int n=(*this).size();
    if (deg==-1) deg=n;
    FPS ret(1);
    ret[0]=1;
    for (int d=1;d<deg;d<<=1) ret=(ret*(pre(d*2)-ret.log(d*2)+1)).pre(d*2);
    return ret.pre(deg);
  }
  FPS pow(ll k,int deg=-1)const{
    int n=(*this).size();
    if (deg==-1) deg=n;
    FPS ret(n);
    ll shift=-1;
    mint a=1,ainv=1;
    for (int i=0;i<n;i++){
      if ((*this)[i].val()){
        shift=i;
        a=(*this)[i];
        ainv=a.inv();
        break;
      }
    }
    if (shift==-1){
      if (k==0) ret[0]=1;
      return ret.pre(deg);
    }
    if (__int128_t(shift)*k>=deg) return FPS(deg);
    for (int i=shift;i<n;i++) ret[i-shift]=(*this)[i]*ainv;
    ret=(ret.log()*k).exp();
    a=a.pow(k);
    shift*=k;
    for (int i=n-1;i>=shift;i--) ret[i]=ret[i-shift]*a;
    for (int i=0;i<shift;i++) ret[i]=0;
    return ret.pre(deg);
  }

};
using fps=FPS;

int main(){
  int n,m;
  cin>>n>>m;
  vector<int> v(n);
  for (int i=0;i<n;i++) cin>>v[i];
  auto func=[&](vector<int> a){
    int n=a.size();
    queue<pair<fps,fps>> q;
    for (int i=0;i<n;i++) q.push({{1},{1,-a[i]}});
    while (q.size()>1){
      auto f=q.front();q.pop();
      auto g=q.front();q.pop();
      fps h1=f.first*g.second+f.second*g.first,h2=f.second*g.second;
      q.push({h1,h2});
    }
    auto [f,g]=q.front();
    return (f*g.inv(m+1)).pre(m+1);
  };
  auto g=func(v);
  vector<fps> f(m+1);
  for (int i=1;i<=m;i++){
    f[i]=fps(m/i+1);
    mint s=g[i];
    for (int j=1;j<=m/i;j++){
      f[i][j]=s;
      s*=g[i];
    }
  }
  vector<vector<int>> d(m+1);
  for (int i=2;i<=m;i++) for (int j=i;j<=m;j+=i) d[j].push_back(i);
  vector<int> len(m+1,0);
  auto rec=[&](auto rec,int x,ll pw)-> void {
    assert(pw<=m);
    if (len[pw]>=x) return;
    if (x==1){
      len[pw]=1;
      return;
    }
    for (int i=2;pw*i<=m;i++) rec(rec,x/i,pw*i);
    for (int i=len[pw]+1;i<=x;i++){
      for (int j:d[i]){
        f[pw][i]-=f[pw*j][i/j];
      }
    }
    len[pw]=x;
    return;
  };
  rec(rec,m,1);
  for (int i=1;i<=m;i++) cout<<f[1][i].val()<<" \n"[i==m];
}
0