結果

問題 No.3414 Aperiodic Sequence
コンテスト
ユーザー wolgnik
提出日時 2025-12-18 14:16:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,997 ms / 3,000 ms
コード長 4,260 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 303 ms
コンパイル使用メモリ 82,908 KB
実行使用メモリ 203,712 KB
最終ジャッジ日時 2025-12-20 23:31:31
合計ジャッジ時間 17,019 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

"""
lint

"""

import sys

def validate_input(raw: str):
    # 入力末尾に余計な空行は無いか？
    # → 最後の改行の後に空行があるとダメ
    assert not raw.endswith('\n\n'), "末尾に余計な空行"
    
    # 改行で入力が終わっているか？
    assert raw.endswith('\n'), "改行で終わってない"
    
    # 行末に余計なスペースは無いか？
    lines = raw.rstrip('\n').split('\n')
    for i, line in enumerate(lines):
        assert line == line.rstrip(' '), f"{i+1}行目の末尾にスペースがある"
        
        # 行頭にスペースがないか？
        assert line == line.lstrip(' '), f"{i}行目：行頭にスペースがある"
        
        # 連続スペースがないか？
        assert '  ' not in line, f"{i}行目：連続スペースがある"

raw_input = sys.stdin.read()
validate_input(raw_input)
lines = raw_input.split('\n')
N, M = map(int, lines[0].split())
v = list(map(int, lines[1].split()))
mod = 998244353

class Convolution:
  __slots__ = ['W', 'iW']
  def __init__(self):
    g = 3
    ig = 332748118
    self.W = [pow(g, (mod - 1) >> i, mod) for i in range(24)]
    self.iW = [pow(ig, (mod - 1) >> i, mod) for i in range(24)]
  
  def fmt(self, k, a):
    W = self.W
    for l in range(k, 0, -1):
      d = 1 << (l - 1)
      w = W[l]
      for i in range(0, len(a), d * 2):
        u = 1
        for j in range(d):
          s = i + j
          a[s], a[s + d] = (a[s] + a[s + d]) % mod, u * (a[s] - a[s + d]) % mod
          u = u * w % mod
    return a
  
  def ifmt(self, k, a):
    iW = self.iW
    for l in range(1, k + 1):
      d = 1 << (l - 1)
      w = iW[l]
      for i in range(0, len(a), d * 2):
        u = 1
        for j in range(d):
          s = i + j
          a[s + d] *= u
          a[s], a[s + d] = (a[s] + a[s + d]) % mod, (a[s] - a[s + d]) % mod
          u = u * w % mod
    return a

  def Convolve(self, a, b):
    n0 = len(a) + len(b) - 1
    if n0 == 1:
      return [a[0] * b[0] % mod]
    
    if min(len(a), len(b)) <= 50:
      res = [0] * n0
      for i, ai in enumerate(a):
        for j, bj in enumerate(b):
          res[i + j] += ai * bj
      return [x % mod for x in res]
    
    k = n0.bit_length()
    n = 1 << k
    A = a + [0] * (n - len(a))
    B = b + [0] * (n - len(b))
    
    A = self.fmt(k, A)
    B = self.fmt(k, B)
    
    C = [A[i] * B[i] % mod for i in range(n)]
    C = self.ifmt(k, C)
    
    invn = pow(n, mod - 2, mod)
    return [C[i] * invn % mod for i in range(n0)]

conv = Convolution()

def fps_inv(f, deg):
  res = [pow(f[0], mod - 2, mod)]
  d = 1
  while d < deg:
    d <<= 1
    f_trunc = f[:min(len(f), d)]
    fg = conv.Convolve(res, f_trunc)
    
    ln = len(fg)
    for i in range(ln):
      fg[i] = -fg[i] % mod
    fg += [0] * (d - ln)
    fg[0] = (fg[0] + 2) % mod
    
    res = conv.Convolve(res, fg)[:d]
  return res[:deg]

def calc_g():
  n = len(v)
  if n == 0:
    return [0] * (M + 1)
  
  deg = M + 2
  polys = [[1, -vi % mod] for vi in v]
  
  while len(polys) > 1:
    new_polys = []
    for i in range(0, len(polys), 2):
      if i + 1 < len(polys):
        q_new = conv.Convolve(polys[i], polys[i + 1])
        new_polys.append(q_new[:deg] if len(q_new) > deg else q_new)
      else:
        new_polys.append(polys[i])
    polys = new_polys
  
  Q = polys[0][:deg]
  Q_deriv = [(k + 1) * Q[k + 1] % mod for k in range(len(Q) - 1)]
  neg_Q_deriv = [-x % mod for x in Q_deriv]
  
  Q_inv = fps_inv(Q, M + 1)
  S = conv.Convolve(neg_Q_deriv, Q_inv)[:M + 1]
  
  return [n] + S[:M]

g = calc_g()

# メビウス関数
mobius = [0] * (M + 1)
mobius[1] = 1
spf = list(range(M + 1))
for i in range(2, int(M ** 0.5) + 1):
  if spf[i] == i:
    for j in range(i * i, M + 1, i):
      if spf[j] == j:
        spf[j] = i

for i in range(2, M + 1):
  p = spf[i]
  prev = i // p
  mobius[i] = 0 if prev % p == 0 else -mobius[prev]

# 約数
divisors = [[] for _ in range(M + 1)]
for i in range(1, M + 1):
  for j in range(i, M + 1, i):
    divisors[j].append(i)

# solve 展開
res = []
for n in range(1, M + 1):
  f = 0
  for d in divisors[n]:
    m = mobius[n // d]
    if m:
      f = (f + m * pow(g[n // d], d, mod)) % mod
  res.append(str(f))

print(' '.join(res))
0