結果
問題 | No.1310 量子アニーリング |
ユーザー |
|
提出日時 | 2024-09-16 00:50:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 159 ms / 2,000 ms |
コード長 | 1,800 bytes |
コンパイル時間 | 245 ms |
コンパイル使用メモリ | 82,288 KB |
実行使用メモリ | 78,592 KB |
最終ジャッジ日時 | 2024-09-16 00:51:02 |
合計ジャッジ時間 | 3,093 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
## https://yukicoder.me/problems/no/1310MOD = 998244353class CombinationCalculator:"""modを考慮したPermutation, Combinationを計算するためのクラス"""def __init__(self, size, mod):self.mod = modself.factorial = [0] * (size + 1)self.factorial[0] = 1for i in range(1, size + 1):self.factorial[i] = (i * self.factorial[i - 1]) % self.modself.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.moddef calc_combination(self, n, r):if n < 0 or n < r or r < 0:return 0if r == 0 or n == r:return 1ans = self.inv_factorial[n - r] * self.inv_factorial[r]ans %= self.modans *= self.factorial[n]ans %= self.modreturn ansdef calc_permutation(self, n, r):if n < 0 or n < r:return 0ans = self.inv_factorial[n - r]ans *= self.factorial[n]ans %= self.modreturn ansdef main():N = int(input())combi = CombinationCalculator(N, MOD)answer = 0for n in range(N):# s_1 = +として「変化がある点のかずの組み合わせ」で主客転倒を行うif n % 2 == 0:E = - (N - 2 * n)else:E = - (N - 2 - 2 * n)absE = abs(E)ans = pow(2, absE, MOD)c = combi.calc_combination(N - 1, n)answer += (ans * c) % MODanswer %= MODanswer *= 2answer %= MODprint(answer)if __name__ == "__main__":main()