結果

問題 No.3397 Max Weighted Floor of Linear
コンテスト
ユーザー Kude
提出日時 2025-12-04 01:22:55
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 408 ms / 2,000 ms
コード長 2,953 bytes
記録
コンパイル時間 3,551 ms
コンパイル使用メモリ 276,348 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-04 01:23:08
合計ジャッジ時間 11,344 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;

template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;

constexpr long long INF = 8002003004005006007;
struct M {
  ll sm, mx;
  static M unit() { return {0, -INF}; }
  friend M operator*(M a, M b) { return {a.sm + b.sm, max(a.mx, a.sm + b.mx)}; }
  M& operator*=(const M& rhs) {
    chmax(mx, sm + rhs.mx);
    sm += rhs.sm;
    return *this;
  }
};


// https://259-momone.hatenablog.com/entry/2025/04/28/232456
#include <type_traits>

template <typename U, typename... Args>
struct has_power_method {
private:
    template <typename V, typename... PowArgs>
    static auto check(int)
        -> decltype(std::declval<V>().power(std::declval<PowArgs>()...),
            std::true_type{});
    template <typename, typename...>
    static auto check(...) -> std::false_type;

public:
    static constexpr bool value = decltype(check<U, Args...>(0))::value;
};

#include <concepts>
#include <cassert>

template <typename Monoid, std::integral I>
auto monoid_pow(Monoid x, I exp, Monoid base = Monoid::unit()) {
    if constexpr (has_power_method<Monoid, I, Monoid>::value) {
        return x.power(exp, base);
    } else if constexpr (has_power_method<Monoid, I>::value) {
        return base * x.power(exp);
    } else {
        assert(exp >= 0);
        Monoid res{base};
        while (exp) {
            if (exp & 1) res *= x;
            x *= x;
            exp >>= 1;
        }
        return res;
    }
}

using I = ll;
using Monoid = M;
using SafeInteger = __uint128_t;
// template <std::integral I, class Monoid, std::integral SafeInteger = __uint128_t>
Monoid floor_prod(I n, I m, I a, I b, Monoid x, Monoid y) {
    Monoid prefix_prod{Monoid::unit()}, suffix_prod{Monoid::unit()};

    while (true) {
        x = monoid_pow(y, a / m, x);
        a %= m;

        prefix_prod = monoid_pow(y, b / m, prefix_prod);
        b %= m;

        const auto y_max{static_cast<SafeInteger>(a) * n + b};
        if (y_max < m)
            return monoid_pow(x, n, prefix_prod) * suffix_prod;

        suffix_prod = monoid_pow(x, static_cast<I>(y_max % m) / a, y) * suffix_prod;
        n = static_cast<I>(y_max / m) - 1;
        std::swap(a, m);
        std::swap(x, y);
        b = m + a - b - 1;
    }
}

using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    ll n, m, a, b, c, d;
    cin >> n >> m >> a >> b >> c >> d;
    cout << floor_prod(n, m, c, d, M{a, 0}, M{b, -INF}).mx << '\n';
  }
}
0