結果
問題 | No.2362 Inversion Number of Mod of Linear |
ユーザー |
👑 ![]() |
提出日時 | 2023-06-24 01:18:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 295 ms / 2,000 ms |
コード長 | 3,053 bytes |
コンパイル時間 | 952 ms |
コンパイル使用メモリ | 86,568 KB |
最終ジャッジ日時 | 2025-02-15 01:49:02 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 8 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <algorithm>#include <atcoder/modint>#include <atcoder/math>using namespace std;using i32 = int;using u32 = unsigned int;using i64 = long long;using u64 = unsigned long long;#define rep(i,n) for(int i=0; i<(int)(n); i++)const i64 INF = 1001001001001001001;using Modint = atcoder::static_modint<998244353>;template<class modint>modint TriangleSumTimesLinear(long long n,long long a,long long b,modint c,modint d,modint e){if(n <= 0) return modint(0);if(a < b) return TriangleSumTimesLinear(n, b, a, d, c, e);modint res = 0;static const modint inv2 = modint(2).inv();static const modint inv6 = modint(6).inv();while(true){if(n <= 0) break;if(a < b){ swap(a,b); swap(c,d); continue; }// eliminate trianglei64 maxi = (n - 1) / a + 1;i64 t = min<i64>(a / b, (n - 1) % a / b + 1);res += c * maxi * (maxi-1) * (maxi+1) * inv6 * t;res -= d * maxi * (maxi-1) * (maxi+1) * inv6 * t * (t-1) * inv2;res += d * maxi * maxi * (maxi+1) * inv2 * t * (t-1) * inv2;res += d * maxi * (maxi-1) * (maxi+1) * inv6 * t;res += e * maxi * (maxi+1) * inv2 * t;n -= maxi * b * t;a -= b * t;c -= d * t;e += d * maxi * t;}return res;}template<class modint>modint AKindOfFloorSum(long long n,long long m,long long a,long long b){long long q = b / m;modint tmp = modint(n) * modint(n-1) / 2 * q;b -= q * m;long long newn = a * (n-1) + b - (m-1);if(newn <= 0) return 0;return tmp + TriangleSumTimesLinear<modint>(newn, a, m, -1, 0, n-1);}template<class modint>modint BKindOfFloorSum(long long n,long long m,long long a,long long b){long long q = b / m;modint tmp = modint(n) * q;b -= q * m;long long newn = a * (n-1) + b - (m-1);if(newn <= 0) return 0;return tmp + TriangleSumTimesLinear<modint>(newn, a, m, 0, 0, 1);}using Modint1 = atcoder::static_modint<1000000007>;using Modint2 = atcoder::static_modint<1000000009>;template<class modint>modint find_mod(long long N,long long M,long long X,long long Y){modint x1 = AKindOfFloorSum<modint>(N, M, X, Y) * 2;modint x2 = BKindOfFloorSum<modint>(N, M, X, Y) * (1-N);modint x3 = AKindOfFloorSum<modint>(N, M, X, 0);modint x4 = BKindOfFloorSum<modint>(N, M, X, 0) * (-N);return x1 + x2 + x3 + x4;}int main(){int T; cin >> T;rep(t,T){long long N,M,X,Y; cin >> N >> M >> X >> Y;auto x1 = find_mod<Modint1>(N, M, X, Y);auto x2 = find_mod<Modint2>(N, M, X, Y);long long ans = atcoder::crt({ x1.val(), x2.val() }, { x1.mod(), x2.mod() }).first;cout << ans << '\n';}return 0;}struct ios_do_not_sync{ios_do_not_sync(){ios::sync_with_stdio(false);cin.tie(nullptr);}} ios_do_not_sync_instance;