test/yosupo/sum_of_floor_of_linear.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 12:11:12+09:00
• Problem: https://judge.yosupo.jp/problem/sum_of_floor_of_linear

Depends on

• 万能欧几里得 (src/Math/AllPurposeEuclid.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/sum_of_floor_of_linear
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include "src/Math/AllPurposeEuclid.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 using FST= FloorSumTable<long long, 0, 1>;
 FST::init();
 int T;
 cin >> T;
 while (T--) {
  long long N, M, A, B;
  cin >> N >> M >> A >> B;
  cout << FST::solve(N - 1, A, B, M, 0, 1)[0][1] << '\n';
 }
 return 0;
}

#line 1 "test/yosupo/sum_of_floor_of_linear.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/sum_of_floor_of_linear
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#line 2 "src/Math/AllPurposeEuclid.hpp"
#include <algorithm>
#include <array>
template <typename M> class AllPurposeEuclid {
 using Node= typename M::Node;
 using u64= unsigned long long;
 static inline Node pow(Node x, u64 e) {
  Node ret= M::ti();
  for (; e; e>>= 1, x= M::f(x, x))
   if (e & 1) ret= M::f(ret, x);
  return ret;
 }
 static Node rec(u64 n, u64 a, u64 b, u64 c, const Node &sU, const Node &sR) {
  if (!n) return M::ti();
  if (a >= c) return rec(n, a % c, b, c, sU, M::f(pow(sU, a / c), sR));
  u64 m= ((long double)a * n + b) / c;
  if (!m) return pow(sR, n);
  u64 cnt= n - u64(((long double)c * m - b - 1) / a);
  return M::f(M::f(pow(sR, (c - b - 1) / a), sU), M::f(rec(m - 1, c, (c - b - 1) % a, a, sR, sU), pow(sR, cnt)));
 }
public:
 static Node solve(u64 n, u64 a, u64 b, u64 c) { return M::f(pow(M::sU, b / c), rec(n, a, b % c, c, M::sU, M::sR)); }
};
template <typename int_t, int MXK1, int MXK2> struct FloorSumTable {
 static constexpr int MXK= std::max(MXK1, MXK2) + 1;
 static inline int_t C[MXK][MXK]= {}, pwX[MXK1 + 1]= {1}, pwY[MXK2 + 1]= {1};
 static inline int k1= MXK1, k2= MXK2;
 using u64= unsigned long long;
 struct Monoid {
  struct Node {
   int_t cntU= 0, cntR= 0, v[MXK1 + 1][MXK2 + 1]= {0};
  };
  static inline Node sU, sR;
  static Node ti() { return Node(); }
  static Node f(Node vl, const Node &vr) {
   for (int i= 0; i < k1; i++) pwX[i + 1]= pwX[i] * vl.cntR;
   for (int j= 0; j < k2; j++) pwY[j + 1]= pwY[j] * vl.cntU;
   vl.cntU+= vr.cntU, vl.cntR+= vr.cntR;
   for (int i= 0; i <= k1; i++)
    for (int j= 0; j <= k2; j++)
     for (int k= 0; k <= i; k++)
      for (int l= 0; l <= j; l++) vl.v[i][j]+= pwX[k] * pwY[l] * C[i][k] * C[j][l] * vr.v[i - k][j - l];
   return vl;
  }
 };
 static void init() {
  for (int i= 0; i < MXK; i++) C[i][0]= 1;
  for (int i= 1; i < MXK; i++)
   for (int j= 1; j <= i; j++) C[i][j]= C[i - 1][j] + C[i - 1][j - 1];
  Monoid::sU.cntU= Monoid::sR.cntR= 1;
  for (int i= 0; i <= k1; i++) Monoid::sR.v[i][0]= 1;
 }
 static auto solve(u64 n, u64 a, u64 b, u64 c, int k1_, int k2_) {
  k1= k1_, k2= k2_;
  auto tmp= AllPurposeEuclid<Monoid>::solve(n, a, b, c);
  std::array<std::array<int_t, MXK2 + 1>, MXK1 + 1> ret;
  for (int i= 0; i <= k1; i++)
   for (int j= 0; j <= k2; j++) ret[i][j]= tmp.v[i][j];
  int_t pw= 1, bs= double(b) / c;
  for (int j= 0; j <= k2; j++, pw*= bs) ret[0][j]+= pw;
  return ret;
 }
};
template <class R_t, R_t (*ro)(), R_t (*ri)()> struct RingFloorSum {
 using u64= unsigned long long;
 struct Monoid {
  struct Node {
   R_t u= ri(), r= ri(), v= ro();
  };
  static inline Node sU, sR;
  static Node ti() { return Node(); }
  static Node f(Node vl, const Node &vr) {
   vl.v+= vl.r * vr.v * vl.u, vl.u*= vr.u, vl.r*= vr.r;
   return vl;
  }
 };
 static R_t solve(u64 n, u64 a, u64 b, u64 c, const R_t &A, const R_t &B) {
  Monoid::sU= {B, ri(), ro()}, Monoid::sR= {ri(), A, A};
  return AllPurposeEuclid<Monoid>::solve(n, a, b, c).v;
 }
};
#line 6 "test/yosupo/sum_of_floor_of_linear.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 using FST= FloorSumTable<long long, 0, 1>;
 FST::init();
 int T;
 cin >> T;
 while (T--) {
  long long N, M, A, B;
  cin >> N >> M >> A >> B;
  cout << FST::solve(N - 1, A, B, M, 0, 1)[0][1] << '\n';
 }
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	example_00	AC	5 ms	4 MB
g++-13	random_00	AC	67 ms	4 MB
g++-13	random_01	AC	251 ms	4 MB
g++-13	random_02	AC	194 ms	4 MB
g++-13	random_03	AC	135 ms	4 MB
g++-13	random_04	AC	58 ms	4 MB
g++-13	small_00	AC	25 ms	4 MB
g++-13	small_01	AC	80 ms	4 MB
g++-13	small_02	AC	63 ms	4 MB
g++-13	small_03	AC	44 ms	4 MB
g++-13	small_04	AC	22 ms	4 MB
clang++-18	example_00	AC	5 ms	4 MB
clang++-18	random_00	AC	110 ms	4 MB
clang++-18	random_01	AC	420 ms	4 MB
clang++-18	random_02	AC	322 ms	4 MB
clang++-18	random_03	AC	220 ms	4 MB
clang++-18	random_04	AC	94 ms	4 MB
clang++-18	small_00	AC	36 ms	4 MB
clang++-18	small_01	AC	125 ms	4 MB
clang++-18	small_02	AC	97 ms	4 MB
clang++-18	small_03	AC	69 ms	4 MB
clang++-18	small_04	AC	31 ms	4 MB

Back to top page