#962195 (C++23) No.2679 MODice

• 問題: No.2679 MODice
• ユーザー: downer
• 提出日時: 2024-03-20 21:12:46
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 3,819 bytes
• コンパイル時間: 2,408 ms
• コンパイル使用メモリ: 337,328 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-04-16 11:56:26
• 合計ジャッジ時間: 5,445 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 15

コンパイルメッセージ

In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/vector:67,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/functional:66,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/x86_64-pc-linux-gnu/bits/stdc++.h:55,
                 from main.cpp:1:
In function '_ForwardIterator std::uninitialized_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = MontgomeryModInt64*; _ForwardIterator = MontgomeryModInt64*]',
    inlined from 'constexpr _ForwardIterator std::__uninitialized_copy_a(_InputIterator, _Sentinel, _ForwardIterator, allocator<_Tp>&) [with _InputIterator = MontgomeryModInt64*; _Sentinel = MontgomeryModInt64*; _ForwardIterator = MontgomeryModInt64*; _Tp = MontgomeryModInt64]' at /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_uninitialized.h:635:32,
    inlined from 'constexpr std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = MontgomeryModInt64; _Alloc = std::allocator<MontgomeryModInt64>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/vector.tcc:257:35,
    inlined from 'int main()' at main.cpp:139:14:
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_uninitialized.h:273:31: warning: 'void* __builtin_memcpy(void*, const void*, long unsigned int)' writing between 1 and 48 bytes into a region of size 0 overflows the destination [-Wstringop-overflow=]
  273 |               __builtin_memcpy(std::__niter_base(__result),
      |               ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  274 |                                std::__niter_base(__first),
      |                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~
  275 |                                __n * sizeof(_ValT));
      |                                ~~~~~~~~~~~~~~~~~~~~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++

ソースコード

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

// modint
// using mint = MontgomeryModInt64; と定義する
// mint::set_mod(M); でmodをMに設定する
struct MontgomeryModInt64 {
    using mint = MontgomeryModInt64;
    using u64 = uint64_t;
    using u128 = __uint128_t;

    // static変数
    // R = 2 ^ 64
    static inline u64 MOD;
    static inline u64 INV_MOD;  // INV_MOD * MOD ≡ 1 (mod 2 ^ 64)
    static inline u64 T128;     // 2 ^ 128 (mod MOD)

    u64 val;

    // コンストラクタ
    // MODを足す？
    MontgomeryModInt64(): val(0) {}
    MontgomeryModInt64(long long v): val(MR((u128(v) + MOD) * T128)) {}

    // 値を返す
    u64 get() const {
        u64 res = MR(val);
        return res >= MOD ? res - MOD : res;
    }

    // static関数
    static u64 get_mod() { return MOD; }
    static void set_mod(u64 mod) {
        MOD = mod;
        T128 = -u128(mod) % mod;
        INV_MOD = get_inv_mod();
    }
    // ニュートン法で逆元を求める
    static u64 get_inv_mod() {
        u64 res = MOD;
        for(int i = 0; i < 5; ++i) res *= 2 - MOD * res;
        return res;
    }
    // モンゴメリリダクション
    static u64 MR(const u128& v) {
        return (v + u128(u64(v) * u64(-INV_MOD)) * MOD) >> 64;
    }

    // 算術演算子
    mint operator - () const { return mint() - mint(*this); }

    mint operator + (const mint& r) const { return mint(*this) += r; }
    mint operator - (const mint& r) const { return mint(*this) -= r; }
    mint operator * (const mint& r) const { return mint(*this) *= r; }
    mint operator / (const mint& r) const { return mint(*this) /= r; }

    mint& operator += (const mint& r) {
        if((val += r.val) >= 2 * MOD) val -= 2 * MOD;
        return *this;
    }
    mint& operator -= (const mint& r) {
        if((val += 2 * MOD - r.val) >= 2 * MOD) val -= 2 * MOD;
        return *this;
    }
    mint& operator *= (const mint& r) {
        val = MR(u128(val) * r.val);
        return *this;
    }
    mint& operator /= (const mint& r) {
        *this *= r.inv();
        return *this;
    }

    mint inv() const { return pow(MOD - 2); }
    mint pow(u128 n) const {
        mint res(1), mul(*this);
        while(n > 0) {
            if(n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }

    // その他演算子
    bool operator == (const mint& r) const {
        return (val >= MOD ? val - MOD : val) == (r.val >= MOD ? r.val - MOD : r.val);
    }
    bool operator != (const mint& r) const {
        return (val >= MOD ? val - MOD : val) != (r.val >= MOD ? r.val - MOD : r.val);
    }

    // 入力
    friend istream& operator >> (istream& is, mint& x) {
        long long t;
        is >> t;
        x = mint(t);
        return is;
    }
    // 出力
    friend ostream& operator << (ostream& os, const mint& x) {
        return os << x.get();
    }
    friend mint modpow(const mint& r, long long n) {
        return r.pow(n);
    } 
    friend mint modinv(const mint& r) {
        return r.inv();
    }
};

using mint = MontgomeryModInt64;


int main() {
    mint::set_mod(998244353);
    int N, K;
    cin >> N >> K;
    vector<mint> ans(6, 0);
    ans[0] = 1;
    vector<mint> db(6, mint(1) / 6);

    while(N) {
        if(N & 1) {
            vector<mint> na(6, 0);
            for(int i = 0; i < 6; i++) {
                for(int j = 0; j < 6; j++) {
                    na[(i + j) % 6] += ans[i] * db[i];
                }
            }
            ans = na;
        }
        vector<mint> ndb(6, 0);
        for(int i = 0; i < 6; i++) {
            for(int j = 0; j < 6; j++) {
                ndb[(i + j) % 6] += db[i] * db[j];
            }
        }
        db = ndb;
        N >>= 1;
    }

    cout << ans[K] << endl;

    return 0;
}