結果
問題 |
No.1310 量子アニーリング
|
ユーザー |
![]() |
提出日時 | 2023-03-21 11:57:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 316 ms / 2,000 ms |
コード長 | 1,026 bytes |
コンパイル時間 | 184 ms |
コンパイル使用メモリ | 81,936 KB |
実行使用メモリ | 102,912 KB |
最終ジャッジ日時 | 2024-09-18 14:19:30 |
合計ジャッジ時間 | 3,523 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
# うーん、単なる数字の組み合わせではなく掛け算、偶数の時は違うらしい # これは量子論をかじってないと思いつかないと思う、悪問と思う # t=s1s2とすれば、t1****tn = (s1***sn)**2 = 1であり、マイナスのtは偶数個しかない N = int(input()) mod = 998244353 # nCrメモ化パッケージ factorial = [1] #0分 inverse = [1] #0分 for i in range(1, N+1): factorial.append(factorial[-1]*i%mod) inverse.append(pow(factorial[-1], mod-2, mod)) def nCr_fast(N, R, MOD): if N < R or R < 0: return 0 elif R == 0 or R == N: return 1 return factorial[N]*inverse[R]*inverse[N-R]%MOD ans = 0 # これは量子論をかじってないと思いつかないと思う、悪問と思う # t=s1s2とすれば、t1****tn = (s1***sn)**2 = 1であり、マイナスのtは偶数個しかない for i in range(0, N+1, 2): calc = nCr_fast(N, i, mod)*2 add = calc*pow(2, abs(N-i*2), mod) ans += add ans %= mod print(ans)