2022 ICPC Asia Taiwan Online Programming Contest
===
比賽鏈結
---
https://codeforces.com/gym/103990/
比賽影片
---
沒有ㄚ QAQ
記分板
---
題解
---
### A. AibohphobiA(待補)
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### B. Balanced Seesaw Array
---
#### 題目摘要
讓$\,A=[a_1,a_2,\dots,a_m]$，定義一個陣列為平衡翹翹板陣列，如果存在一個$\,k\,$在$\,1\,$和$\,m\,$之間$\sum_{i=1}^m(i-k) a_i = 0$
$Q\,$筆操作
* $1\; \ell\; r \; x$ 代表 $a_\ell,a_{\ell+1},\dots,a_r$ 增加 $x$
* $2\; \ell\; r\; x$ 代表 $a_\ell,a_{\ell+1},\dots,a_r$ 改為 $x$
* $3\; \ell\; r$ 輸出 $[a_\ell,a_{\ell+1},\dots,a_r]$ 是否為平衡翹翹板陣列
#### 想法
數式展開 $\sum_{i=1}^m(i-k)a_i=0$
$\sum_{i=1}^mia_i= k\sum_{i=1}^ma_i$
$k= \frac{\sum_{i=1}^mia_i}{\sum_{i=1}^ma_i}$
因此只要用線段樹好好維護$ia_i$及$a_i$的區間和，再判斷k有沒有符合條件就好。
在維護$ia_i$時可以考慮維護一個等差數列，細節的部分好好處理就好
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; ++a)
#define ll long long
#define pii pair<int, int>
#define lpos pos << 1
#define rpos pos << 1 | 1
const int MAXN = 1e5 + 5;
#define int long long
struct node {
ll val, pre, tag = 10001, st, inc;
void update(int, int, int, ll, ll);
} tree[MAXN << 2];
node operator + (node a, node b) {
return {a.val + b.val, a.pre + b.pre, 10001, 0, 0};
}
ll a[MAXN], p[MAXN];
void node::update(int l, int r, int lval, ll d, ll v) {
if (v != 10001) {
val = v * (r - l + 1);
pre = v * (l + r) * (r - l + 1) / 2;
st = inc = 0;
tag = v;
}
val += d * (r - l + 1);
pre += (2 * lval + (r - l) * d) * (r - l + 1) / 2;
st += lval;
inc += d;
}
void pull(int pos) {
tree[pos] = tree[lpos] + tree[rpos];
}
void build(int pos, int l, int r) {
if (l == r) {
tree[pos] = {a[l], p[l], 10001, 0, 0};
return;
}
int mid = l + r >> 1;
build(lpos, l, mid);
build(rpos, mid + 1, r);
pull(pos);
}
void push(int pos, int l, int r) {
int mid = l + r >> 1;
tree[lpos].update(l, mid, 0, 0, tree[pos].tag);
tree[rpos].update(mid + 1, r, 0, 0, tree[pos].tag);
tree[pos].tag = 10001;
tree[lpos].update(l, mid, tree[pos].st, tree[pos].inc, 10001);
tree[rpos].update(mid + 1, r, tree[pos].st + (mid + 1 - l) * tree[pos].inc, tree[pos].inc, 10001);
tree[pos].st = tree[pos].inc = 0;
}
void mod(int pos, int l, int r, int ml, int mr, ll val, int d, int t) {
if (ml <= l && mr >= r) {
if (t == 1) {
tree[pos].update(l, r, val, d, 10001);
} else {
tree[pos].update(l, r, 0, 0, d);
}
return;
}
push(pos, l, r);
int mid = l + r >> 1;
if (ml <= mid) mod(lpos, l, mid, ml, mr, val, d, t);
if (mr > mid) mod(rpos, mid + 1, r, ml, mr, (mid + 1) * d, d, t);
pull(pos);
}
node query(int pos, int l, int r, int ql, int qr) {
if (ql <= l && qr >= r) {
return tree[pos];
}
push(pos, l, r);
int mid = l + r >> 1;
node res = {0, 0, 0, 0, 0};
if (ql <= mid) res = res + query(lpos, l, mid, ql, qr);
if (qr > mid) res = res + query(rpos, mid + 1, r, ql, qr);
return res;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, q; cin >> n >> q;
rep (i, 1, n + 1) cin >> a[i];
rep (i, 1, n + 1) p[i] = a[i] * i;
build(1, 1, n);
while (q--) {
int t, l, r; cin >> t >> l >> r;
if (t == 3) {
node tmp = query(1, 1, n, l, r);
ll val = tmp.val, pre = tmp.pre;
pre -= val * (l - 1);
// cout << pre << ' ' << val << '\n';
if (val == 0) {
if (pre == 0) {
cout << "Yes\n";
} else {
cout << "No\n";
}
} else if (pre % val != 0) {
cout << "No\n";
} else {
ll k = pre / val;
if (k < 1 || k > r - l + 1) cout << "No\n";
else cout << "Yes\n";
}
} else {
int x; cin >> x;
mod(1, 1, n, l, r, l * x, x, t);
}
}
}
```
:::
### C. Correct
---
#### 題目摘要
9:00開始的比賽，Charlie 在$HH, MM$時一發AC第一題，問他們penalty為多少
#### 想法
$(Hours - 9) \times 60 + Minutes$
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; ++a)
#define ll long long
#define pii pair<int, int>
int a, b;
int main() {
cin >> a >> b;
cout << (a-9)*60+b;
}
```
:::
### D. Distance and Tree
---
#### 題目摘要
一個圓上有$n$個點，每點有各自的深度，要連邊並且邊邊不相交，若能不能連成一顆樹。若能，輸出所有邊，否則輸出-1
#### 想法
對於一個點，如果他跟另一個點連線，那麼他的左邊跟右邊必定無法相連，換句話說，你沒辦法跨過一個已經被連接的點連他的另一邊，所以從深度比較高的搜左右邊最近被連接過的點是不是自己的深度-1，是的話就連起來，不然就代表沒辦法連，開頭記得把1先接好
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
const int N=100005;
vector<int> v[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i=1;i<=n;i++){
int d;
cin >> d;
v[d].push_back(i);
}
if (v[0].size()!=1){
cout << -1 << '\n';
exit(0);
}
map<int, int> mp;
mp[v[0][0]]=0;
bool phlag=1;
vector<pair<int, int>> ans;
for(int i=1;i<n;i++){
for(auto pos:v[i]){
auto it=mp.upper_bound(pos);
if (it!=mp.end()){
if (it->S==i-1){
ans.push_back({it->F, pos});
continue;
}
}else{
it=mp.begin();
if (it->S==i-1){
ans.push_back({it->F, pos});
continue;
}
}
if (it!=mp.begin()){
it=prev(it);
if (it->S==i-1){
ans.push_back({it->F, pos});
continue;
}
}else{
it=prev(mp.end());
if (it->S==i-1){
ans.push_back({it->F, pos});
continue;
}
}
}
for(auto pos:v[i]) mp[pos]=i;
}
if (ans.size()!=n-1) phlag=0;
if (phlag){
for(auto p:ans){
cout << p.first << ' ' << p.second << '\n';
}
}else{
cout << -1 << '\n';
}
}
```
:::
### E. Etched Emerald Orbs
---
#### 題目摘要
找到一組$(x,\, y) \ {(x < y)}$符合：
$\frac{2}{k} = \frac{1}{x} + \frac{1}{y} \ (3\le k \le 4\times 10^{18})$
如有多組解輸出$\,x + y \,$最小的一組
#### 想法
炸柿子
$\ \ \ \ \ \ \frac{2}{k} = \frac{1}{x} + \frac{1}{y}$
$\Rightarrow 2xy=kx+ky$
$\Rightarrow 4xy-kx-ky=0$
$\Rightarrow 4xy-kx-ky+k^2=k^2$
$\Rightarrow k^2=(2x-k)(2y-k)!!!$
會發現我們只要將$k^2$的所有因數枚舉過一遍就能找出解
$k^2$的因數可以利用先找$\, k \,$的所有因數來枚舉出來
因數分解的部分則可使用Pollard's Rho演算法
注意要__int128
複雜度應該還行
:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second
pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }
#define lpos pos << 1
#define rpos pos << 1 | 1
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = __int128(res) * x % mod; x = __int128(x) * x % mod; exp >>= 1;} return res; }
bool Miller_Rabin(ll n) {
const int lim = 10;
if (n < 3 || n % 2 == 0) return n == 2;
if (n % 3 == 0) return n == 3;
ll d = n - 1, t = 0;
while (d & 1 ^ 1) d >>= 1, t++;
rep (i, 0, lim) {
ll x = rng() % (n - 3) + 2, val = fpow(x, d, n);
if (val == 1) continue;
int s = 0;
while (s < t) {
if (val == n - 1) break;
val = __int128(val) * val % n;
s++;
}
if (s == t) return false;
}
return true;
}
ll Pollard_Rho(ll n) {
ll c = rng() % (n - 1) + 1;
auto calc = [&](ll x) -> ll {
return (__int128(x) * x + c) % n;
};
ll s = 0, t = 0;
ll val = 1;
for (int goal = 1;; goal <<= 1, s = t, val = 1) {
rep (step, 1, goal + 1) {
t = calc(t);
val = __int128(val) * abs(s - t) % n;
if (val == 0) return n;
if (step % 127 == 0) {
ll d = __gcd(val, n);
if (d > 1) return d;
}
}
ll d = __gcd(val, n);
if (d > 1) return d;
}
}
void print(__int128 x) {
if (x < 0) {
x = -x;
putchar('-');
}
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}
void solve() {
ll k; cin >> k;
ll tmp = k;
vector<pll> prime;
auto fac = [&](auto self, ll x) -> void {
if (x < 2) return;
if (Miller_Rabin(x)) {
prime.pb({x, 0});
while (tmp % x == 0) {
prime.back().S++;
tmp /= x;
}
return;
}
ll p = x;
while (p >= x) p = Pollard_Rho(x);
while (x % p == 0) x /= p;
self(self, p), self(self, x);
};
fac(fac, k);
vector<ll> div;
auto gen_div = [&](auto self, int d, ll cur) -> void {
if (d == prime.size()) {
div.pb(cur);
return;
}
self(self, d + 1, cur);
rep (i, 1, prime[d].S + 1) {
cur *= prime[d].F;
self(self, d + 1, cur);
}
};
gen_div(gen_div, 0, 1);
// (2x - k) * (2y - k) = k ^ 2
sort(all(div));
// cout << div;
__int128 mx = __int128(1) << 126, a, b;
int sz = div.size();
rep (i, 0, sz) {
rep (j, 0, i + 1) {
ll x = div[i], y = div[j];
__int128 mul = __int128(x) * y;
if (mul >= k) break;
__int128 mul2 = __int128(k) * k / mul;
if (((mul + k) & 1) || ((mul2 + k) & 1)) continue;
mul = (mul + k) / 2, mul2 = (mul2 + k) / 2;
if (mx > mul + mul2) {
a = mul, b = mul2;
mx = mul + mul2;
}
}
}
print(a);
putchar(' ');
print(b);
}
int main() {
ZTMYACANESOCUTE;
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
```
:::
### F. Finalists
---
#### 題目摘要
題序超長自己看，給六個國家的很多分數，給你一個公式算出每個國家的分數，然後按照排名分配名額，問台灣拿幾個名額
#### 想法
他有浮點數所以開long double，然後用簡單數學
(每個人都有=$\frac{total}{6}$,多拿=$\frac{total \% 6}{排名}$)算一下名額
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; ++a)
#define ll long long
#define pii pair<int, int>
long double ru, rt, pu, pt, f;
int n;
long double site_score;
int main() {
cin >> n;
string s;
int tai;
vector<pair<long double, int>> c;
rep(i,0,6){
cin >> s >> pt >> pu >> rt >> ru >> f;
site_score = 0.56f*ru+0.24f*rt+0.14f*pu+0.06f*pt+0.3f*f;
if(s == "Taiwan") tai = i;
c.push_back({-site_score,i});
}
sort(c.begin(),c.end());
rep(i,0,6){
if(c[i].second == tai){
cout << n/6+(n%6)/(i+1);
}
}
}
```
:::
### G. Geekflix
---
#### 題目摘要
有$n$個直播，每看一個直播拿到點數，第$i$個直播看第$k$次能拿到的點數為$\, \max(a_i-(k-1)b_i, \; 0)$。你有三種操作，往前一台轉(1會到$n$)、往後一台轉($n$會到1)以及播放目前的直播，你會從第1場直播開始，問你做$m$個操作後最多能有多少點數
#### 想法
相信聰明的讀者一看到這題$n$的大小，就能馬上看出這是複雜度為$O(n^2m\log m)$的枚舉區間題了。對於每個區間，只要先算出最少需要幾個操作才能讓區間內所有直播都被轉到，剩下再用pq去維護最大的點數就好
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=205;
int a[N<<1], b[N<<1];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i=0;i<n;i++){
cin >> a[i];
a[i+n]=a[i];
}
for(int i=0;i<n;i++){
cin >> b[i];
b[i+n]=b[i];
}
ll ans=0;
for(int r=0;r<(n<<1);r++){
for(int l=max(0, r-n+1);l<=min(n-1, r);l++){
int t=0;
if (0<=l&&r<=n){
t=min(r, n-l);
}else{
t+=r-l;
t+=min(r-n, n-l);
}
t=m-t;
priority_queue<pair<int, int>> pq;
for(int k=l;k<=r;k++) pq.push({a[k], k});
ll res=0;
while((t>0)&&(!pq.empty())){
auto [val, idx]=pq.top();
pq.pop();
if (val==0) break;
res+=val;
val-=b[idx];
pq.push({max(0, val), idx});
t--;
}
ans=max(ans, res);
}
}
cout << ans << '\n';
}
```
:::
### H. Heximal
---
#### 題目摘要
給一個10進位數字$N,$ 並且 $0 \le N < 10^{500000}$
求轉成6進位後長度為多少
#### 想法
二分搜第一個滿足 $6^{ans} > N$ 的$ans$，大數運算交給python
:::spoiler 實作
```python=
a = int(input(''))
l=1
r=1000000
while(l<r):
m=(l+r)>>1
if (pow(6, m)>a):
r=m
else:
l=m+1
if a==0:
print(1)
else:
print(l)
```
:::
### I. Invitation(待補)
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
#ifdef LOCAL
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define rep(X, a, b) for(int X = a; X < b; ++X)
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
#define fi first
#define se second
#ifdef LOCAL
#define ZTMYACANESOCUTE // freopen("in.txt", "r", stdin);
#define debug(...) {cerr << #__VA_ARGS__ << " = "; dbg(__VA_ARGS__);}
#else
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0);
#define debug(...) 6;
#endif
void dbg() { cerr << '\n'; }
template<typename T, typename ...U>
void dbg(T t, U ...u) { cerr << t << ' '; dbg(u...); }
pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }
template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }
#define lpos pos << 1
#define rpos pos << 1 | 1
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
ll fpow (ll x, ll exp, ll mod = LLONG_MAX) { if (x == 0) return 0; ll res = 1; while (exp > 0) { if (exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1; } return res; }
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder_modint {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename conditional<is_same<T, __int128_t>::value ||
is_same<T, __int128>::value,
true_type,
false_type>::type;
template <class T>
using is_unsigned_int128 =
typename conditional<is_same<T, __uint128_t>::value ||
is_same<T, unsigned __int128>::value,
true_type,
false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename conditional<is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
true_type,
false_type>::type;
template <class T>
using is_signed_int = typename conditional<(is_integral<T>::value &&
is_signed<T>::value) ||
is_signed_int128<T>::value,
true_type,
false_type>::type;
template <class T>
using is_unsigned_int =
typename conditional<(is_integral<T>::value &&
is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
true_type,
false_type>::type;
template <class T>
using to_unsigned = typename conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename conditional<is_signed<T>::value,
make_unsigned<T>,
common_type<T>>::type>::type;
#else
template <class T> using is_integral = typename is_integral<T>;
template <class T>
using is_signed_int =
typename conditional<is_integral<T>::value && is_signed<T>::value,
true_type,
false_type>::type;
template <class T>
using is_unsigned_int =
typename conditional<is_integral<T>::value &&
is_unsigned<T>::value,
true_type,
false_type>::type;
template <class T>
using to_unsigned = typename conditional<is_signed_int<T>::value,
make_unsigned<T>,
common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = {2, 7, 61};
for (long long a : bases) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);
// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
// Contracts:
// [1] s - m0 * a = 0 (mod b)
// [2] t - m1 * a = 0 (mod b)
// [3] s * |m1| + t * |m0| <= b
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
// [3]:
// (s - t * u) * |m1| + t * |m0 - m1 * u|
// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
// = s * |m1| + t * |m0| <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
// by [3]: |m0| <= b/g
// by g != b: |m0| < b/g
if (m0 < 0) m0 += b / s;
return {s, m0};
}
// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
unsigned int _m;
unsigned long long im;
// @param m `1 <= m < 2^31`
explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
// @return m
unsigned int umod() const { return _m; }
// @param a `0 <= a < m`
// @param b `0 <= b < m`
// @return `a * b % m`
unsigned int mul(unsigned int a, unsigned int b) const {
// [1] m = 1
// a = b = im = 0, so okay
// [2] m >= 2
// im = ceil(2^64 / m)
// -> im * m = 2^64 + r (0 <= r < m)
// let z = a*b = c*m + d (0 <= c, d < m)
// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
// ((ab * im) >> 64) == c or c + 1
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned int v = (unsigned int)(z - x * _m);
if (_m <= v) v += _m;
return v;
}
};
struct modint_base {};
struct static_modint_base : modint_base {};
template <class T> using is_modint = is_base_of<modint_base, T>;
template <class T> using is_modint_t = enable_if_t<is_modint<T>::value>;
} // namespace internal
template <int m, enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
static_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
static_modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
static_modint(T v) {
_v = (unsigned int)(v % umod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint& operator*=(const mint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
if (prime) {
assert(_v);
return pow(umod() - 2);
} else {
auto eg = internal::inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
static constexpr bool prime = internal::is_prime<m>;
};
template <int id> struct dynamic_modint : internal::modint_base {
using mint = dynamic_modint;
public:
static int mod() { return (int)(bt.umod()); }
static void set_mod(int m) {
assert(1 <= m);
bt = internal::barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
dynamic_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
dynamic_modint(T v) {
long long x = (long long)(v % (long long)(mod()));
if (x < 0) x += mod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
dynamic_modint(T v) {
_v = (unsigned int)(v % mod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator*=(const mint& rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = internal::inv_gcd(_v, mod());
assert(eg.first == 1);
return eg.second;
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static internal::barrett bt;
static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt(998244353);
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
namespace internal {
template <class T>
using is_static_modint = is_base_of<internal::static_modint_base, T>;
template <class T>
using is_static_modint_t = enable_if_t<is_static_modint<T>::value>;
template <class> struct is_dynamic_modint : public false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public true_type {};
template <class T>
using is_dynamic_modint_t = enable_if_t<is_dynamic_modint<T>::value>;
} // namespace internal
} // namespace atcoder_modint
// need atcoder_modint
namespace atcoder_convolution {
namespace internal {
// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
constexpr int bsf_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (atcoder_modint::internal::pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
template <class mint,
int g = internal::primitive_root<mint::mod()>,
atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
struct fft_info {
static constexpr int rank2 = bsf_constexpr(mint::mod() - 1);
array<mint, rank2 + 1> root; // root[i]^(2^i) == 1
array<mint, rank2 + 1> iroot; // root[i] * iroot[i] == 1
array<mint, max(0, rank2 - 2 + 1)> rate2;
array<mint, max(0, rank2 - 2 + 1)> irate2;
array<mint, max(0, rank2 - 3 + 1)> rate3;
array<mint, max(0, rank2 - 3 + 1)> irate3;
fft_info() {
root[rank2] = mint(g).pow((mint::mod() - 1) >> rank2);
iroot[rank2] = root[rank2].inv();
for (int i = rank2 - 1; i >= 0; i--) {
root[i] = root[i + 1] * root[i + 1];
iroot[i] = iroot[i + 1] * iroot[i + 1];
}
{
mint prod = 1, iprod = 1;
for (int i = 0; i <= rank2 - 2; i++) {
rate2[i] = root[i + 2] * prod;
irate2[i] = iroot[i + 2] * iprod;
prod *= iroot[i + 2];
iprod *= root[i + 2];
}
}
{
mint prod = 1, iprod = 1;
for (int i = 0; i <= rank2 - 3; i++) {
rate3[i] = root[i + 3] * prod;
irate3[i] = iroot[i + 3] * iprod;
prod *= iroot[i + 3];
iprod *= root[i + 3];
}
}
}
};
template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
void butterfly(vector<mint>& a) {
int n = int(a.size());
int h = internal::ceil_pow2(n);
static const fft_info<mint> info;
int len = 0; // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
while (len < h) {
if (h - len == 1) {
int p = 1 << (h - len - 1);
mint rot = 1;
for (int s = 0; s < (1 << len); s++) {
int offset = s << (h - len);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p] * rot;
a[i + offset] = l + r;
a[i + offset + p] = l - r;
}
if (s + 1 != (1 << len))
rot *= info.rate2[bsf(~(unsigned int)(s))];
}
len++;
} else {
// 4-base
int p = 1 << (h - len - 2);
mint rot = 1, imag = info.root[2];
for (int s = 0; s < (1 << len); s++) {
mint rot2 = rot * rot;
mint rot3 = rot2 * rot;
int offset = s << (h - len);
for (int i = 0; i < p; i++) {
auto mod2 = 1ULL * mint::mod() * mint::mod();
auto a0 = 1ULL * a[i + offset].val();
auto a1 = 1ULL * a[i + offset + p].val() * rot.val();
auto a2 = 1ULL * a[i + offset + 2 * p].val() * rot2.val();
auto a3 = 1ULL * a[i + offset + 3 * p].val() * rot3.val();
auto a1na3imag =
1ULL * mint(a1 + mod2 - a3).val() * imag.val();
auto na2 = mod2 - a2;
a[i + offset] = a0 + a2 + a1 + a3;
a[i + offset + 1 * p] = a0 + a2 + (2 * mod2 - (a1 + a3));
a[i + offset + 2 * p] = a0 + na2 + a1na3imag;
a[i + offset + 3 * p] = a0 + na2 + (mod2 - a1na3imag);
}
if (s + 1 != (1 << len))
rot *= info.rate3[bsf(~(unsigned int)(s))];
}
len += 2;
}
}
}
template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
void butterfly_inv(vector<mint>& a) {
int n = int(a.size());
int h = internal::ceil_pow2(n);
static const fft_info<mint> info;
int len = h; // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
while (len) {
if (len == 1) {
int p = 1 << (h - len);
mint irot = 1;
for (int s = 0; s < (1 << (len - 1)); s++) {
int offset = s << (h - len + 1);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p];
a[i + offset] = l + r;
a[i + offset + p] =
(unsigned long long)(mint::mod() + l.val() - r.val()) *
irot.val();
;
}
if (s + 1 != (1 << (len - 1)))
irot *= info.irate2[bsf(~(unsigned int)(s))];
}
len--;
} else {
// 4-base
int p = 1 << (h - len);
mint irot = 1, iimag = info.iroot[2];
for (int s = 0; s < (1 << (len - 2)); s++) {
mint irot2 = irot * irot;
mint irot3 = irot2 * irot;
int offset = s << (h - len + 2);
for (int i = 0; i < p; i++) {
auto a0 = 1ULL * a[i + offset + 0 * p].val();
auto a1 = 1ULL * a[i + offset + 1 * p].val();
auto a2 = 1ULL * a[i + offset + 2 * p].val();
auto a3 = 1ULL * a[i + offset + 3 * p].val();
auto a2na3iimag =
1ULL *
mint((mint::mod() + a2 - a3) * iimag.val()).val();
a[i + offset] = a0 + a1 + a2 + a3;
a[i + offset + 1 * p] =
(a0 + (mint::mod() - a1) + a2na3iimag) * irot.val();
a[i + offset + 2 * p] =
(a0 + a1 + (mint::mod() - a2) + (mint::mod() - a3)) *
irot2.val();
a[i + offset + 3 * p] =
(a0 + (mint::mod() - a1) + (mint::mod() - a2na3iimag)) *
irot3.val();
}
if (s + 1 != (1 << (len - 2)))
irot *= info.irate3[bsf(~(unsigned int)(s))];
}
len -= 2;
}
}
}
template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
vector<mint> convolution_naive(const vector<mint>& a,
const vector<mint>& b) {
int n = int(a.size()), m = int(b.size());
vector<mint> ans(n + m - 1);
if (n < m) {
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
ans[i + j] += a[i] * b[j];
}
}
} else {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans[i + j] += a[i] * b[j];
}
}
}
return ans;
}
template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
vector<mint> convolution_fft(vector<mint> a, vector<mint> b) {
int n = int(a.size()), m = int(b.size());
int z = 1 << internal::ceil_pow2(n + m - 1);
a.resize(z);
internal::butterfly(a);
b.resize(z);
internal::butterfly(b);
for (int i = 0; i < z; i++) {
a[i] *= b[i];
}
internal::butterfly_inv(a);
a.resize(n + m - 1);
mint iz = mint(z).inv();
for (int i = 0; i < n + m - 1; i++) a[i] *= iz;
return a;
}
} // namespace internal
template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
vector<mint> convolution(vector<mint>&& a, vector<mint>&& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
if (min(n, m) <= 60) return atcoder_convolution::internal::convolution_naive(a, b);
return internal::convolution_fft(a, b);
}
template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
vector<mint> convolution(const vector<mint>& a,
const vector<mint>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
if (min(n, m) <= 60) return atcoder_convolution::internal::convolution_naive(a, b);
return internal::convolution_fft(a, b);
}
template <unsigned int mod = 998244353,
class T,
enable_if_t<atcoder_modint::internal::is_integral<T>::value>* = nullptr>
vector<T> convolution(const vector<T>& a, const vector<T>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
using mint = atcoder_modint::static_modint<mod>;
vector<mint> a2(n), b2(m);
for (int i = 0; i < n; i++) {
a2[i] = mint(a[i]);
}
for (int i = 0; i < m; i++) {
b2[i] = mint(b[i]);
}
auto c2 = convolution(move(a2), move(b2));
vector<T> c(n + m - 1);
for (int i = 0; i < n + m - 1; i++) {
c[i] = c2[i].val();
}
return c;
}
vector<long long> convolution_ll(const vector<long long>& a,
const vector<long long>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
static constexpr unsigned long long MOD1 = 754974721; // 2^24
static constexpr unsigned long long MOD2 = 167772161; // 2^25
static constexpr unsigned long long MOD3 = 469762049; // 2^26
static constexpr unsigned long long M2M3 = MOD2 * MOD3;
static constexpr unsigned long long M1M3 = MOD1 * MOD3;
static constexpr unsigned long long M1M2 = MOD1 * MOD2;
static constexpr unsigned long long M1M2M3 = MOD1 * MOD2 * MOD3;
static constexpr unsigned long long i1 =
atcoder_modint::internal::inv_gcd(MOD2 * MOD3, MOD1).second;
static constexpr unsigned long long i2 =
atcoder_modint::internal::inv_gcd(MOD1 * MOD3, MOD2).second;
static constexpr unsigned long long i3 =
atcoder_modint::internal::inv_gcd(MOD1 * MOD2, MOD3).second;
auto c1 = convolution<MOD1>(a, b);
auto c2 = convolution<MOD2>(a, b);
auto c3 = convolution<MOD3>(a, b);
vector<long long> c(n + m - 1);
for (int i = 0; i < n + m - 1; i++) {
unsigned long long x = 0;
x += (c1[i] * i1) % MOD1 * M2M3;
x += (c2[i] * i2) % MOD2 * M1M3;
x += (c3[i] * i3) % MOD3 * M1M2;
// B = 2^63, -B <= x, r(real value) < B
// (x, x - M, x - 2M, or x - 3M) = r (mod 2B)
// r = c1[i] (mod MOD1)
// focus on MOD1
// r = x, x - M', x - 2M', x - 3M' (M' = M % 2^64) (mod 2B)
// r = x,
// x - M' + (0 or 2B),
// x - 2M' + (0, 2B or 4B),
// x - 3M' + (0, 2B, 4B or 6B) (without mod!)
// (r - x) = 0, (0)
// - M' + (0 or 2B), (1)
// -2M' + (0 or 2B or 4B), (2)
// -3M' + (0 or 2B or 4B or 6B) (3) (mod MOD1)
// we checked that
// ((1) mod MOD1) mod 5 = 2
// ((2) mod MOD1) mod 5 = 3
// ((3) mod MOD1) mod 5 = 4
long long diff =
c1[i] - atcoder_modint::internal::safe_mod((long long)(x), (long long)(MOD1));
if (diff < 0) diff += MOD1;
static constexpr unsigned long long offset[5] = {
0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3};
x -= offset[diff % 5];
c[i] = x;
}
return c;
}
} // namespace atcoder_convolution
using mint = atcoder_modint::modint998244353;
using namespace atcoder_convolution;
ostream& operator << (ostream &os, const mint &p) { os << p.val(); return os; }
// need modint
vector<mint> fac, inv;
inline void init (int n) {
fac.resize(n + 1);
inv.resize(n + 1);
fac[0] = inv[0] = 1;
rep (i, 1, n + 1) fac[i] = fac[i - 1] * i;
inv[n] = fac[n].inv();
for (int i = n; i > 0; --i) inv[i - 1] = inv[i] * i;
}
inline mint Comb(int n, int k) {
if (k > n || k < 0) return 0;
return fac[n] * inv[k] * inv[n - k];
}
inline mint H(int n, int m) {
return Comb(n + m - 1, m);
}
inline mint catalan(int n){
return fac[2 * n] * inv[n + 1] * inv[n];
}
void solve() {
int n; cin >> n;
init(n);
vector<pii> seg;
vector<int> dic;
rep (i, 0, n) {
int l, r; cin >> l >> r;
seg.pb({l, r});
dic.pb(l);
dic.pb(r);
}
sort(all(dic));
dic.erase(unique(all(dic)), dic.end());
int m = ssize(dic);
for (auto &[l, r] : seg) {
l = lower_bound(all(dic), l) - dic.begin();
r = lower_bound(all(dic), r) - dic.begin();
}
auto calc = [&]() -> vector<mint> {
vector<int> cnt(m + 2, 0);
for (auto [l, r] : seg) cnt[l]++, cnt[r + 1]--;
partial_sum(all(cnt), cnt.begin());
vector<mint> a(n + 1, 0), b(n + 1, 0);
rep (i, 0, m + 1) a[cnt[i]] += fac[cnt[i]];
rep (i, 0, n + 1) b[i] = inv[n - i];
auto c = convolution(a, b);
c = vector(c.begin() + n, c.end());
rep (i, 0, n + 1) c[i] *= inv[i];
return c;
};
auto sum = calc();
for (auto &[l, r] : seg) r--;
auto sum2 = calc();
rep (i, 1, n + 1) cout << sum[i] - sum2[i] << " \n" [i == n];
}
int main() {
ZTMYACANESOCUTE;
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
```
:::
Sign in with Wallet
Connect another wallet