結果
問題 | No.2483 Yet Another Increasing XOR Problem |
ユーザー | novaandcabral |
提出日時 | 2024-05-13 21:55:46 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,477 bytes |
コンパイル時間 | 170 ms |
コンパイル使用メモリ | 82,328 KB |
実行使用メモリ | 67,324 KB |
最終ジャッジ日時 | 2024-05-13 21:55:49 |
合計ジャッジ時間 | 2,791 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | RE | - |
testcase_01 | RE | - |
testcase_02 | RE | - |
testcase_03 | RE | - |
testcase_04 | RE | - |
testcase_05 | RE | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | RE | - |
testcase_20 | RE | - |
testcase_21 | RE | - |
testcase_22 | AC | 31 ms
53,480 KB |
testcase_23 | RE | - |
testcase_24 | RE | - |
ソースコード
MOD = 998244353 class Modint: def __init__(self, x): self.x = x % MOD if x >= 0 else (x % MOD + MOD) % MOD def __add__(self, other): return Modint((self.x + other.x) % MOD) def __sub__(self, other): return Modint((self.x - other.x) % MOD) def __mul__(self, other): return Modint((self.x * other.x) % MOD) def __pow__(self, exp): result = 1 base = self.x while exp > 0: if exp & 1: result = (result * base) % MOD base = (base * base) % MOD exp >>= 1 return Modint(result) def __truediv__(self, other): return self * other.__pow__(MOD - 2) def __str__(self): return str(self.x) def solve(): n = int(input()) x = 0 if n == 1: print(1) return while (1 << x) < n: x += 1 x -= 1 m = 1 << x t = Modint(2) ** (m - 1) * m times = [0] * (x + 2) for i in range(x + 1): k = Modint(2) ** (1 << i) times[i] = (k + 1 / k) / 2 n -= 1 ans = Modint(0) tt = Modint(1) for i in range(x - 1, -1, -1): if (n >> i) & 1: t2 = tt for j in range(i - 1, -1, -1): t2 *= 1 + times[j] ans += t2 * t tt *= times[i] ans += t * tt ans += (2 ** m - 1) ans += (2 ** m - 1) ans -= (2 ** (2 * m - n - 1) - 1) print(ans) if __name__ == "__main__": solve()