結果
問題 |
No.1191 数え上げを愛したい(数列編)
|
ユーザー |
|
提出日時 | 2025-04-05 13:15:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 94 ms / 2,000 ms |
コード長 | 1,763 bytes |
コンパイル時間 | 329 ms |
コンパイル使用メモリ | 82,732 KB |
実行使用メモリ | 74,088 KB |
最終ジャッジ日時 | 2025-04-05 13:15:28 |
合計ジャッジ時間 | 3,327 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
## https://yukicoder.me/problems/no/3078 MOD = 998244353 class CombinationCalculator: """ modを考慮したPermutation, Combinationを計算するためのクラス """ def __init__(self, size, mod): self.mod = mod self.factorial = [0] * (size + 1) self.factorial[0] = 1 for i in range(1, size + 1): self.factorial[i] = (i * self.factorial[i - 1]) % self.mod self.inv_factorial = [0] * (size + 1) self.inv_factorial[size] = pow(self.factorial[size], self.mod - 2, self.mod) for i in reversed(range(size)): self.inv_factorial[i] = ((i + 1) * self.inv_factorial[i + 1]) % self.mod def calc_combination(self, n, r): if n < 0 or n < r or r < 0: return 0 if r == 0 or n == r: return 1 ans = self.inv_factorial[n - r] * self.inv_factorial[r] ans %= self.mod ans *= self.factorial[n] ans %= self.mod return ans def calc_permutation(self, n, r): if n < 0 or n < r: return 0 ans = self.inv_factorial[n - r] ans *= self.factorial[n] ans %= self.mod return ans def main(): N, M, A, B = map(int, input().split()) if A * (N - 1) > B: print(0) return combi = CombinationCalculator(M + N, MOD) answer = 0 for n in range(A * (N - 1), B + 1): m1 = n - (A * (N - 1)) m2 = N - 2 x = combi.calc_combination(m1 + m2, m2) x *= combi.factorial[N] x %= MOD x *= (M - (1 + n) + 1) x %= MOD answer += x answer %= MOD print(answer) if __name__ == "__main__": main()