結果

問題 No.3462 Buttons
コンテスト
ユーザー おのせ
提出日時 2026-02-10 12:06:48
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,586 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,093 ms
コンパイル使用メモリ 279,432 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-02-28 13:06:02
合計ジャッジ時間 17,608 ms
ジャッジサーバーID
（参考情報） 		judge7 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
#include <iostream>
#include <cmath>
using namespace std;
using namespace atcoder;
using ll = long long;
using lb = long double;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vb = vector<bool>;
using vvll = vector<vector<ll>>;
using vP = vector<P>;
using Graph = vector<vector<ll>>;
using WGraph = vector<vector<pair<ll, ll>>>; // コスト、頂点番号の順
using mint = modint998244353;
//using mint = long double;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
mt19937_64 rng(58);
long double PI = 3.14159265358979;
const ll LLMAX = 9223372036854775807;
const ll INF = 1e18;
vector<ll> di = {-1, 0, 1, 0}; // 上左下右
vector<ll> dj = {0, -1, 0, 1};
template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

void solve() {
    ll a, b, k;
    cin >> a >> b >> k;

    mint ans = 0;

    if (a == 0) {
        cout << 0 << endl;
        return;
    }    
    if (b == 0) {
        if (a <= 0) {
            cout << ans.val() << endl;
            return;
        }
        else {
            ans = (mint)a * (mint)k;
            cout << ans.val() << endl;
            return;
        }
    }
    if (abs(b) == 1) {
        ans = (mint)a * (mint)k;
        cout << ans.val() << endl;
        return;
    }


    ll A = abs(a);
    ll B = abs(b);
    ll shold = 0;
    if (A % (B - 1) == 0) shold = A / (B - 1);
    else shold = A / (B - 1) + 1;
    shold += (A - shold % A);
    if (k - shold / A < 0) {
        ans = (mint)a * (mint)k;
        cout << ans.val() << endl;
        return;
    } 
    k -= shold / A;
    

    ll cnt = 0;
    if (a < 0) cnt++;
    if (b < 0) cnt += k;
    
    vector<mint> Rb(40);
    Rb[0] = B;
    rep (i, 39) Rb[i + 1] = Rb[i] * Rb[i];
    auto power = [&](ll x) {
        mint res = 1;
        rep (i, 40) {
            if ((x >> i) & 1) res *= Rb[i]; // ansにしてた
        }
        return res;
    };
    if (cnt % 2 == 0) {
        ans = (mint)shold * power(k);
    }
    else {
        ll sh1 = 0, sh2 = 0;
        if (k != 0) sh1 = shold + A; // *にしてた
        if (shold != 0) sh2 = (shold - A) * B * B;
        //cout << shold << ", " << sh1 << ", " << sh2 << ", " << k << endl;
        if (sh1 > sh2) ans = (mint)sh1 * power(k - 1);
        else ans = (mint)sh2 * power(k - 1);
    }

    cout << ans.val() << endl;
}

int main() {
    ll t;
    cin >> t;
    rep (ti, t) solve();
    return 0;
}
0