#1139580 (C++17) No.3462 Buttons

• 問題: No.3462 Buttons
• ユーザー: dyktr_06
• 提出日時: 2025-12-09 04:57:26
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 710 ms / 2,000 ms
• コード長: 4,135 bytes
• コンパイル時間: 2,121 ms
• コンパイル使用メモリ: 215,656 KB
• 実行使用メモリ: 7,844 KB
• 最終ジャッジ日時: 2026-02-28 13:00:38
• 合計ジャッジ時間: 15,208 ms
• ジャッジサーバーID （参考情報）: judge1 / judge7

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

ソースコード

#include <bits/stdc++.h>

using namespace std;

const long long MOD = 998244353;

template <long long Modulus>
struct ModInt{
    long long val;
    static constexpr int mod() { return Modulus; }
    constexpr ModInt(const long long _val = 0) noexcept : val(_val) {
        normalize();
    }
    void normalize(){
        val = (val % Modulus + Modulus) % Modulus;
    }
    inline ModInt &operator+=(const ModInt &rhs) noexcept {
        if(val += rhs.val, val >= Modulus) val -= Modulus;
        return *this;
    }
    inline ModInt &operator-=(const ModInt &rhs) noexcept {
        if(val -= rhs.val, val < 0) val += Modulus;
        return *this;
    }
    inline ModInt &operator*=(const ModInt &rhs) noexcept {
        val = val * rhs.val % Modulus;
        return *this;
    }
    inline ModInt &operator/=(const ModInt &rhs) noexcept {
        val = val * inv(rhs.val).val % Modulus;
        return *this;
    }
    inline ModInt &operator++() noexcept {
        if(++val >= Modulus) val -= Modulus;
        return *this;
    }
    inline ModInt operator++(int) noexcept {
        ModInt t = val;
        if(++val >= Modulus) val -= Modulus;
        return t;
    }
    inline ModInt &operator--() noexcept {
        if(--val < 0) val += Modulus;
        return *this;
    }
    inline ModInt operator--(int) noexcept {
        ModInt t = val;
        if(--val < 0) val += Modulus;
        return t;
    }
    inline ModInt operator-() const noexcept { return (Modulus - val) % Modulus; }
    inline ModInt inv(void) const { return inv(val); }
    ModInt pow(long long n) const {
        assert(0 <= n);
        ModInt x = *this, r = 1;
        while(n){
            if(n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    ModInt inv(const long long n) const {
        long long a = n, b = Modulus, u = 1, v = 0;
        while(b){
            long long t = a / b;
            a -= t * b; std::swap(a, b);
            u -= t * v; std::swap(u, v);
        }
        u %= Modulus;
        if(u < 0) u += Modulus;
        return u;
    }
    friend inline ModInt operator+(const ModInt &lhs, const ModInt &rhs) noexcept { return ModInt(lhs) += rhs; }
    friend inline ModInt operator-(const ModInt &lhs, const ModInt &rhs) noexcept { return ModInt(lhs) -= rhs; }
    friend inline ModInt operator*(const ModInt &lhs, const ModInt &rhs) noexcept { return ModInt(lhs) *= rhs; }
    friend inline ModInt operator/(const ModInt &lhs, const ModInt &rhs) noexcept { return ModInt(lhs) /= rhs; }
    friend inline bool operator==(const ModInt &lhs, const ModInt &rhs) noexcept { return lhs.val == rhs.val; }
    friend inline bool operator!=(const ModInt &lhs, const ModInt &rhs) noexcept { return lhs.val != rhs.val; }
    friend inline std::istream &operator>>(std::istream &is, ModInt &x) noexcept {
        is >> x.val;
        x.normalize();
        return is;
    }
    friend inline std::ostream &operator<<(std::ostream &os, const ModInt &x) noexcept { return os << x.val; }
};

using mint = ModInt<MOD>;

void solve(){
    long long A, B, K;
    cin >> A >> B >> K;

    if(A >= 0 && B >= 0){
        if(B <= 1){
            mint ans = A * K;
            cout << ans << endl;
            return;
        }
        mint ans = A;
        ans *= mint(B).pow(K - 1);
        cout << ans << endl;
    }else if(A >= 0 && B < 0){
        if(B == -1){
            mint ans = A * K;
            cout << ans << endl;
            return;
        }
        mint ans = A * (K % 2 == 0 ? 2 : 1);
        ans *= mint(B).pow(((K - 1) / 2) * 2);
        cout << ans << endl;
    }else if(A < 0 && B >= 0){
        cout << 0 << endl;
    }else{
        // A < 0 && B < 0
        if(K == 1){
            cout << 0 << endl;
            return;
        }

        if(B == -1){
            mint ans = A * (K - 1);
            ans *= B;
            cout << ans << endl;
            return;
        }

        mint ans = A * (K % 2 == 0 ? 1 : 2);
        ans *= mint(B).pow(((K - 2) / 2) * 2 + 1);
        cout << ans << endl;
    }
}

int main(){
    int T; cin >> T;
    while(T--){
        solve();
    }
}