結果
問題 |
No.2529 Treasure Hunter
|
ユーザー |
|
提出日時 | 2025-07-05 18:07:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 163 ms / 2,000 ms |
コード長 | 2,548 bytes |
コンパイル時間 | 503 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 77,800 KB |
最終ジャッジ日時 | 2025-07-05 18:07:31 |
合計ジャッジ時間 | 3,597 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 22 |
ソースコード
# https://yukicoder.me/problems/no/2529 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 solve(N, M): matrix =[[0] *3 for _ in range(3)] # 向き先が0 for i in range(3): matrix[i][0] = 1 # 向き先が1 for i in range(3): matrix[i][1] = N - i # 向き先が2 if N <= 3: matrix[0][2] = 0 else: y = (N * (N - 3)) % MOD matrix[0][2] = (y * pow(2, MOD - 2, MOD)) % MOD matrix[1][2] = ((N - 3) * (N - 2)) % MOD matrix[1][2] *= pow(2, MOD - 2, MOD) matrix[1][2] %= MOD if N <= 3: matrix[2][2] = 0 else: y1 = pow(N - 2, 2, MOD) y1 -= (N - 2) y1 %= MOD y1 *= pow(2, MOD - 2, MOD) y1 %= MOD y1 -= N - 4 y1 %= MOD matrix[2][2] = y1 dp = [0] * 3 dp[0] = 1 for _ in range(M): new_dp = [0] * 3 for j in range(3): for k in range(3): new_dp[k] += (dp[j] * matrix[j][k]) % MOD new_dp[k] %= MOD dp = new_dp answer = 0 for j in range(3): answer += dp[j] answer %= MOD return answer def main(): T = int(input()) answers = [] for _ in range(T): N, M = map(int, input().split()) ans = solve(N, M) answers.append(ans) for ans in answers: print(ans) if __name__ == "__main__": main()