#1052007 (C++23) No.3399 One Two Three Two Three

• 問題: No.3399 One Two Three Two Three
• ユーザー: akakimidori
• 提出日時: 2025-03-12 20:37:42
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 519 ms / 4,000 ms
• コード長: 5,391 bytes
• コンパイル時間: 3,462 ms
• コンパイル使用メモリ: 164,916 KB
• 実行使用メモリ: 7,848 KB
• 最終ジャッジ日時: 2025-12-05 23:31:38
• 合計ジャッジ時間: 9,270 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

ファイルパターン	結果
sample	AC * 5
other	AC * 40

ソースコード

#include <cstdint>
#include <iostream>
#include <vector>
#include <initializer_list>

#include <atcoder/convolution>
#include <atcoder/modint>

using i64 = int64_t;
using i32 = int32_t;
using u32 = uint32_t;

using mint = atcoder::modint998244353;

template <class T>
T read() {
    T v;
    std::cin >> v;
    return v;
}

template <class T>
std::vector<T> vec(T elem, std::size_t len) {
    return std::vector<T>(len, elem);
}

class fps {
public:
    fps() = default;
    fps(const std::vector<mint> &x) : a(x) {}
    fps(const std::size_t len) : a(len, mint(0)) {}
    fps(const std::initializer_list<mint> init) : a(init.begin(), init.end()) {}
    static fps zero() { return fps(); }
    static fps one() { return fps{1}; }
    fps &operator+=(const fps &rhs) {
        if (a.size() < rhs.a.size()) {
            a.resize(rhs.a.size(), mint(0));
        }
        for (std::size_t i = 0; i < rhs.a.size(); ++i) a[i] += rhs.a[i];
        return *this;
    }
    fps &operator-=(const fps &rhs) {
        if (a.size() < rhs.a.size()) {
            a.resize(rhs.a.size(), mint(0));
        }
        for (std::size_t i = 0; i < rhs.a.size(); ++i) a[i] -= rhs.a[i];
        return *this;
    }
    fps &operator*=(const fps &rhs) {
        a = atcoder::convolution(a, rhs.a);
        return *this;
    }
    friend fps operator+(const fps &lhs, const fps &rhs) {
        return fps(lhs) += rhs;
    }
    friend fps operator-(const fps &lhs, const fps &rhs) {
        return fps(lhs) -= rhs;
    }
    friend fps operator*(const fps &lhs, const fps &rhs) {
        return fps(lhs) *= rhs;
    }
    const mint &operator[](const std::size_t x) const { return a.at(x); }
    mint &operator[](const std::size_t x) { return a.at(x); }
    std::size_t size() const { return a.size(); }
    void truncate(const std::size_t len) {
        if (len < a.size()) {
            a.resize(len);
        }
    }
    void resize(const std::size_t len) { a.resize(len, mint(0)); }
    fps step(const std::size_t s, const std::size_t k) const {
        assert(k > 0);
        std::vector<mint> res;
        for (std::size_t i = s; i < a.size(); i += k) res.emplace_back(a[i]);
        return res;
    }
    fps calc2() const {
        auto res = a;
        for (std::size_t i = 1; i < res.size(); i += 2) {
            res[i] = -res[i];
        }
        return res;
    }
    fps calc3() const {
        const std::size_t len = a.size();
        auto x = vec(fps(len), 2);
        auto y = vec(fps(len), 2);
        for (std::size_t i = 0; i < len; ++i) {
            const auto v = a[i];
            if (i % 3 == 0) {
                x[0][i] = y[0][i] = v;
            } else if (i % 3 == 1) {
                x[1][i] = v;
                y[0][i] = y[1][i] = -v;
            } else {
                y[1][i] = v;
                x[0][i] = x[1][i] = -v;
            }
        }
        return x[0] * y[0] - x[1] * y[1];
    }

private:
    std::vector<mint> a;
};

i64 ilog(i64 n, const i64 r) {
    assert(n >= 1 && r > 1);
    i64 c = 0;
    while (n >= r) {
        n /= r;
        c += 1;
    }
    return c;
}

int main() {
    const i64 n = read<i64>();
    const i64 h = ilog(n, 3);
    const i64 w = ilog(n, 2);
    const fps base{1, -1, -1, -1};
    const auto two = ([&] {
        auto two = vec(fps::one(), w + 1);
        for (std::size_t i = 1; i < two.size(); ++i) {
            const auto f = two[i - 1] * base;
            two[i] = (f * f.calc2()).step(0, 2);
        }
        return two;
    })();
    const auto three = ([&] {
        auto three = vec(fps::one(), h + 1);
        for (std::size_t i = 1; i < three.size(); ++i) {
            const auto f = three[i - 1] * base;
            three[i] = (f * f.calc3()).step(0, 3);
        }
        return three;
    })();
    auto calc_n = [&](std::size_t i, std::size_t j) -> i64 {
        i64 v = n;
        while (i--) v /= 3;
        while (j--) v /= 2;
        return v;
    };
    auto dp = vec(vec(std::pair<fps, fps>{}, w + 1), h + 1);
    mint ans = 0;
    for (std::size_t i = 0; i <= h; ++i) {
        fps bm_nu;
        for (std::size_t j = 0; j <= w; ++j) {
            fps nu, de;
            if (i > 0) {
                const auto [a, b] = std::exchange(dp[i - 1][j], {});
                const auto f = b.calc3();
                const auto r = calc_n(i - 1, j) % 3;
                nu = (a * f).step(r, 3) * two[j];
                de = (b * f).step(0, 3) * two[j];
            }
            if (j > 0) {
                const auto &[a, b] = dp[i][j - 1];
                const auto f = b.calc2();
                const auto r = calc_n(i, j - 1) % 2;
                bm_nu = (bm_nu * f).step(r, 2) * three[i];
                nu += (a * f).step(r, 2) * three[i];
                if (i == 0) de = (b * f).step(0, 2) * three[i];
            }
            if (i == 0 && j == 0) {
                nu = fps::one();
                de = fps::one();
            }
            bm_nu *= base;
            de *= base;
            bm_nu += nu * fps{0, 1};
            const auto m = calc_n(i, j);
            bm_nu.truncate(m + 1);
            nu.truncate(m + 1);
            de.truncate(m + 1);
            if (m == 1) {
                ans += bm_nu[0] * -de[1] + bm_nu[1];
                break;
            }
            dp[i][j] = std::make_pair(nu, de);
        }
    }
    std::cout << ans.val() << std::endl;
    return 0;
}