結果
問題 | No.1310 量子アニーリング |
ユーザー |
![]() |
提出日時 | 2020-12-07 20:09:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 114 ms / 2,000 ms |
コード長 | 847 bytes |
コンパイル時間 | 173 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 118,656 KB |
最終ジャッジ日時 | 2024-09-17 14:02:21 |
合計ジャッジ時間 | 3,495 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
N = int(input())p = 998244353PN = 2 * 10 ** 5 + 100fact = [1, 1]factinv = [1, 1]inv = [0, 1]def cmb(n, r, p):if (r < 0) or (n < r):return 0r = min(r, n - r)return fact[n] * factinv[r] * factinv[n-r] % pfor i in range(2, PN + 1):fact.append((fact[-1] * i) % p)inv.append((-inv[p % i] * (p // i)) % p)factinv.append((factinv[-1] * inv[-1]) % p)po = [0]*(PN)po[0] = 1for i in range(1,N+2):po[i] = po[i-1]*2%pans = 0if N%4 == 0:cnt = 0for i in range(N//4):ans = (ans+(cmb(N,i*2,p)*4*po[N-i*4]))%pcnt = (cnt + cmb(N,i*2,p)*4)%pans = (ans+(po[N] - cnt)%p)%pelif N % 2 ==0:for a,i in enumerate(range(N,-1,-4)):ans = (ans+(cmb(N,a*2,p)*4*po[i]))%pelse:for i in range(N//2+1):ans = (ans+(cmb(N,i,p)*2*po[N-(i*2)]))%pprint(ans)