結果

問題 No.3160 Party Game
コンテスト
ユーザー みうね
提出日時 2025-05-11 22:52:39
言語 Ruby
(3.4.1)
結果
AC  
実行時間 1,479 ms / 2,000 ms
コード長 886 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,296 ms
コンパイル使用メモリ 8,224 KB
実行使用メモリ 75,520 KB
最終ジャッジ日時 2025-05-27 21:54:07
合計ジャッジ時間 45,025 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff #
raw source code 

MOD = 998244353
MAX_V = 2000001

# 階乗、逆元、逆階乗のテーブル
fac = Array.new(MAX_V, 0)
finv = Array.new(MAX_V, 0)
inv = Array.new(MAX_V, 0)

fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1

(2...MAX_V).each do |i|
  fac[i] = fac[i - 1] * i % MOD
  inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD
  finv[i] = finv[i - 1] * inv[i] % MOD
end

n, m = gets.split.map(&:to_i)

cumnoc = Array.new(m + 1, 0)
(0..m).each do |i|
  break if i * n > m
  cumnoc[i] = fac[m - i * n + n] * finv[n] % MOD * finv[m - i * n] % MOD
end

if n == 1
  (0..m).each do |i|
    cumnoc[i] = (cumnoc[i] - n) % MOD
  end
else
  cumnoc[0] = (cumnoc[0] - n) % MOD
end

noc = Array.new(m, 0)
(0...m).each do |i|
  noc[i] = (cumnoc[i] - cumnoc[i + 1]) % MOD
end

ans = 0
(0...m).each do |i|
  ans = (ans + i * noc[i]) % MOD
end

total = cumnoc[0]
ans = ans * total.pow(MOD - 2, MOD) % MOD
puts ans
0