結果

問題 No.3554 Rurumaru Function Problem 2
コンテスト
ユーザー ルク
提出日時 2026-04-23 21:34:21
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,419 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,121 ms
コンパイル使用メモリ 216,528 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-05-22 21:47:19
合計ジャッジ時間 2,790 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
using i128 = __int128_t;

vector<int64> pow4(20), pow9(20);

// B_m(n):
// 全 m 桁列 × P_m(n) の中で AND = 0..0 になる組数
int64 zeroFP(int len, int64 n) {
    if (n <= 0) return 0;
    if (len == 0) return n; // n = 0 or 1

    int64 q = pow4[len - 1];

    if (n <= q) {
        return 2 * zeroFP(len - 1, n);
    }
    if (n <= 2 * q) {
        return 2 * pow9[len - 1] + zeroFP(len - 1, n - q);
    }
    if (n <= 3 * q) {
        return 3 * pow9[len - 1] + 4 * zeroFP(len - 1, n - 2 * q);
    }
    return 7 * pow9[len - 1] + 2 * zeroFP(len - 1, n - 3 * q);
}

// A_m(n):
// P_m(n) × P_m(n) の中で AND = 0..0 になる組数
int64 zeroPP(int len, int64 n) {
    if (n <= 0) return 0;
    if (len == 0) return n; // n = 0 or 1

    int64 q = pow4[len - 1];

    if (n < 2 * q) {
        return 0;
    }
    if (n <= 3 * q) {
        return 4 * zeroFP(len - 1, n - 2 * q)
             + zeroPP(len - 1, n - 2 * q);
    }
    return 5 * pow9[len - 1]
         + 4 * zeroFP(len - 1, n - 3 * q);
}

// Q_k = max { n | A_{k+1}(n) <= 3 * 9^k }
int64 upperBoundForValue(int k) {
    int64 lo = 0, hi = pow4[k + 1];
    int64 target = 3 * pow9[k];

    while (lo < hi) {
        int64 mid = (lo + hi + 1) / 2;
        if (zeroPP(k + 1, mid) <= target) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

string toString128(i128 x) {
    if (x == 0) return "0";
    string s;
    while (x > 0) {
        int d = (int)(x % 10);
        s.push_back(char('0' + d));
        x /= 10;
    }
    reverse(s.begin(), s.end());
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int64 N;
    cin >> N;

    pow4[0] = pow9[0] = 1;
    for (int i = 1; i < 20; i++) {
        pow4[i] = pow4[i - 1] * 4;
        pow9[i] = pow9[i - 1] * 9;
    }

    // U_k = (22...2)_4
    vector<int64> U;
    vector<int64> Q;

    U.push_back(0); // U_0

    for (int k = 0;; k++) {
        int64 q = upperBoundForValue(k);
        Q.push_back(q);
        if (q >= N) break;
        U.push_back(U.back() * 4 + 2); // U_{k+1} = 4 U_k + 2
    }

    i128 ans = 0;
    int64 prev = 0; // Q_{-1} = 0

    for (int k = 0; k < (int)Q.size() && prev < N; k++) {
        int64 up = min<int64>(N, Q[k]);
        ans += (i128)(up - prev) * U[k];
        prev = up;
    }

    cout << toString128(ans) << '\n';
    return 0;
}
0