#1150224 (C++23) No.3462 Buttons

• 問題: No.3462 Buttons
• ユーザー: syndrome
• 提出日時: 2026-02-28 14:28:42
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 568 ms / 2,000 ms
• コード長: 3,855 bytes
• コンパイル時間: 4,326 ms
• コンパイル使用メモリ: 357,256 KB
• 実行使用メモリ: 7,848 KB
• 最終ジャッジ日時: 2026-02-28 14:29:01
• 合計ジャッジ時間: 14,938 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

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

ソースコード

// (◕ᴗ◕✿)

// #pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define srep(i, s, n) for (ll i = s; i < (n); i++)
#define len(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
template<typename T> using vvv = vv<vc<T>>;
using vi = vc<int>;using vvi = vv<int>; using vvvi = vv<vi>;
using ll = long long;using vl = vc<ll>;using vvl = vv<ll>; using vvvl = vv<vl>;
using ld = long double; using vld = vc<ld>; using vvld = vc<vld>; using vvvld = vc<vvld>;
using uint = unsigned int;
using ull = unsigned long long;
const ld pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
// const ll mod = 1000000007;
const ll mod = 998244353;
inline bool inside(ll y, ll x, ll H, ll W) {return 0 <= (y) and (y) < (H) and 0 <= (x) and (x) < (W); }

#define debug(var) do { cerr << #var << " :\n"; view(var); } while(0)
template<typename T>void view(const T& e) {cerr << e;}
template<typename T1, typename T2>void view(const pair<T1, T2>& p) {cerr << "{" << p.first << ", " << p.second << "}";}
template<typename T>void view(const vc<T>& v) {for (const auto& e : v) {view(e);cerr << " ";} cerr << endl;}
template<typename T>void view(const vv<T>& vv) {for (const auto& v : vv) {view(v);} cerr << endl;}
template<typename T>void view(const set<T>& s) {for (const auto& e : s) {view(e);cerr << " ";} cerr << endl;}
template<typename T>void view(const multiset<T>& s) {for (const auto& e : s) {view(e);cerr << " ";} cerr << endl;}
template<typename T>void view(const unordered_set<T>& s) {for (const auto& e : s) {view(e);cerr << " ";} cerr << endl;}
template<typename T1, typename T2>void view(const map<T1, T2>& mp){for (const auto& e : mp) {view(e);cerr << " ";} cerr << endl;}

ll pow_mod(ll a, ll d, ll m){
    ll ret = 1;
    while (d > 0){
        if (d & 1){
            ret *= a;
            ret %= m;
        }
        a = a * a % m;
        d >>= 1;
    }
    return ret;
}

void solve(){
    ll A, B, K; cin >> A >> B >> K;
    if (abs(B) <= 1 || A == 0){
        if (A >= 0){
            cout << A * K % mod << endl;
        }else{
            if (B == -1){
                cout << (-A * (K - 1) % mod) << endl;
            }else cout << 0 << endl;
        }
        return;
    }
    if (A < 0 && B < 0){ // b : odd
        if (K == 1) cout << 0 << endl;
        else if (K % 2){
            cout << pow_mod(-B, K - 2, mod) * 2 * (-A) % mod << endl;
        }else{
            cout << pow_mod(-B, K - 1, mod) * (-A) % mod << endl;
        }
    }
    if (A < 0 && B > 0){
        cout << 0 << endl;
    }
    if (A > 0 && B < 0){
        if (K <= 2) cout << K * A % mod << endl;
        else if (K % 2){
            cout << pow_mod(-B, K - 1, mod) * A % mod << endl;
        }else{
            cout << pow_mod(-B, K - 2, mod) * 2 * A % mod << endl;
        }
        // for (int a = (K % 2);a <= K; a += 2){
        //     ll sm = A * a;
        //     if (1 + 2 * A / sm < B * B){
        //         ll ans = sm % mod * pow_mod(B, K - a, mod) % mod;
        //         cout << ans << endl;
        //         return;
        //     }
        // }
    }
    if (A > 0 && B > 0){
        cout << pow_mod(B, K - 1, mod) * A % mod << endl;
        // a < 1 / (B - 1)
        // for (int a = 1;; a ++){
        //     ll sm = A * a;
        //     if (sm + A < sm * B){
        //         ll ans = sm % mod * pow_mod(B, K - a, mod) % mod;
        //         cout << ans << endl;
        //         return;
        //     }
        // }
    }
    // cout << 0 << endl;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) solve();
}