結果
問題 |
No.2336 Do you like typical problems?
|
ユーザー |
|
提出日時 | 2023-06-02 22:22:43 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 355 ms / 2,000 ms |
コード長 | 1,213 bytes |
コンパイル時間 | 2,093 ms |
コンパイル使用メモリ | 175,512 KB |
実行使用メモリ | 56,648 KB |
最終ジャッジ日時 | 2024-12-28 19:19:01 |
合計ジャッジ時間 | 5,754 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; const int mod=998244353; pair<int,int>a[N]; vector<int>f[N<<2],g[N<<2]; int n; int ksm(int x,int y){ int ans=1; for (;y;y>>=1,x=1ll*x*x%mod) if (y&1) ans=1ll*ans*x%mod; return ans; } int main(){ scanf("%d",&n); vector<int>w; for (int i=1;i<=n;i++) { scanf("%d%d",&a[i].first,&a[i].second); a[i].second++; w.push_back(a[i].first); w.push_back(a[i].second); } sort(w.begin(),w.end()); int m=unique(w.begin(),w.end())-w.begin(); w.resize(m); for (int i=1;i<=n;i++){ f[lower_bound(w.begin(),w.end(),a[i].first)-w.begin()].push_back(ksm(a[i].second-a[i].first,mod-2)); g[lower_bound(w.begin(),w.end(),a[i].second)-w.begin()].push_back(ksm(a[i].second-a[i].first,mod-2)); } int x=0,x2=0; int ans=1ll*n*(n-1)/2%mod; int inv2=ksm(2,mod-2); for (int i=0;i<m-1;i++){ for (int j=0;j<f[i].size();j++) x=(x+f[i][j])%mod,x2=(x2+1ll*f[i][j]*f[i][j]%mod)%mod; for (int j=0;j<g[i].size();j++) x=(x-g[i][j]+mod)%mod,x2=(x2-1ll*g[i][j]*g[i][j]%mod+mod)%mod; ans=(ans-1ll*(1ll*x*x%mod-x2+mod)%mod*inv2%mod*(w[i+1]-w[i])%mod+mod)%mod; } for (int i=1;i<=n;i++) ans=1ll*ans*i%mod; ans=1ll*ans*ksm(2,mod-2)%mod; printf("%d\n",ans); }