結果
問題 | No.2362 Inversion Number of Mod of Linear |
ユーザー |
|
提出日時 | 2024-12-22 00:48:09 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 756 ms / 2,000 ms |
コード長 | 4,264 bytes |
コンパイル時間 | 3,014 ms |
コンパイル使用メモリ | 251,596 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-22 00:48:17 |
合計ジャッジ時間 | 6,003 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 8 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define all(x) begin(x), end(x)#ifdef local#define safe cerr << __LINE__ << " line " << __LINE__ << " safe\n"#define debug(a...) debug_(#a, a)#define orange(a...) orange_(#a, a)template <typename ...T>void debug_(const char *s, T ...a) {cerr << "\e[1;32m(" << s << ") = (";int cnt = sizeof...(T);(..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));}template <typename I>void orange_(const char *s, I L, I R) {cerr << "\e[1;32m[ " << s << " ] = [ ";for (int f = 0; L != R; ++L)cerr << (f++ ? ", " : "") << *L;cerr << " ]\e[0m\n";}#else#define safe ((void)0)#define debug(...) safe#define orange(...) safe#endifnamespace {using lld = int64_t;using llu = uint64_t;using llf = long double;using u128 = llu;lld fdiv(lld a, lld b){ return a / b - (a % b && (a < 0) ^ (b < 0)); }lld cdiv(lld a, lld b){ return a / b + (a % b && (a < 0) ^ (b > 0)); }/* template <typename T>T brute(llu a, llu b, llu c, llu n, T U, T R) {T res;for (llu i = 1, l = 0; i <= n; i++, res = res * R)for (llu r = (a*i+b)/c; l < r; ++l) res = res * U;return res;} */template <typename T>T euclid(llu a, llu b, llu c, llu n, T U, T R) {if (!n) return T{};if (b >= c)return mpow(U, b / c) * euclid(a, b % c, c, n, U, R);if (a >= c)return euclid(a % c, b, c, n, U, mpow(U, a / c) * R);llu m = (u128(a) * n + b) / c;if (!m) return mpow(R, n);return mpow(R, (c - b - 1) / a) * U* euclid(c, (c - b - 1) % a, a, m - 1, R, U)* mpow(R, n - (u128(c) * m - b - 1) / a);}// time complexity is O(log max(a, b, c))// UUUU R UUUUU R ... UUU R 共 N 個 R,最後一個必是 R// 一直到第 k 個 R 前總共有 (ak+b)/c 個 U/*U -> cnt += 1, sum += iR -> i += 1*/template <int K>struct Mat : array<array<llu, K>, K> {friend Mat operator*(const Mat &a, const Mat &b) {Mat c;for (int i = 0; i < K; i++)for (int j = 0; j < K; j++)c[i][j] = 0;for (int i = 0; i < K; i++)for (int j = i; j < K; j++)for (int k = i; k <= j; k++)c[i][j] += a[i][k] * b[k][j];return c;}constexpr Mat() {for (int i = 0; i < K; i++)for (int j = 0; j < K; j++)(*this)[i][j] = (i == j);}};template <typename T>T mpow(T e, llu n) {T r;while (n) {if (n & 1) r = r * e;e = e * e;n >>= 1;}return r;}}signed main() {cin.tie(nullptr)->sync_with_stdio(false);// a = q_a * M + r_a// b = q_b * M + r_b//// floor((b - a) / M)// = (q_b - q_a) (if r_b >= r_a)// (q_b - q_a - 1) (if r_b < r_a)//// therefore ans// = \sum _ {i > j} floor((A_i - A_j) / M) - (floor(A_i / M) - floor(A_j / M))// = \sum _ {1 <= l < N} (N - l) * fdiv(l * X, M)// - \sum _ {0 <= i < N} i * fdiv(i * X + Y, M)// + \sum _ {0 <= j < N} (N - 1 - j) * fdiv(j * X + Y, M)int T;cin >> T;while (T--) {lld N, M, X, Y;cin >> N >> M >> X >> Y;llu ans = 0;// for (int i = 0; i < N; i++)// ans -= (N - i) * fdiv(i * X, M);// for (int i = 0; i < N; i++)// ans += (i * 2 - N + 1) * fdiv(i * X + Y, M);// ans += N * (N + 1) / 2;// for (int i = 1; i <= N; i++) {// ans += (0 - N - 1) * fdiv(i * X + (M - X), M);// }// for (int i = 1; i <= N; i++) {// ans += (0 * 2 - N - 1) * fdiv(i * X + Y - X + M, M);// }// cout << ans << '\n';// continue;debug(Y + (M - X));ans += N * (N + 1) / 2;// 1, (i), (U 加了幾次), (i) * (U 加了幾次), (\sum _ {1 <= j <= i} (j * (U 加了幾次)){Mat<5> U;U[0][2] = 1;U[1][3] = 1;Mat<5> R;R[0][1] = 1;R[2][3] = 1;R[2][4] = 1;R[3][4] = 1;auto m1 = euclid(X, 0 + (M - X), M, N, U, R);auto m2 = euclid(X, Y + (M - X), M, N, U, R);ans += m1[0][4];ans += m2[0][4] * 2;}// 1, (U 加了幾次), \sum _ {i} U 加了幾次{Mat<3> U;U[0][1] = 1;Mat<3> R;R[1][2] = 1;auto m1 = euclid(X, 0 + (M - X), M, N, U, R);auto m2 = euclid(X, Y + (M - X), M, N, U, R);ans -= (N + 1) * m1[0][2];ans -= (N + 1) * m2[0][2];}cout << ans << '\n';}}