結果
問題 | No.685 Logical Operations |
ユーザー |
![]() |
提出日時 | 2021-01-12 20:35:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 57 ms / 2,000 ms |
コード長 | 1,549 bytes |
コンパイル時間 | 153 ms |
コンパイル使用メモリ | 82,588 KB |
実行使用メモリ | 66,420 KB |
最終ジャッジ日時 | 2024-11-21 10:07:15 |
合計ジャッジ時間 | 2,488 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
mod = 10 ** 9 + 7 # x=yのとき条件が成り立たないので # 大小関係無視して後で2で割ればOK N = int(input()) S = bin(N)[2:] L = len(S) dp = [[[[0] * 3 for _ in range(3)] for _ in range(2)] for _ in range(L + 1)] dp[0][0][0][0] = 1 for i, s in enumerate(S): nd = int(s) for ja in range(2): for jb in range(2): for k in range(3): for a in range(2): for b in range(2): ni = i + 1 nja = ja njb = jb nk = k if nja == 0: if nd > a: nja = 1 if nd < a: continue if njb == 0: if nd > b: njb = 1 if nd < b: continue if nk == 0: if a ^ b: nk += 1 if a & b: continue elif nk == 1: if a & b: nk += 1 dp[ni][nja][njb][nk] += dp[i][ja][jb][k] dp[ni][nja][njb][nk] %= mod ans = 0 for ja in range(2): for jb in range(2): ans += dp[L][ja][jb][2] ans %= mod print(ans * pow(2, mod - 2, mod) % mod)