結果

問題 No.2904 Distinct Multisets in a Way
ユーザー PNJPNJ
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 77 ms
66,428 KB
testcase_01 AC 151 ms
104,768 KB
testcase_02 AC 96 ms
67,544 KB
testcase_03 AC 149 ms
104,908 KB
testcase_04 AC 82 ms
70,104 KB
testcase_05 AC 83 ms
69,028 KB
testcase_06 AC 82 ms
69,372 KB
testcase_07 AC 79 ms
66,800 KB
testcase_08 AC 79 ms
66,928 KB
testcase_09 AC 78 ms
67,196 KB
testcase_10 AC 85 ms
68,648 KB
testcase_11 AC 87 ms
69,448 KB
testcase_12 AC 86 ms
70,980 KB
testcase_13 AC 78 ms
67,288 KB
testcase_14 AC 94 ms
70,184 KB
testcase_15 AC 78 ms
66,916 KB
testcase_16 AC 87 ms
70,552 KB
testcase_17 AC 82 ms
69,508 KB
testcase_18 AC 83 ms
69,232 KB
testcase_19 AC 84 ms
69,028 KB
testcase_20 AC 76 ms
67,676 KB
testcase_21 AC 80 ms
69,564 KB
testcase_22 AC 81 ms
69,504 KB
testcase_23 AC 79 ms
68,176 KB
testcase_24 AC 119 ms
95,056 KB
testcase_25 AC 165 ms
104,620 KB
testcase_26 AC 87 ms
76,396 KB
testcase_27 AC 102 ms
91,464 KB
testcase_28 AC 136 ms
102,640 KB
testcase_29 AC 104 ms
91,268 KB
testcase_30 AC 115 ms
94,560 KB
testcase_31 AC 148 ms
102,516 KB
testcase_32 AC 88 ms
74,420 KB
testcase_33 AC 87 ms
78,884 KB
testcase_34 AC 87 ms
78,860 KB
testcase_35 AC 141 ms
102,640 KB
testcase_36 AC 130 ms
102,764 KB
testcase_37 AC 149 ms
105,256 KB
testcase_38 AC 87 ms
72,128 KB
testcase_39 AC 131 ms
103,000 KB
testcase_40 AC 108 ms
91,492 KB
testcase_41 AC 136 ms
92,776 KB
testcase_42 AC 125 ms
99,536 KB
testcase_43 AC 92 ms
71,848 KB
権限があれば一括ダウンロードができます

ソースコード

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