結果
問題 | No.1968 Distance |
ユーザー |
![]() |
提出日時 | 2022-06-03 22:05:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,465 bytes |
コンパイル時間 | 1,685 ms |
コンパイル使用メモリ | 168,156 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-21 02:44:51 |
合計ジャッジ時間 | 2,547 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h>using namespace std;const long long MOD = 998244353;long long modpow(long long a, long long b){long long ans = 1;while (b > 0){if (b % 2 == 1){ans *= a;ans %= MOD;}a *= a;a %= MOD;b /= 2;}return ans;}long long modinv(long long a){return modpow(a % MOD, MOD - 2);}long long integral(long long L, long long R, long long a, long long b){long long ans = 0;ans += R * R % MOD * modinv(2) % MOD * a % MOD;ans += MOD - L * L % MOD * modinv(2) % MOD * a % MOD;ans += (R - L + MOD) * b % MOD;ans %= MOD;return ans;}int main(){long long N;cin >> N;long long ans = 0;long long c = 1;long long R = modinv(2);while (true){if (N <= ((long long) 1 << (c - 1)) - 1){ans += integral(0, R, 1, 0);break;}long long L = modinv(((long long) 1 << c) + 1);long long N2 = N;N2 -= ((long long) 1 << c) - 1;long long b = modinv((long long) 1 << c);long long a = MOD - b;long long x = 1, y = (long long) 1 << c;int t = 0;while (N2 > 0){if (t % 2 == 0){N2 -= x;b = 0;a = modinv((long long) 1 << (t / 2 + 1));x *= 2;} else {N2 -= y;b = modinv((long long) 1 << (c + 1 + t / 2));a = MOD - b;y *= 2;}t++;}ans += integral(L, R, a, b);c++;R = L;}ans %= MOD;ans *= 2;ans %= MOD;cout << ans << endl;}