結果
問題 | No.2904 Distinct Multisets in a Way |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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)