結果

問題 No.2744 Power! or +1
コンテスト
ユーザー zatsu308
提出日時 2024-04-20 14:40:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 904 ms / 3,000 ms
コード長 1,977 bytes
コンパイル時間 2,460 ms
コンパイル使用メモリ 207,132 KB
最終ジャッジ日時 2025-02-21 06:38:54
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr ll mod = 998244353;

template<ll mod>
struct Mint {
  using M=Mint; ll v;
  M& put(ll x) { v=(x<mod)?x:x-mod; return *this; }
  Mint(ll x=0) { put(x%mod+mod); }
  M operator+(M m) {return M().put(v+m.v);}
  M operator-(M m) {return M().put(v+mod-m.v);}
  M operator*(M m) {return M().put(v*m.v%mod);}
  M operator/(M m) {return M().put(v*m.inv().v%mod);}
// BEGIN IGNORE
  M operator+=(M m) { return put(v+m.v); }
  M operator-=(M m) { return put(v+mod-m.v); }
  M operator*=(M m) { return put(v*m.v%mod); }
  M operator/=(M m) { return put(v*m.inv().v%mod); }
// END IGNORE
  bool operator==(M m) { return v==m.v; }
  M pow(ll m) const {
    M x=v, res=1;
    while (m) {
      if (m&1) res=res*x;
      x=x*x; m>>=1;
    }
    return res;
  }
  M inv() { return pow(mod-2); }
};

using mint = Mint<mod>;


int main(){

  cin.tie(0);
  cin.sync_with_stdio(0);

  ll n, a, b, c;
  cin >> n >> a >> b >> c;
  vector<ll> dp(n + 1, 1e18);

  dp[1] = 0;
  vector<vector<pair<int,ll>>> edges(n + 1);

  ll y = 1;
  ll y2 = 1;
  for(int x = 1; x < n; ++x){
    edges[x].emplace_back((x + 1) % n, a);
    if(x == n - 1)edges[x].emplace_back(n + 1, a);
    ll xx2 = x;
    ll bb = b, xx = x;
    while(bb <= n * a){
      bb *= b;
      xx = xx * x % n;
      xx2 = min(n, xx2 * x);
      if(xx2 == n)edges[x].emplace_back(xx2, bb);
      edges[x].emplace_back(xx, bb);
    }
    y2 = min(y2 * x, n);
    y = y * x % n;
    if(y2 == n)edges[x].emplace_back(y2, c);
    edges[x].emplace_back(y, c);
  }
  priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> que;
  que.emplace(0, 1);
  while(!que.empty()){
    auto [cost, x] = que.top();
    que.pop();
    if(cost != dp[x])continue;
    for(auto [y, cost2] : edges[x]){
      if(dp[y] > cost + cost2){
        dp[y] = cost + cost2;
        que.emplace(dp[y], y);
      }
    }
  }
  dp[0] = min(dp[0], dp.back() + c);
  cout << dp[0] << endl;
}
0