結果
問題 | No.2875 What is My Rank? |
ユーザー |
![]() |
提出日時 | 2024-09-12 12:50:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 113 ms / 2,000 ms |
コード長 | 1,370 bytes |
コンパイル時間 | 2,026 ms |
コンパイル使用メモリ | 203,180 KB |
最終ジャッジ日時 | 2025-02-24 06:43:34 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> using ll = std::int64_t; std::tuple<ll, ll, ll> extgcd(ll a, ll b){ ll s1 = 1, t1 = 0, s2 = 0, t2 = 1; while(b != 0){ std::tie(s1, t1, s2, t2) = std::make_tuple(s2, t2, s1 - (a / b) * s2, t1 - (a / b) * t2); std::tie(a, b) = std::make_tuple(b, a % b); } return std::make_tuple(s1, t1, a); } ll inv(ll a, ll n){ ll inv_a; std::tie(inv_a, std::ignore, std::ignore) = extgcd(a, n); inv_a %= n; if(inv_a < 0){inv_a += n;} return inv_a; } int main(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); int N; std::cin >> N; std::vector<int> l(N), r(N); for(int i=0;i<N;i++){ std::cin >> l[i] >> r[i]; } constexpr ll MOD = 998'244'353; ll res = 1; ll inv_n1 = inv(r[0] - l[0] + 1, MOD); for(int i=1;i<N;i++){ ll inv_ni = inv(r[i] - l[i] + 1, MOD); int l1 = std::max(l[i], r[0] + 1); if(l1 <= r[i]){ res += 1ll * (r[i] - l1 + 1) * inv_ni % MOD; if(res >= MOD){res -= MOD;} } int l2 = std::max(l[i], l[0]); int r2 = std::min(r[i], r[0]); if(l2 <= r2){ res += (1ll * (r2 - l[0] + l2 - l[0]) * (r2 - l2 + 1) / 2) % MOD * inv_n1 % MOD * inv_ni % MOD; if(res >= MOD){res -= MOD;} } } std::cout << res << std::endl; }