#1177846 (C++23(gcc16)) No.3554 Rurumaru Function Problem 2

• 問題: No.3554 Rurumaru Function Problem 2
• ユーザー: Aob-11
• 提出日時: 2026-08-21 14:32:47
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 2,767 bytes
• コンパイル時間: 2,137 ms
• コンパイル使用メモリ: 357,504 KB
• 実行使用メモリ: 9,348 KB
• 最終ジャッジ日時: 2026-08-21 14:32:53
• 合計ジャッジ時間: 3,995 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 12

ソースコード

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(3)
#define DB double
#define LL long long
#define ULL unsigned long long
#define uint unsigned int
#define in128 int128
#define cint const int
#define cLL const LL
#define For(z,e1,e2) for(int z=(e1);z<=(e2);z++)
#define Rof(z,e1,e2) for(int z=(e2);z>=(e1);z--)
#define inint(e) scanf("%d",&e)
#define inll(e) scanf("%lld",&e)
#define outll(e) printf("%lld\n",e)
#define exc(e) if(e) continue
#define stop(e) if(e) break
#define ret(e) if(e) return
#define pb push_back

cLL mod = 998244353ll;

LL U[35];
__int128 memo[65][2][2];
LL m_val, v_val;

__int128 dfs(int pos, int less_x, int less_y) {
    if (pos == -1) return 1;
    if (memo[pos][less_x][less_y] != -1) return memo[pos][less_x][less_y];
    
    __int128 res = 0;
    int limit_x = less_x ? 1 : (int)((m_val >> pos) & 1);
    int limit_y = less_y ? 1 : (int)((m_val >> pos) & 1);
    int bit_v = (int)((v_val >> pos) & 1);

    for (int bx = 0; bx <= limit_x; ++bx) {
        for (int by = 0; by <= limit_y; ++by) {
            int actual = (pos % 2 == 0) ? (bx & by) : (bx | by);
            if (actual == bit_v) {
                res += dfs(pos - 1, less_x | (bx < limit_x), less_y | (by < limit_y));
            }
        }
    }
    return memo[pos][less_x][less_y] = res;
}

__int128 C(LL n, LL v) {
    if (n <= 0) return 0;
    m_val = n - 1;
    v_val = v;
    For(i, 0, 61) For(j, 0, 1) For(k, 0, 1) memo[i][j][k] = -1;
    return dfs(61, 0, 0);
}

void print128(__int128 x) {
    if (x == 0) {
        printf("0\n");
        return;
    }
    char buf[45];
    int cnt = 0;
    while (x > 0) {
        buf[cnt++] = (char)('0' + (x % 10));
        x /= 10;
    }
    Rof(i, 0, cnt - 1) putchar(buf[i]);
    putchar('\n');
}

void main_solve() {
    LL N;
    if (scanf("%lld", &N) != 1) return;

    U[0] = 0;
    For(i, 1, 30) U[i] = (U[i - 1] << 2) | 2;

    vector<LL> B(35, N + 1);
    B[0] = 1;

    For(k, 1, 30) {
        if (B[k - 1] > N) {
            B[k] = N + 1;
            continue;
        }
        
        LL L = B[k - 1], R = N + 1;
        LL ans = N + 1;
        while (L <= R) {
            LL mid = L + (R - L) / 2;
            if (C(mid, U[k]) > C(mid, U[k - 1])) {
                ans = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        B[k] = ans;
    }

    __int128 total_sum = 0;
    
    For(k, 0, 30) {
        LL start = B[k];
        LL end = (k == 30) ? (N + 1) : B[k + 1];
        if (start > N) break;
        if (end > N + 1) end = N + 1;
        
        if (start < end) {
            total_sum += (__int128)U[k] * (end - start);
        }
    }

    print128(total_sum);
}

int main() {
    main_solve();
    return 0;
}