結果

問題 No.3462 Buttons
コンテスト
ユーザー MM
提出日時 2026-02-28 15:57:45
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,758 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,206 ms
コンパイル使用メモリ 378,424 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-02-28 15:58:04
合計ジャッジ時間 18,086 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#include<atcoder/all>
#define chmin(x,y) (x) = min((x),(y))
#define chmax(x,y) (x) = max((x),(y))
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define vec vector
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back 
#define eb emplace_back

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
const ll mod = 998244353;
using mint = modint998244353;
const vector<int> dx = {1,0,-1,0}, dy = {0,1,0,-1};
// using Graph = vector<vector<pair<int,ll>>>;
using Graph = vector<vector<int>>;

ll ceill(ll x, ll y){
  ll res = x / y;
  if(x % y != 0) res++;
  return res;
}

mint f(ll X, ll A, ll B, ll K){
  // press A until score becomes ceil(A/B-1),
  // which is the solution of Bx < x + A,
  // then press B
  if(B == 1) return (mint)A * K;

  ll push_A = min(K,max(0LL,ceill(ceill(A,(B-1))-X, A)));
  // cout << push_A << endl;
  mint res = (mint)X + A * push_A * ((mint)B).pow(K-push_A);
  return res;
}

int main(){
  // input
  int T;
  cin >> T;
  while(T--){
    ll A,B,K;
    cin >> A >> B >> K;
    if(A == 0){
      //  corner case
      cout << 0 << endl;
    }
    else if(A > 0){
      // A > 0 && B > 0
      if(B > 1){
        cout << f(0,A,B,K).val() << endl;
      }
      else cout << (A * K) % mod << endl;
    }
    else if(A < 0){
      if(B >= 0 || K == 1) cout << 0 << endl;
      else{
        // most crazy
        // "(K-n) * A -> n * B" where n is odd
        // K >= 2 is assured
        if(K % 2)
          cout << f(2*A*B,-2*A,B*B,K/2-1).val() << endl;
        // ll ini = A * B * (K % 2 == 0 ? 2 : 1);
        else
          cout << f(A*B,-2*A,B*B,K/2-1).val() << endl;
      }
    }
  }
  
  // solve
  
  // output
  
}
0