1972.md (22638B)
1 Source: https://codeforces.com/blog/entry/129027 2 3 [1972A - Contest Proposal](/contest/1972/problem/A "Codeforces Round 942 (Div. 2)") 4 5 **Hint 1** 6 7 Only add problems when they are needed. 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Solution** 14 15 ``` 16 //By: OIer rui_er 17 #include <bits/stdc++.h> 18 #define rep(x, y, z) for(int x = (y); x <= (z); ++x) 19 #define per(x, y, z) for(int x = (y); x >= (z); --x) 20 #define endl '\n' 21 using namespace std; 22 typedef long long ll; 23 24 const int N = 105; 25 26 int T, n, a[N], b[N]; 27 28 int main() { 29 ios::sync_with_stdio(false); 30 cin.tie(0); cout.tie(0); 31 for(cin >> T; T; --T) { 32 cin >> n; 33 rep(i, 1, n) cin >> a[i]; 34 rep(i, 1, n) cin >> b[i]; 35 int diff = 0, ans = 0; 36 rep(i, 1, n) { 37 if(a[i - diff] > b[i]) { 38 ++ans; 39 ++diff; 40 } 41 } 42 cout << ans << endl; 43 } 44 return 0; 45 } 46 ``` 47 48 [1972B - Coin Games](/contest/1972/problem/B "Codeforces Round 942 (Div. 2)") 49 50 **Hint 1** 51 52 Is there anything that *never* / *always* changes after each operation? 53 54 **Hint 2** 55 56 The parity. 57 58 **Tutorial** 59 60 Tutorial is loading... 61 62 **Solution** 63 64 ``` 65 //By: OIer rui_er 66 #include <bits/stdc++.h> 67 #define rep(x, y, z) for(int x = (y); x <= (z); ++x) 68 #define per(x, y, z) for(int x = (y); x >= (z); --x) 69 #define endl '\n' 70 using namespace std; 71 typedef long long ll; 72 73 int T, n; 74 string s; 75 76 int main() { 77 ios::sync_with_stdio(false); 78 cin.tie(0); cout.tie(0); 79 for(cin >> T; T; --T) { 80 cin >> n >> s; 81 int cntU = 0; 82 for(char c : s) if(c == 'U') ++cntU; 83 if(cntU & 1) cout << "YES" << endl; 84 else cout << "NO" << endl; 85 } 86 return 0; 87 } 88 ``` 89 90 [1967A - Permutation Counting](/contest/1967/problem/A "Codeforces Round 942 (Div. 1)") 91 92 **Hint 1** 93 94 What's the answer if $a_1=a_2=\cdots=a_n$ and $k=0$? 95 96 **Hint 2** 97 98 What's the answer if $k=0$? 99 100 **Hint 3** 101 102 You've already known the $\mathcal O(k)$ solution. How to improve it? 103 104 **Tutorial** 105 106 Tutorial is loading... 107 108 **Solution** 109 110 ``` 111 #include<bits/stdc++.h> 112 using namespace std; 113 void solve() 114 { 115 int n;long long k; 116 cin>>n>>k; 117 vector<long long>a(n); 118 for(int x=0;x<n;x++) 119 cin>>a[x]; 120 sort(a.begin(),a.end()); 121 reverse(a.begin(),a.end()); 122 long long lst=a.back(),cnt=1; 123 a.pop_back(); 124 while(!a.empty()&&lst==a.back())a.pop_back(),cnt++; 125 while(!a.empty()) 126 { 127 long long delta=a.back()-lst; 128 if(k<delta*cnt)break; 129 k-=delta*cnt; 130 lst=a.back(); 131 while(!a.empty()&&lst==a.back())a.pop_back(),cnt++; 132 } 133 lst+=k/cnt; 134 k%=cnt; 135 cnt-=k; 136 cout<<lst*n-cnt+1<<endl; 137 } 138 main() 139 { 140 ios::sync_with_stdio(false),cin.tie(0); 141 int t; 142 cin>>t; 143 while(t--)solve(); 144 } 145 ``` 146 147 [1967B1 - Reverse Card (Easy Version)](/contest/1967/problem/B1 "Codeforces Round 942 (Div. 1)") 148 149 **Hint 1** 150 151 Denote $\gcd(a,b)$ as $d$. 152 153 **Hint 2** 154 155 Did you notice that $b\mid a$? How to prove that? 156 157 **Tutorial** 158 159 Tutorial is loading... 160 161 **Solution** 162 163 ``` 164 #include<bits/stdc++.h> 165 using namespace std; 166 typedef long long ll; 167 const int N=2000005; 168 int tc,n,m; ll ans; 169 inline void solve(){ 170 cin>>n>>m; ans=0; 171 for(int i=1;i<=m;i++) 172 ans+=(n+i)/(1ll*i*i); 173 cout<<ans-1<<'\n'; 174 } 175 int main(){ 176 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 177 cin>>tc; while(tc--) solve(); 178 return 0; 179 } 180 ``` 181 182 [1967B2 - Reverse Card (Hard Version)](/contest/1967/problem/B2 "Codeforces Round 942 (Div. 1)") 183 184 **Hint 1** 185 186 Denote $\gcd(a,b)$ as $d$. Assume that $a=pd$ and $b=qd$. 187 188 **Hint 2** 189 190 $\gcd(p,q)=1$. 191 192 **Hint 3** 193 194 How large could $p$ and $q$ be? 195 196 **Tutorial** 197 198 Tutorial is loading... 199 200 **Solution** 201 202 ``` 203 #include <bits/stdc++.h> 204 using namespace std; 205 206 #define nl "\n" 207 #define nf endl 208 #define ll long long 209 #define pb push_back 210 #define _ << ' ' << 211 212 #define INF (ll)1e18 213 #define mod 998244353 214 #define maxn 110 215 216 int main() { 217 ios::sync_with_stdio(0); 218 cin.tie(0); 219 220 #if !ONLINE_JUDGE && !EVAL 221 ifstream cin("input.txt"); 222 ofstream cout("output.txt"); 223 #endif 224 int t; 225 cin>>t; 226 while(t--) 227 { 228 ll n,m; cin >> n>>m; 229 ll sq = sqrt(n) + 2,sqm=sqrt(m)+2; 230 231 vector bad(sq + 1, vector<bool>(sqm+1, 0)); 232 for (ll i = 2; i <= min(sq,sqm); i++) { 233 for (ll a = i; a <= sq; a += i) { 234 for (ll b = i; b <= sqm; b += i) { 235 bad[a][b] = true; 236 } 237 } 238 } 239 240 ll ans = 0; 241 for (ll a = 1; a * a <= n; a++) { 242 for (ll b = 1; b * b <= m; b++) { 243 if (bad[a][b]) continue; 244 ans += min(n/(a+b)/a,m/(a+b)/b); 245 } 246 } 247 cout << ans << nl; 248 } 249 250 return 0; 251 } 252 ``` 253 254 [1967C - Fenwick Tree](/contest/1967/problem/C "Codeforces Round 942 (Div. 1)") 255 256 **Hint 1** 257 258 The height of a Fenwick Tree is $\mathcal O(\log n)$, so operations like enumerating ancestors of each vertex will be acceptable. 259 260 **Hint 2** 261 262 What's the coefficient of $a_u$ in each $b$ value of its ancestors? 263 264 **Tutorial** 265 266 Tutorial is loading... 267 268 **Solution** 269 270 ``` 271 //By: OIer rui_er 272 #include <bits/stdc++.h> 273 #define rep(x, y, z) for(int x = (y); x <= (z); ++x) 274 #define per(x, y, z) for(int x = (y); x >= (z); --x) 275 #define debug(format...) fprintf(stderr, format) 276 #define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false) 277 #define endl '\n' 278 using namespace std; 279 typedef long long ll; 280 281 mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count()); 282 int randint(int L, int R) { 283 uniform_int_distribution<int> dist(L, R); 284 return dist(rnd); 285 } 286 287 template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;} 288 template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;} 289 290 template<int mod> 291 inline unsigned int down(unsigned int x) { 292 return x >= mod ? x - mod : x; 293 } 294 295 template<int mod> 296 struct Modint { 297 unsigned int x; 298 Modint() = default; 299 Modint(unsigned int x) : x(x) {} 300 friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;} 301 friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;} 302 friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);} 303 friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);} 304 friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;} 305 friend Modint operator/(Modint a, Modint b) {return a * ~b;} 306 friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;} 307 friend Modint operator~(Modint a) {return a ^ (mod - 2);} 308 friend Modint operator-(Modint a) {return down<mod>(mod - a.x);} 309 friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;} 310 friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;} 311 friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;} 312 friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;} 313 friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;} 314 friend Modint& operator++(Modint& a) {return a += 1;} 315 friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;} 316 friend Modint& operator--(Modint& a) {return a -= 1;} 317 friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;} 318 friend bool operator==(Modint a, Modint b) {return a.x == b.x;} 319 friend bool operator!=(Modint a, Modint b) {return !(a == b);} 320 }; 321 322 const int N = 1e6 + 100, mod = 998244353; 323 typedef Modint<mod> mint; 324 325 int T, n, k; 326 mint a[N], inv[N]; 327 328 inline int lowbit(int x) {return x & -x;} 329 330 int main() { 331 ios::sync_with_stdio(false); 332 cin.tie(0); cout.tie(0); 333 inv[0] = inv[1] = 1; 334 rep(i, 2, N - 1) inv[i] = (mod - mod / i) * inv[mod % i]; 335 for(cin >> T; T; --T) { 336 cin >> n >> k; 337 rep(i, 1, n) cin >> a[i]; 338 rep(i, 1, n) { 339 mint mul = 1; 340 for(int u = i + lowbit(i), d = 1; u <= n; u += lowbit(u), ++d) { 341 mul *= (d + k - 1) * inv[d]; 342 a[u] -= mul * a[i]; 343 } 344 } 345 rep(i, 1, n) cout << a[i] << " \n"[i == n]; 346 } 347 return 0; 348 } 349 ``` 350 351 [1967D - Long Way to be Non-decreasing](/contest/1967/problem/D "Codeforces Round 942 (Div. 1)") 352 353 **Hint 1** 354 355 Binary search on the answer of magics. 356 357 **Hint 2** 358 359 You may come up with many $\mathcal O(m\log m + n\log^2 m)$ solutions with heavy data structures. Unfortunately, none of them is helpful. 360 361 **Hint 3** 362 363 The key is to judge $\mathcal O(m\log n)$ times whether vertex $u$ is reachable from vertex $v$ in $k$ steps, instead of querying the minimal value or something else. 364 365 **Tutorial** 366 367 Tutorial is loading... 368 369 **Solution** 370 371 ``` 372 #include <bits/stdc++.h> 373 374 namespace FastIO { 375 template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; } 376 template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar(x % 10 ^ '0'); } 377 template <typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x); } 378 template <typename T> inline void print(T x, char en) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x), putchar(en); } 379 }; using namespace FastIO; 380 381 #define MAXM 1000001 382 int dep[MAXM], id[MAXM], dfn[MAXM], to[MAXM], sz[MAXM], tot = 0; 383 std::vector<int> ch[MAXM]; 384 void dfs(int u) { 385 sz[u] = 1, dfn[u] = ++tot; 386 for (int v : ch[u]) { 387 dep[v] = dep[u] + 1, id[v] = id[u]; 388 dfs(v), sz[u] += sz[v]; 389 } 390 } 391 inline bool inSub(int u, int v) /* v \in u ? */ { return dfn[u] <= dfn[v] && dfn[v] < dfn[u] + sz[u]; } 392 constexpr int INF = 0x3f3f3f3f; 393 inline int query(int u, int v) /* u -> v */ { 394 if (u == v) return 0; 395 if (id[u] != id[v]) return INF; 396 int res = INF; 397 if (inSub(v, u)) res = dep[u] - dep[v]; 398 if (inSub(v, to[id[u]])) res = std::min(dep[u] - dep[v] + dep[to[id[u]]] + 1, res); 399 // printf("query(%d, %d) = %d\n", u, v, res); 400 return res; 401 } 402 403 #define MAXN 1000001 404 int a[MAXN], N, M; 405 bool check(int val) { 406 // printf("check %d\n", val); 407 int lst = 1; 408 for (int i = 1; i <= N; ++i) { 409 while (lst <= M && query(a[i], lst) > val) ++lst; 410 if (lst > M) return false; 411 // printf("a[%d] = %d\n", i, lst); 412 } 413 return true; 414 } 415 416 namespace DSU { 417 int fa[MAXM]; 418 void inis(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; } 419 inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } 420 inline bool merge(int x, int y) { if (find(x) == find(y)) return false; fa[fa[x]] = fa[y]; return true; } 421 }; using namespace DSU; 422 423 int main() { 424 int T = read<int>(); 425 while (T--) { 426 N = read<int>(), M = read<int>(), inis(M); 427 for (int i = 1; i <= N; ++i) a[i] = read<int>(); 428 for (int x = 1; x <= M; ++x) dep[x] = id[x] = dfn[x] = to[x] = sz[x] = 0, ch[x].clear(); 429 tot = 0; 430 for (int i = 1, p; i <= M; ++i) { 431 p = read<int>(); 432 if (merge(i, p)) ch[p].push_back(i); else to[i] = p; 433 } 434 for (int i = 1; i <= M; ++i) if (to[i] > 0) id[i] = i, dfs(i); 435 if (!check(M)) { puts("-1"); continue; } 436 int L = 0, R = M; 437 while (L < R) { 438 int mid = L + R >> 1; 439 if (check(mid)) R = mid; else L = mid + 1; 440 } 441 print<int>(R, '\n'); 442 } 443 } 444 ``` 445 446 [1967E1 - Again Counting Arrays (Easy Version)](/contest/1967/problem/E1 "Codeforces Round 942 (Div. 1)") 447 448 **Hint 1** 449 450 Use the simplest way to judge if an $a$ is valid. 451 452 **Hint 2** 453 454 We've got a $\mathcal O(nm)$ solution. Our target time complexity is $\mathcal O(n\sqrt{n})$. 455 456 **Hint 3** 457 458 It can be boiled down to a grid path counting problem. 459 460 **Tutorial** 461 462 Tutorial is loading... 463 464 **Solution** 465 466 ``` 467 #include <bits/stdc++.h> 468 469 namespace FastIO { 470 template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; } 471 template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar(x % 10 ^ '0'); } 472 template <typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x); } 473 template <typename T> inline void print(T x, char en) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x), putchar(en); } 474 }; using namespace FastIO; 475 476 #define MAXN 2000001 477 namespace Maths { 478 constexpr int MOD = 998244353; 479 long long qpow(long long a, long long x) { long long ans = 1; while (x) (x & 1) && (ans = ans * a % MOD), a = a * a % MOD, x >>= 1; return ans; } 480 long long frac[MAXN << 1 | 1], prac[MAXN << 1 | 1]; 481 inline void inis(int V = MAXN * 2) { frac[0] = prac[0] = 1; for (int i = 1; i <= V; ++i) frac[i] = frac[i - 1] * i % MOD; prac[V] = qpow(frac[V], MOD - 2); for (int i = V - 1; i; --i) prac[i] = prac[i + 1] * (i + 1) % MOD; } 482 inline long long C(int N, int M) { if (N < 0 || M < 0 || N < M) return 0; return frac[N] * prac[M] % MOD * prac[N - M] % MOD; } 483 }; using namespace Maths; 484 485 struct Point { 486 int x, y; 487 Point () {} 488 Point (int X, int Y) : x(X), y(Y) {} 489 inline void flip(int b) { x += b, y -= b, std::swap(x, y); } 490 inline int calc() { return C(x + y, y); } 491 } pA, pB; 492 493 inline void add(int& x, int y) { (x += y) >= MOD && (x -= MOD); } 494 inline void del(int& x, int y) { (x -= y) < 0 && (x += MOD); } 495 496 int calc(int p, int q, int b1, int b2) { 497 pA = pB = Point(p, q); 498 int ans = pA.calc(); 499 while (pA.x >= 0 && pA.y >= 0) 500 pA.flip(b1), del(ans, pA.calc()), pA.flip(b2), add(ans, pA.calc()); 501 while (pB.x >= 0 && pB.y >= 0) 502 pB.flip(b2), del(ans, pB.calc()), pB.flip(b1), add(ans, pB.calc()); 503 return ans; 504 } 505 506 int dp[2][3001], powm[MAXN]; 507 void solve() { 508 int N = read<int>(), M = read<int>(), b0 = read<int>(); 509 if (b0 >= M) return (void)print<int>(qpow(M, N), '\n'); 510 powm[0] = 1; for (int i = 1; i <= N; ++i) powm[i] = 1ll * M * powm[i - 1] % MOD; 511 if (1ll * M * M <= N) { // dp 512 for (int k = 0; k < M; ++k) dp[0][k] = (int)(k == b0), dp[1][k] = 0; 513 int ans = 1ll * dp[0][M - 1] * (M - 1) % MOD * powm[N - 1] % MOD; 514 for (int i = 1; i <= N; ++i) { 515 auto now = dp[i & 1], lst = dp[(i & 1) ^ 1]; 516 now[0] = 0; for (int k = 0; k + 1 < M; ++k) now[k + 1] = 1ll * lst[k] * (M - 1) % MOD; 517 for (int k = 1; k < M; ++k) add(now[k - 1], lst[k]); 518 if (i < N) add(ans, 1ll * now[M - 1] * (M - 1) % MOD * powm[N - i - 1] % MOD); 519 } 520 for (int k = 0; k < M; ++k) add(ans, dp[N & 1][k]); 521 print<int>(ans, '\n'); 522 } else { // reflective inclusion-exclusion 523 const int B1 = M - b0, B2 = -1 - b0; int ans = qpow(M, N); 524 for (int x = b0, y = 0, k = 1, p = b0; p < N; p += 2, ++x, ++y, k = 1ll * k * (M - 1) % MOD) 525 del(ans, 1ll * calc(x, y, B1, B2) * k % MOD * powm[N - p - 1] % MOD); 526 print<int>(ans, '\n'); 527 } 528 } 529 530 int main() { int T = read<int>(); inis(); while (T--) solve(); return 0; } 531 ``` 532 533 [1967E2 - Again Counting Arrays (Hard Version)](/contest/1967/problem/E2 "Codeforces Round 942 (Div. 1)") 534 535 Thanks [A_G](/profile/A_G "Legendary Grandmaster A_G") for discovering that E2 is possible! 536 537 **Hint 1** 538 539 Solve E1 with $\mathcal O(n\sqrt{n})$ solution first (The $\mathcal O(n\log^2n)$ solution doesn't help much in E2). 540 541 **Hint 2** 542 543 For a single round of inclusion-exclusion, write down the form of the answer as simple as possible. 544 545 **Tutorial** 546 547 Tutorial is loading... 548 549 **Solution** 550 551 ``` 552 #include <bits/stdc++.h> 553 using namespace std; 554 555 const int MOD = 998244353; 556 const int N = 2e6+5; 557 int inv[N]; 558 559 int inversemod(int p, int q) { 560 // assumes p > 0 561 // https://codeforces.com/blog/entry/23365 562 return (p > 1 ? q-1LL*inversemod(q%p, p)*q/p : 1); 563 } 564 565 void add(int& x, int y) { 566 x += y; 567 if (x >= MOD) x -= MOD; 568 } 569 570 void sub(int& x, int y) { 571 x -= y; 572 if (x < 0) x += MOD; 573 } 574 575 int solve(int n, int m, int b0) { 576 // let X = hit -1, Y = hit m 577 // f(S) = count of sequences that end up in [0, infty] while containing the pattern S 578 // g(S) = count of sequences that end up in [-infty, -1] while containing the pattern S 579 // we want f() - f(X) + f(YX) - f(XYX) + f(YXYX) - f(XYXYX) + ... 580 // + g(Y) - g(XY) + g(YXY) - g(XYXY) + g(YXYXY) - ... 581 vector<int> pw(n+1); 582 pw[0] = 1; 583 for (int i = 1; i <= n; i++) pw[i] = 1LL*pw[i-1]*(m-1) % MOD; 584 585 // final ans will be sum from i = 0 to n of (n choose i) a_i 586 vector<int> a(n+2); 587 auto work = [&] (int c, int pw_coeff, int sgn_x) -> bool { 588 // let RANGE = [-infty, -1] if sgn_x == -1 and [0, infty] if sgn_x == 1 589 // for all x in RANGE such that (n+x+c)/2 is between 0 and n inclusive, 590 // add pw_coeff*pw[(n+x-b0)/2] to a[(n+x+c)/2] 591 592 // return 0 to signal that we are out of bounds and should exit, otherwise 1 593 int l = 0; 594 if (sgn_x == 1) l = max(l, (n+c+1)>>1); 595 int r = n; 596 if (sgn_x == -1) r = min(r, (n+c-1)>>1); 597 if (l > r) return 0; 598 add(a[l], 1LL*pw_coeff*pw[l-(b0+c)/2] % MOD); 599 sub(a[r+1], 1LL*pw_coeff*pw[r+1-(b0+c)/2] % MOD); 600 return 1; 601 }; 602 603 int ans = 0; 604 // f(k*YX) 605 // after reflection trick, end up in x + 2*(m+1)*k 606 for (int k = 0; work(2*(m+1)*k - b0, 1, 1); k++); 607 608 // f(X + k*YX) 609 // after reflection trick, end up in -2-x - 2*(m+1)*k 610 for (int k = 0; work(2*(m+1)*k+2+b0, MOD-1, 1); k++); 611 612 // g(Y + k*XY) 613 // after reflection trick, end up in 2*m-x + 2*(m+1)*k 614 for (int k = 0; work(-2*m -2*(m+1)*k + b0, 1, -1); k++); 615 616 // g(k*XY) 617 // after reflection trick, end up in x - 2*(m+1)*k 618 for (int k = 1; work(-2*(m+1)*k - b0, MOD-1, -1); k++); 619 620 for (int i = 1; i <= n; i++) { 621 add(a[i], 1LL*a[i-1]*(m-1) % MOD); 622 } 623 624 // do the binomial stuff without precalculated factorials because why not 625 int coeff = 1; 626 for (int i = 0; i <= n; i++) { 627 add(ans, 1LL * coeff * a[i] % MOD); 628 coeff = 1LL * coeff * (n-i) % MOD * inv[i+1] % MOD; 629 } 630 631 return ans; 632 } 633 634 int main () { 635 ios_base::sync_with_stdio(0); cin.tie(0); 636 inv[1] = 1; 637 for (int i = 2; i < N; i++) inv[i] = 1LL*(MOD-MOD/i)*inv[MOD % i] % MOD; 638 639 int T; 640 cin >> T; 641 while (T--) { 642 int n, m, b0; 643 cin >> n >> m >> b0; 644 if (b0 >= m) { 645 int ans = 1; 646 for (int i = 0; i < n; i++) ans = 1LL*ans*m % MOD; 647 cout << ans << '\n'; 648 continue; 649 } 650 cout << solve(n, m, b0) << '\n'; 651 } 652 } 653 ``` 654 655 [1967F - Next and Prev](/contest/1967/problem/F "Codeforces Round 942 (Div. 1)") 656 657 **Hint 1** 658 659 How to maintain $\sum\min(nxt_i-pre_i,x)$? Try $\sum\min(nxt_i-i,x)+\min(i-pre_i,x)$. 660 661 **Hint 2** 662 663 To maintain $\sum\min(nxt_i-i,x)$, we can use chunking. Just +1 and $\operatorname{chkmin}$. 664 665 **Hint 3** 666 667 To finish it, consider what we do in segment-beats. 668 669 **Tutorial** 670 671 Tutorial is loading... 672 673 **Solution** 674 675 ``` 676 #include<bits/stdc++.h> 677 using namespace std; 678 679 constexpr int maxn=300010,maxq=100010,B=400; 680 681 int n,bn,a[maxn],b[maxn],idx[maxn],nxt[maxn],add[maxn/B+5],mxadd[maxn/B+5],mx[maxn/B+5],se[maxn/B+5],t[maxn]; 682 long long ans[maxq]; 683 vector<int>val[maxn/B+5],mxval[maxn/B+5],pre[maxn/B+5],mxpre[maxn/B+5],pos[maxn/B+5],ks[maxn]; 684 685 void vAdd(int i) 686 { 687 for(;i<=n;i+=(i&-i)) t[i]++; 688 } 689 690 int nQuery(int i) 691 { 692 int s=0; 693 for(;i;i-=(i&-i)) s+=t[i]; 694 return s; 695 } 696 697 void vWork() 698 { 699 int i,j,tot=0; 700 for(i=1;i<=n;i++) b[a[i]]=i; 701 for(i=1;i<=n;i++) 702 { 703 int p=b[i],bp=(p-1)/B+1; 704 val[bp].clear(); 705 mxval[bp].clear(); 706 auto radixsort=[](vector<int>&v) 707 { 708 if(v.empty()) return; 709 static int buc[1024],res[B+5]; 710 auto tmp=minmax_element(v.begin(),v.end()); 711 int mn=*tmp.first,rg=*tmp.second-mn; 712 if(!rg) return; 713 int lv=__lg(rg)/2+1,len=1<<lv,i; 714 memset(buc,0,len*4); 715 for(int &it:v) it-=mn,buc[it&(len-1)]++; 716 for(i=1;i<len;i++) buc[i]+=buc[i-1]; 717 for(int it:v) res[--buc[it&(len-1)]]=it; 718 memset(buc,0,len*4); 719 for(int it:v) buc[it>>lv]++; 720 for(i=1;i<len;i++) buc[i]+=buc[i-1]; 721 for(i=v.size()-1;i>=0;i--) v[--buc[res[i]>>lv]]=res[i]+mn; 722 }; 723 auto getpre=[&](vector<int>&pre,const vector<int>&ori) 724 { 725 pre.resize(ori.size()); 726 if(ori.empty()) return; 727 pre[0]=ori[0]; 728 for(int i=1;i<(int)ori.size();i++) pre[i]=pre[i-1]+ori[i]; 729 }; 730 int lstmx=mx[bp]; 731 vAdd(p); 732 idx[p]=nQuery(p); 733 mx[bp]=nxt[p]=n*2; 734 se[bp]=0; 735 auto it=pos[bp].begin(); 736 for(;it<pos[bp].end();it++) 737 { 738 j=*it; 739 if(j>p) break; 740 nxt[j]+=add[bp]; 741 if(nxt[j]>lstmx) nxt[j]+=mxadd[bp]; 742 nxt[j]=min(nxt[j],idx[p]); 743 idx[j]+=add[bp]; 744 if(nxt[j]>mx[bp]) se[bp]=mx[bp],mx[bp]=nxt[j]; 745 else if(nxt[j]>se[bp]) se[bp]=nxt[j]; 746 } 747 it=pos[bp].insert(it,p); 748 for(it++;it!=pos[bp].end();it++) 749 { 750 j=*it; 751 nxt[j]+=add[bp]; 752 if(nxt[j]>lstmx) nxt[j]+=mxadd[bp]; 753 nxt[j]++; 754 idx[j]+=add[bp]+1; 755 if(nxt[j]>mx[bp]) se[bp]=mx[bp],mx[bp]=nxt[j]; 756 else if(nxt[j]>se[bp]) se[bp]=nxt[j]; 757 } 758 for(int j:pos[bp]) 759 { 760 if(nxt[j]==mx[bp]) mxval[bp].push_back(nxt[j]-idx[j]); 761 else val[bp].push_back(nxt[j]-idx[j]); 762 } 763 add[bp]=mxadd[bp]=0; 764 radixsort(val[bp]); 765 getpre(pre[bp],val[bp]); 766 radixsort(mxval[bp]); 767 getpre(mxpre[bp],mxval[bp]); 768 for(j=bp+1;j<=bn;j++) add[j]++,mx[j]++,se[j]++; 769 for(j=1;j<bp;j++) 770 { 771 if(mx[j]<=idx[p]) continue; 772 if(se[j]<idx[p]) 773 { 774 mxadd[j]+=idx[p]-mx[j],mx[j]=idx[p]; 775 continue; 776 } 777 val[j].clear(); 778 mxval[j].clear(); 779 lstmx=mx[j]; 780 mx[j]=idx[p],se[j]=0; 781 for(int x:pos[j]) 782 { 783 nxt[x]+=add[j]; 784 idx[x]+=add[j]; 785 if(nxt[x]>lstmx) nxt[x]+=mxadd[j]; 786 if(nxt[x]>=idx[p]) 787 { 788 nxt[x]=idx[p]; 789 mxval[j].push_back(nxt[x]-idx[x]); 790 } 791 else 792 { 793 if(nxt[x]>se[j]) se[j]=nxt[x]; 794 val[j].push_back(nxt[x]-idx[x]); 795 } 796 } 797 add[j]=mxadd[j]=0; 798 radixsort(val[j]); 799 getpre(pre[j],val[j]); 800 radixsort(mxval[j]); 801 getpre(mxpre[j],mxval[j]); 802 } 803 for(int ki:ks[i]) 804 { 805 tot++; 806 for(j=1;j<=bn;j++) 807 { 808 auto it=lower_bound(val[j].begin(),val[j].end(),ki); 809 ans[tot]+=(val[j].end()-it)*ki; 810 if(it!=val[j].begin()) ans[tot]+=pre[j][it-val[j].begin()-1]; 811 it=lower_bound(mxval[j].begin(),mxval[j].end(),ki-mxadd[j]); 812 ans[tot]+=(mxval[j].end()-it)*ki; 813 if(it!=mxval[j].begin()) ans[tot]+=(it-mxval[j].begin())*mxadd[j]+mxpre[j][it-mxval[j].begin()-1]; 814 } 815 } 816 } 817 } 818 819 int main() 820 { 821 ios::sync_with_stdio(false),cin.tie(0); 822 int T; 823 cin>>T; 824 while(T--) 825 { 826 int i,ki,tot=0; 827 cin>>n; 828 bn=(n-1)/B+1; 829 for(i=1;i<=n;i++) cin>>a[i]; 830 for(i=1;i<=n;i++) 831 { 832 cin>>ki; 833 ks[i].resize(ki); 834 for(int &it:ks[i]) 835 { 836 cin>>it; 837 ans[++tot]=-(i+it-1); 838 } 839 } 840 vWork(); 841 reverse(a+1,a+n+1); 842 for(int x=1;x<=n;x++) 843 t[x]=0; 844 for(i=1;i<=bn;i++) mx[i]=0,se[i]=0,val[i].clear(),mxval[i].clear(),pos[i].clear(); 845 vWork(); 846 for(int x=1;x<=n;x++) 847 t[x]=0; 848 for(i=1;i<=bn;i++) mx[i]=0,se[i]=0,val[i].clear(),mxval[i].clear(),pos[i].clear(); 849 for(i=1;i<=tot;i++) cout<<ans[i]<<'\n'; 850 tot=0; 851 } 852 return 0; 853 } 854 ```