結果
問題 | No.2875 What is My Rank? |
ユーザー | tottoripaper |
提出日時 | 2024-09-12 12:50:22 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 117 ms / 2,000 ms |
コード長 | 1,370 bytes |
コンパイル時間 | 2,330 ms |
コンパイル使用メモリ | 213,392 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-12 12:50:28 |
合計ジャッジ時間 | 5,944 ms |
ジャッジサーバーID (参考情報) |
judge1 / 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;}