結果

問題 No.2904 Distinct Multisets in a Way
コンテスト
ユーザー PNJ
提出日時 2024-09-27 20:47:22
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 165 ms / 2,000 ms
コード長 1,209 bytes
コンパイル時間 341 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 105,256 KB
最終ジャッジ日時 2024-09-27 20:47:38
合計ジャッジ時間 6,158 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 998244353
inv_2 = (mod + 1) // 2

n = 10**6
inv = [1 for j in range(n+1)]
for a in range(2,n+1):
  # ax + py = 1 <=> rx + p(-x-qy) = -q => x = -(inv[r]) * (p//a)  (r = p % a)
  res = (mod - inv[mod%a]) * (mod // a)
  inv[a] = res % mod

def fps_pow_sparse(f,k,deg = -1): # F = f^k,fF' = kFf'

  if k == 0:
    return [1] + [0] * (deg - 1)
  
  if len(f) == 0:
    return [0] * deg
  
  if deg == -1:
    deg = f[-1][0]

  i,a = f[0]
  inv_0 = pow(a,-1,mod)
  for l in range(len(f)):
    j,aa = f[l]
    j -= i
    aa = aa * inv_0 % mod
    f[l] = (j,aa)

  if i * k > deg:
    return [0] * deg

  F = [1]
  for n in range(deg - i * k - 1):
    c = 0
    res = 0
    for j,aa in f:
      if j == 0:
        continue
      if n - j + 1 >= 0:
        res = (res + F[n - j + 1] * (j * aa % mod) % mod) % mod
      if n - j + 1 >= 0:
        c = (c - aa * (F[n - j + 1] * (n - j + 1) % mod) % mod) % mod
    c = (c + res * k % mod) % mod
    c = c * inv[n + 1] % mod
    F.append(c)

  F = [0] * (i * k) + F
  a = pow(a,k,mod)
  for i in range(deg):
    F[i] = F[i] * a % mod
  return F

N = int(input())
f = [(0,1),(1,1),(2,1)]
f = fps_pow_sparse(f,N,N + 1)
ans = f[N] - 1
ans = ans * inv_2 % mod
print(ans)
0