結果

問題 No.3053 $((0 \And 1)\mathop{|}2)\oplus 3$
ユーザー suisen
提出日時 2025-01-18 16:29:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 33 ms / 2,000 ms
コード長 1,304 bytes
コンパイル時間 1,252 ms
コンパイル使用メモリ 76,312 KB
実行使用メモリ 8,608 KB
最終ジャッジ日時 2025-03-08 00:10:28
合計ジャッジ時間 2,768 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

// correct

#include <iostream>
#include <vector>

#include <atcoder/modint>

using mint = atcoder::modint998244353;

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

    std::string n_str;
    std::cin >> n_str;

    const int l = n_str.size();
    std::vector<int> n_digits(l);
    for (int i = 0; i < l; ++i) {
        n_digits[l - 1 - i] = n_str[i] - '0';
    }

    // returns x^n
    auto nth_pow = [&](mint x) {
        mint res = 1;
        for (int i = 0; i < l; ++i) {
            if (n_digits[i]) res *= x;
            x *= x;
        }
        return res;
    };

    mint ans = 0;

    // 1
    {
        mint n = 0;
        for (int i = l - 1; i >= 0; --i) {
            n *= 2;
            n += n_digits[i];
        }
        ans += 2 * n * nth_pow(3) / 3;
    }
    // 0
    {
        // r^(2^i)
        mint pow_r_doubling = mint(3) / 2;
        // 2^i
        mint pow_2 = 1;

        mint ans_0 = 0;
        for (int i = 0; i < l; ++i) {
            if (n_digits[i] == 0) {
                ans_0 += pow_2;
            } else {
                ans_0 *= pow_r_doubling;
            }
            pow_r_doubling *= pow_r_doubling;
            pow_2 *= 2;
        }
        ans += ans_0 * nth_pow(2) * 4 / 9;
    }

    std::cout << ans.val() << std::endl;
}
0