1096.md (12552B)
1 Source: https://codeforces.com/blog/entry/64156 2 3 [1096A - Find Divisible](/contest/1096/problem/A "Educational Codeforces Round 57 (Rated for Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution (PikMike)** 10 11 ``` 12 T = int(input()) 13 for i in range(T): 14 l, r = map(int, input().split()) 15 print(l, l * 2) 16 ``` 17 18 [1096B - Substring Removal](/contest/1096/problem/B "Educational Codeforces Round 57 (Rated for Div. 2)") 19 20 **Tutorial** 21 22 Tutorial is loading... 23 24 **Solution (Vovuh)** 25 26 ``` 27 #include <bits/stdc++.h> 28 29 using namespace std; 30 31 int main() { 32 #ifdef _DEBUG 33 freopen("input.txt", "r", stdin); 34 // freopen("output.txt", "w", stdout); 35 #endif 36 37 int n; 38 string s; 39 cin >> n >> s; 40 int cntl = 0, cntr = 0; 41 for (int i = 0; i < n; ++i) { 42 if (s[i] == s[0]) { 43 ++cntl; 44 } else { 45 break; 46 } 47 } 48 for (int i = n - 1; i >= 0; --i) { 49 if (s[i] == s[n - 1]) { 50 ++cntr; 51 } else { 52 break; 53 } 54 } 55 if (s[0] == s[n - 1]) { 56 cout << ((cntl + 1) * 1ll * (cntr + 1)) % 998244353 << endl; 57 } else { 58 cout << (cntl + cntr + 1) % 998244353; 59 } 60 61 return 0; 62 } 63 ``` 64 65 [1096C - Polygon for the Angle](/contest/1096/problem/C "Educational Codeforces Round 57 (Rated for Div. 2)") 66 67 **Tutorial** 68 69 Tutorial is loading... 70 71 **Solution (adedalic)** 72 73 ``` 74 #include<bits/stdc++.h> 75 using namespace std; 76 77 int ang; 78 79 inline bool read() { 80 if(!(cin >> ang)) 81 return false; 82 return true; 83 } 84 85 inline void solve() { 86 int g = __gcd(ang, 180); 87 int k = ang / g; 88 int n = 180 / g; 89 90 if(k + 1 == n) 91 k *= 2, n *= 2; 92 cout << n << endl; 93 } 94 95 int main() { 96 #ifdef _DEBUG 97 freopen("input.txt", "r", stdin); 98 int tt = clock(); 99 #endif 100 cout << fixed << setprecision(15); 101 102 int tc; cin >> tc; 103 while(tc--) { 104 assert(read()); 105 solve(); 106 107 #ifdef _DEBUG 108 cerr << "TIME = " << clock() - tt << endl; 109 tt = clock(); 110 #endif 111 } 112 return 0; 113 } 114 ``` 115 116 [1096D - Easy Problem](/contest/1096/problem/D "Educational Codeforces Round 57 (Rated for Div. 2)") 117 118 **Tutorial** 119 120 Tutorial is loading... 121 122 **Solution (PikMike)** 123 124 ``` 125 #include <bits/stdc++.h> 126 127 #define forn(i, n) for (int i = 0; i < int(n); i++) 128 129 using namespace std; 130 131 const int N = 100 * 1000 + 13; 132 const long long INF64 = 1e18; 133 134 int n; 135 string s; 136 int a[N]; 137 long long dp[N][5]; 138 139 const string h = "hard"; 140 141 int main() { 142 scanf("%d", &n); 143 static char buf[N]; 144 scanf("%s", buf); 145 s = buf; 146 forn(i, n) 147 scanf("%d", &a[i]); 148 149 forn(i, N) forn(j, 5) dp[i][j] = INF64; 150 dp[0][0] = 0; 151 forn(i, n) forn(j, 4){ 152 dp[i + 1][j + (s[i] == h[j])] = min(dp[i + 1][j + (s[i] == h[j])], dp[i][j]); 153 dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + a[i]); 154 } 155 156 printf("%lld\n", *min_element(dp[n], dp[n] + 4)); 157 return 0; 158 } 159 ``` 160 161 [1096E - The Top Scorer](/contest/1096/problem/E "Educational Codeforces Round 57 (Rated for Div. 2)") 162 163 **Tutorial** 164 165 Tutorial is loading... 166 167 **Solution (PikMike)** 168 169 ``` 170 #include <bits/stdc++.h> 171 172 #define forn(i, n) for (int i = 0; i < int(n); i++) 173 174 using namespace std; 175 176 const int MOD = 998244353; 177 const int N = 10 * 1000 + 7; 178 const int M = 100 + 7; 179 180 int fact[N], rfact[N]; 181 182 int add(int a, int b){ 183 a += b; 184 if (a >= MOD) a -= MOD; 185 if (a < 0) a += MOD; 186 return a; 187 } 188 189 int mul(int a, int b){ 190 return (a * 1ll * b) % MOD; 191 } 192 193 int binpow(int a, int b){ 194 int res = 1; 195 while (b){ 196 if (b & 1) 197 res = mul(res, a); 198 a = mul(a, a); 199 b >>= 1; 200 } 201 return res; 202 } 203 204 int cnk(int n, int k){ 205 if (n == k) return 1; 206 if (k < 0 || k > n) return 0; 207 return mul(fact[n], mul(rfact[k], rfact[n - k])); 208 } 209 210 int g(int s, int p, int m){ 211 int res = 0; 212 forn(i, p + 1) 213 res = add(res, mul(i & 1 ? MOD - 1 : 1, mul(cnk(p, i), cnk(s + p - 1 - i * (m + 1), p - 1)))); 214 return res; 215 } 216 217 int inv(int x){ 218 return mul(rfact[x], fact[x - 1]); 219 } 220 221 int main() { 222 fact[0] = 1; 223 for (int i = 1; i < N; ++i) fact[i] = mul(fact[i - 1], i); 224 rfact[N - 1] = binpow(fact[N - 1], MOD - 2); 225 for (int i = N - 2; i >= 0; --i) rfact[i] = mul(rfact[i + 1], i + 1); 226 227 int p, s, r; 228 scanf("%d%d%d", &p, &s, &r); 229 230 int Q = cnk(s - r + p - 1, p - 1); 231 int P = 0; 232 for (int t = r; t <= s; ++t) for (int q = 1; q <= p; ++q) 233 P = add(P, mul(mul(cnk(p - 1, q - 1), inv(q)), g(s - q * t, p - q, t - 1))); 234 235 printf("%d\n", mul(P, binpow(Q, MOD - 2))); 236 return 0; 237 } 238 ``` 239 240 [1096F - Inversion Expectation](/contest/1096/problem/F "Educational Codeforces Round 57 (Rated for Div. 2)") 241 242 **Tutorial** 243 244 Tutorial is loading... 245 246 **Solution (PikMike)** 247 248 ``` 249 #include <bits/stdc++.h> 250 251 #define forn(i, n) for (int i = 0; i < int(n); i++) 252 253 using namespace std; 254 255 const int N = 200 * 1000 + 13; 256 const int MOD = 998244353; 257 258 int n; 259 int p[N]; 260 bool used[N]; 261 int gt[N]; 262 263 int add(int a, int b){ 264 a += b; 265 if (a >= MOD) 266 a -= MOD; 267 return a; 268 } 269 270 int mul(int a, int b){ 271 return (a * 1ll * b) % MOD; 272 } 273 274 int binpow(int a, int b){ 275 int res = 1; 276 while (b){ 277 if (b & 1) 278 res = mul(res, a); 279 a = mul(a, a); 280 b >>= 1; 281 } 282 return res; 283 } 284 285 int f[N]; 286 287 void upd(int x){ 288 for (int i = x; i < N; i |= i + 1) 289 ++f[i]; 290 } 291 292 int get(int x){ 293 int sum = 0; 294 for (int i = x; i >= 0; i = (i & (i + 1)) - 1) 295 sum += f[i]; 296 return sum; 297 } 298 299 int main() { 300 scanf("%d", &n); 301 forn(i, n){ 302 scanf("%d", &p[i]); 303 if (p[i] != -1) 304 used[p[i]] = true; 305 } 306 307 int cur = 0; 308 for (int i = n; i >= 1; --i){ 309 gt[i] = cur; 310 cur += !used[i]; 311 } 312 313 // case 1 314 int ans = mul(mul(cur, cur - 1), binpow(4, MOD - 2)); 315 316 int inv = binpow(cur, MOD - 2); 317 318 // case 2 319 int lft = 0; 320 forn(i, n){ 321 if (p[i] == -1) 322 ++lft; 323 else 324 ans = add(ans, mul(lft, mul(gt[p[i]], inv))); 325 } 326 327 // case 3 328 int rgh = 0; 329 for (int i = n - 1; i >= 0; --i){ 330 if (p[i] == -1) 331 ++rgh; 332 else 333 ans = add(ans, mul(rgh, mul(cur - gt[p[i]], inv))); 334 } 335 336 // case 4 337 int tmp = 0; 338 forn(i, n) if (p[i] != -1){ 339 ans = add(ans, tmp - get(p[i])); 340 upd(p[i]); 341 ++tmp; 342 } 343 344 printf("%d\n", ans); 345 return 0; 346 } 347 ``` 348 349 [1096G - Lucky Tickets](/contest/1096/problem/G "Educational Codeforces Round 57 (Rated for Div. 2)") 350 351 **Tutorial** 352 353 Tutorial is loading... 354 355 **Solution 1 (adedalic)** 356 357 ``` 358 #include<bits/stdc++.h> 359 360 using namespace std; 361 362 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 363 #define forn(i, n) fore(i, 0, n) 364 365 #define sz(a) int((a).size()) 366 #define all(a) (a).begin(), (a).end() 367 368 #define mp make_pair 369 #define pb push_back 370 371 #define x first 372 #define y second 373 374 typedef long long li; 375 typedef long double ld; 376 typedef pair<int, int> pt; 377 378 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 379 return out << "(" << p.x << ", " << p.y << ")"; 380 } 381 382 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 383 out << "["; 384 forn(i, sz(v)) { 385 if(i) out << ", "; 386 out << v[i]; 387 } 388 return out << "]"; 389 } 390 391 const int INF = int(1e9); 392 const li INF64 = li(1e18); 393 const ld EPS = 1e-9; 394 395 const int N = 2500 * 1000 + 555; 396 const int LOGN = 22; 397 398 const int MOD = 998244353; 399 int g = 3; 400 401 inline int mul(int a, int b){ 402 return int(a * 1ll * b % MOD); 403 } 404 405 inline int norm(int a) { 406 if(a >= MOD) 407 a -= MOD; 408 if(a < 0) 409 a += MOD; 410 return a; 411 } 412 413 inline int binPow(int a, int k) { 414 int ans = 1; 415 while(k > 0) { 416 if(k & 1) 417 ans = mul(ans, a); 418 a = mul(a, a); 419 k >>= 1; 420 } 421 return ans; 422 } 423 424 inline int inv(int a) { 425 return binPow(a, MOD - 2); 426 } 427 428 vector<int> w[LOGN]; 429 vector<int> rv[LOGN]; 430 431 void precalc() { 432 int wb = binPow(g, (MOD - 1) / (1 << LOGN)); 433 434 for(int st = 0; st < LOGN - 1; st++) { 435 w[st].assign(1 << st, 1); 436 437 int bw = binPow(wb, 1 << (LOGN - st - 1)); 438 int cw = 1; 439 440 for (int k = 0; k < (1 << st); k++) { 441 w[st][k] = cw; 442 cw = mul(cw, bw); 443 } 444 } 445 for(int st = 0; st < LOGN; st++) { 446 rv[st].assign(1 << st, 0); 447 448 if(st == 0) { 449 rv[st][0] = 0; 450 continue; 451 } 452 int h = (1 << (st - 1)); 453 for(int k = 0; k < (1 << st); k++) 454 rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h); 455 } 456 } 457 458 inline void fft(int a[N], int n, bool inverse) { 459 int ln = 0; 460 while((1 << ln) < n) 461 ln++; 462 463 assert((1 << ln) < N); 464 n = (1 << ln); 465 466 forn(i, n) { 467 int ni = rv[ln][i]; 468 if(i < ni) 469 swap(a[i], a[ni]); 470 } 471 472 for(int st = 0; (1 << st) < n; st++) { 473 int len = (1 << st); 474 for(int k = 0; k < n; k += (len << 1)) { 475 for(int pos = k; pos < k + len; pos++) { 476 int l = a[pos]; 477 int r = mul(a[pos + len], w[st][pos - k]); 478 479 a[pos] = norm(l + r); 480 a[pos + len] = norm(l - r); 481 } 482 } 483 } 484 485 if(inverse) { 486 int in = inv(n); 487 forn(i, n) 488 a[i] = mul(a[i], in); 489 reverse(a + 1, a + n); 490 } 491 } 492 493 int aa[N], bb[N], cc[N]; 494 495 inline vector<int> multiply(const vector<int> a, const vector<int> b) { 496 int ln = 1; 497 while(ln < (sz(a) + sz(b))) 498 ln <<= 1; 499 500 forn(i, ln) 501 aa[i] = (i < sz(a) ? a[i] : 0); 502 503 forn(i, ln) 504 bb[i] = (i < sz(b) ? b[i] : 0); 505 506 fft(aa, ln, false); 507 fft(bb, ln, false); 508 509 forn(i, ln) 510 cc[i] = mul(aa[i], bb[i]); 511 512 fft(cc, ln, true); 513 514 vector<int> c(ln, 0); 515 forn(i, sz(c)) 516 c[i] = cc[i]; 517 518 while(sz(c) > 1 && c.back() == 0) 519 c.pop_back(); 520 return c; 521 } 522 523 int n, k, a[11]; 524 525 inline bool read() { 526 if(!(cin >> n >> k)) 527 return false; 528 forn(i, k) 529 cin >> a[i]; 530 return true; 531 } 532 533 inline void solve() { 534 sort(a, a + k); 535 536 vector<int> ans(1, 1); 537 vector<int> f(10, 0); 538 forn(i, k) 539 f[a[i]] = 1; 540 541 precalc(); 542 543 int pw = n / 2; 544 while(pw > 0) { 545 if(pw & 1) 546 ans = multiply(ans, f); 547 f = multiply(f, f); 548 pw >>= 1; 549 } 550 551 int res = 0; 552 forn(i, sz(ans)) 553 res = norm(res + mul(ans[i], ans[i])); 554 cout << res << endl; 555 } 556 557 int main() { 558 #ifdef _DEBUG 559 freopen("input.txt", "r", stdin); 560 int tt = clock(); 561 #endif 562 cout << fixed << setprecision(15); 563 564 if(read()) { 565 solve(); 566 567 #ifdef _DEBUG 568 cerr << "TIME = " << clock() - tt << endl; 569 tt = clock(); 570 #endif 571 } 572 return 0; 573 } 574 ``` 575 576 **Solution 2 (BledDest)** 577 578 ``` 579 #include<bits/stdc++.h> 580 581 using namespace std; 582 583 const int LOGN = 21; 584 const int N = (1 << LOGN); 585 const int MOD = 998244353; 586 const int g = 3; 587 588 #define forn(i, n) for(int i = 0; i < int(n); i++) 589 590 inline int mul(int a, int b) 591 { 592 return (a * 1ll * b) % MOD; 593 } 594 595 inline int norm(int a) 596 { 597 while(a >= MOD) 598 a -= MOD; 599 while(a < 0) 600 a += MOD; 601 return a; 602 } 603 604 inline int binPow(int a, int k) 605 { 606 int ans = 1; 607 while(k > 0) 608 { 609 if(k & 1) 610 ans = mul(ans, a); 611 a = mul(a, a); 612 k >>= 1; 613 } 614 return ans; 615 } 616 617 inline int inv(int a) 618 { 619 return binPow(a, MOD - 2); 620 } 621 622 vector<int> w[LOGN]; 623 vector<int> iw[LOGN]; 624 vector<int> rv[LOGN]; 625 626 void precalc() 627 { 628 int wb = binPow(g, (MOD - 1) / (1 << LOGN)); 629 630 for(int st = 0; st < LOGN; st++) 631 { 632 w[st].assign(1 << st, 1); 633 iw[st].assign(1 << st, 1); 634 635 int bw = binPow(wb, 1 << (LOGN - st - 1)); 636 int ibw = inv(bw); 637 638 int cw = 1; 639 int icw = 1; 640 641 for(int k = 0; k < (1 << st); k++) 642 { 643 w[st][k] = cw; 644 iw[st][k] = icw; 645 646 cw = mul(cw, bw); 647 icw = mul(icw, ibw); 648 } 649 650 rv[st].assign(1 << st, 0); 651 652 if(st == 0) 653 { 654 rv[st][0] = 0; 655 continue; 656 } 657 int h = (1 << (st - 1)); 658 for(int k = 0; k < (1 << st); k++) 659 rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h); 660 } 661 } 662 663 inline void fft(int a[N], int n, int ln, bool inverse) 664 { 665 for(int i = 0; i < n; i++) 666 { 667 int ni = rv[ln][i]; 668 if(i < ni) 669 swap(a[i], a[ni]); 670 } 671 672 for(int st = 0; (1 << st) < n; st++) 673 { 674 int len = (1 << st); 675 for(int k = 0; k < n; k += (len << 1)) 676 { 677 for(int pos = k; pos < k + len; pos++) 678 { 679 int l = a[pos]; 680 int r = mul(a[pos + len], (inverse ? iw[st][pos - k] : w[st][pos - k])); 681 682 a[pos] = norm(l + r); 683 a[pos + len] = norm(l - r); 684 } 685 } 686 } 687 688 if(inverse) 689 { 690 int in = inv(n); 691 for(int i = 0; i < n; i++) 692 a[i] = mul(a[i], in); 693 } 694 } 695 696 int aa[N], bb[N], cc[N]; 697 698 inline void multiply(int a[N], int sza, int b[N], int szb, int c[N], int &szc) 699 { 700 int n = 1, ln = 0; 701 while(n < (sza + szb)) 702 n <<= 1, ln++; 703 for(int i = 0; i < n; i++) 704 aa[i] = (i < sza ? a[i] : 0); 705 for(int i = 0; i < n; i++) 706 bb[i] = (i < szb ? b[i] : 0); 707 708 fft(aa, n, ln, false); 709 fft(bb, n, ln, false); 710 711 for(int i = 0; i < n; i++) 712 cc[i] = mul(aa[i], bb[i]); 713 714 fft(cc, n, ln, true); 715 716 szc = n; 717 for(int i = 0; i < n; i++) 718 c[i] = cc[i]; 719 } 720 721 vector<int> T[N]; 722 723 int a[N]; 724 int b[N]; 725 int c[N]; 726 727 #define sz(a) (int(a.size())) 728 729 int main() 730 { 731 precalc(); 732 int n, k; 733 scanf("%d %d", &n, &k); 734 for(int i = 0; i < k; i++) 735 { 736 int x; 737 scanf("%d", &x); 738 a[x] = 1; 739 } 740 int nn = 1, ln = 0; 741 int nw = (n * 5) + 1; 742 while(nn < nw) 743 { 744 nn *= 2; 745 ln++; 746 } 747 fft(a, nn, ln, false); 748 forn(i, nn) 749 a[i] = binPow(a[i], n / 2); 750 fft(a, nn, ln, true); 751 int ans = 0; 752 forn(i, nn) 753 ans = norm(ans + binPow(a[i], 2)); 754 printf("%d\n", ans); 755 return 0; 756 } 757 ```