1778.md (17374B)
1 Source: https://codeforces.com/blog/entry/112149 2 3 [1778A - Flip Flop Sum](/contest/1778/problem/A "Codeforces Round 848 (Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Code** 10 11 ``` 12 #include <bits/stdc++.h> 13 using namespace std; 14 15 const int sz = 1e5 + 10; 16 int ara[sz]; 17 18 int main() 19 { 20 int t; 21 scanf("%d", &t); 22 23 while(t--) { 24 int n; 25 scanf("%d", &n); 26 27 int sum = 0; 28 29 for(int i = 1; i <= n; i++) { 30 scanf("%d", &ara[i]); 31 sum += ara[i]; 32 } 33 34 int ans = -1e9; 35 36 for(int i = 1; i < n; i++) { 37 if(ara[i] == ara[i+1]) { 38 if(ara[i] == 1) ans = max(ans, sum-4); 39 else ans = max(ans, sum+4); 40 } 41 else 42 ans = max(ans, sum); 43 } 44 45 printf("%d\n", ans); 46 } 47 48 return 0; 49 } 50 ``` 51 52 [1778B - The Forbidden Permutation](/contest/1778/problem/B "Codeforces Round 848 (Div. 2)") 53 54 **Tutorial** 55 56 Tutorial is loading... 57 58 **Code** 59 60 ``` 61 #include <bits/stdc++.h> 62 using namespace std; 63 64 const int sz = 1e5+10; 65 int p[sz], a[sz], pos[sz]; 66 67 int main() 68 { 69 int t; 70 scanf("%d", &t); 71 72 while(t--) { 73 int n, m, d; 74 scanf("%d %d %d", &n, &m, &d); 75 76 for(int i = 1; i <= n; i++) { 77 scanf("%d", &p[i]); 78 pos[ p[i] ] = i; 79 } 80 81 for(int i = 1; i <= m; i++) { 82 scanf("%d", &a[i]); 83 } 84 85 int ans = 1e9; 86 87 for(int i = 1; i < m; i++) { 88 if(pos[a[i+1]] <= pos[a[i]] || pos[a[i+1]]-pos[a[i]] > d) { 89 ans = 0; 90 break; 91 } 92 93 ans = min(ans, pos[a[i+1]] - pos[a[i]]); 94 95 int dist = pos[a[i+1]]-pos[a[i]]; 96 97 int swapNeed = d-dist+1; 98 int swapPossible = (pos[a[i]]-1) + (n - pos[a[i+1]]); 99 if(swapPossible >= swapNeed) ans = min(ans, swapNeed); 100 } 101 102 printf("%d\n", ans); 103 } 104 105 return 0; 106 } 107 ``` 108 109 [1778C - Flexible String](/contest/1778/problem/C "Codeforces Round 848 (Div. 2)") 110 111 **Tutorial** 112 113 Tutorial is loading... 114 115 **Code** 116 117 ``` 118 #include <bits/stdc++.h> 119 using namespace std; 120 121 #define ll long long 122 #define pb push_back 123 #define EL '\n' 124 #define fastio std::ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 125 126 string a, b; 127 string char_list; 128 bool mark[26]; 129 ll ans, k; 130 131 ll count_matching_pair() 132 { 133 ll tot_pair = 0, match_count = 0; 134 135 for(ll i = 0; i < a.size(); i++) { 136 if(a[i] == b[i] || mark[ a[i]-'a' ]) 137 match_count++; 138 else { 139 tot_pair += match_count*(match_count+1)/2; 140 match_count = 0; 141 } 142 } 143 tot_pair += match_count*(match_count+1)/2; 144 145 return tot_pair; 146 } 147 148 void solve(ll pos, ll cnt) 149 { 150 if(cnt > k) return; 151 152 if(pos == char_list.size()) { 153 if(cnt == k) ans = max(ans, count_matching_pair()); 154 return; 155 } 156 157 solve(pos+1, cnt); 158 159 mark[ char_list[pos]-'a' ] = 1; 160 solve(pos+1, cnt+1); 161 mark[ char_list[pos]-'a' ] = 0; 162 } 163 164 int main() 165 { 166 fastio; 167 ll t; 168 cin >> t; 169 170 while(t--) { 171 ll n; cin >> n >> k; 172 cin >> a >> b; 173 174 unordered_set <char> unq; 175 for(auto &ch : a) unq.insert(ch); 176 177 char_list.clear(); 178 for(auto &x : unq) char_list.pb(x); 179 180 k = min(k, (ll)unq.size()); 181 memset(mark, 0, sizeof mark); 182 ans = 0; 183 solve(0, 0); 184 185 cout << ans << EL; 186 } 187 188 return 0; 189 } 190 ``` 191 192 [1778D - Flexible String Revisit](/contest/1778/problem/D "Codeforces Round 848 (Div. 2)") 193 194 **Tutorial** 195 196 ### [1778D - Flexible String Revisit](/contest/1778/problem/D "Codeforces Round 848 (Div. 2)") 197 198 Let $k$ be the number of indices where the characters between two strings are different and $f(x)$ be the expected number of moves to make two strings equal given that the strings have $x$ differences. We have to find the value of $f(k)$. 199 200 For all $x$ where $1 \leq x \leq n-1$, 201 202 $ \begin{align} f(x) = \frac{x}{n} \cdot [1 + f(x-1)] + \frac{n-x}{n} \cdot [1 + f(x+1)]\\ or,~~~ f(x) = 1 + \frac{x}{n}\cdot f(x-1) + \frac{n-x}{n} \cdot f(x+1) \end{align} $ 203 204 Now, $f(0) = 0$ and $f(1) = 1 + \frac{n-1}{n}f(2)$. 205 206 We can represent any $f(i)$ in the form $f(i) = a_i + b_i \cdot f(i+1)$. 207 208 Let, $a_{1} = 1$ and $b_{1} = \frac{n-1}{n}$. So, we can write $f(1) = a_{1} + b_{1}\cdot f(2)$. 209 210 When $1 \lt i \lt n$, $f(i) = 1 + \frac{i}{n} \cdot f(i-1) + \frac{n-i}{n} \cdot f(i+1)$. We can substitute the value of $f(i-1)$ with $a_{i-1} + b_{i-1}\cdot f(i)$ and calculate the value of $f(i)$. Thus we can get the value of $a_i$ and $b_i$ using the value of $a_{i-1}$ and $b_{i-1}$ by considering $a_1$ and $b_1$ as the base case. 211 212 We get, $a_{i} = \frac{n+i\cdot a_{i-1}}{n-i\cdot b_{i-1}}$ and $b_{i} = \frac{n-i}{n-i \cdot b_{i-1}}$ for $2 \leq i \leq n$. 213 214 **Calculation** 215 216 Substituting $f(i-1) = a_{i-1} + b_{i-1}\cdot f(i)$, 217 218 $ \begin{align} f(i) & = 1 + \frac{i}{n} \cdot [a_{i-1} + b_{i-1}\cdot f(i)] + \frac{n-i}{n} \cdot f(i+1)\\ & = 1 + \frac{i}{n}\cdot a_{i-1} + \frac{i}{n} \cdot b_{i-1} \cdot f(i) + \frac{n-i}{n} \cdot f(i+1)\\ & = \frac{1+\frac{i}{n}\cdot a_{i-1}}{1-\frac{i}{n}\cdot b_{i-1}} + \frac{n-i}{n-i \cdot b_{i-1}}f(i+1)\\ & = \frac{n+i\cdot a_{i-1}}{n-i\cdot b_{i-1}} + \frac{n-i}{n-i \cdot b_{i-1}}f(i+1)\\ & = a_{i} + b_{i} \cdot f(i+1) \end{align} $ 219 220 So, $a_{i} = \frac{n+i\cdot a_{i-1}}{n-i\cdot b_{i-1}}$ and $b_{i} = \frac{n-i}{n-i \cdot b_{i-1}}$ for $2 \leq i \leq n$. 221 222 Similarly, $f(n) = 1+f(n-1)$. 223 224 We can represent any $f(i)$ in the form $f(i) = c_i + d_i \cdot f(i-1)$. 225 226 Let, $c_{n} = 1$ and $d_{n} = 1$. So, we can write $f(n) = c_{n} + d_{n}\cdot f(n-1)$. 227 228 When $1 \lt i \lt n$, $f(i) = 1 + \frac{i}{n} \cdot f(i-1) + \frac{n-i}{n} \cdot f(i+1)$. We can substitute the value of $f(i+1)$ with $c_{i+1} + d_{i+1}\cdot f(i)$ and calculate the value of $f(i)$. Thus we can get the value of $c_i$ and $d_i$ using the value of $c_{i+1}$ and $d_{i+1}$ by considering $c_n$ and $d_n$ as the base case. 229 230 We get, $c_{i} = \frac{n+(n-i)\cdot c_{i+1}}{n-(n-i)\cdot d_{i+1}}$ and $d_{i} = \frac{i}{n-(n-i) \cdot d_{i+1}}$. 231 232 **Calculation** 233 234 Substituting $f(i+1) = c_{i+1} + d_{i+1}\cdot f(i)$, 235 236 $ \begin{align} f(i) & = 1 + \frac{i}{n} \cdot f(i-1) + \frac{n-i}{n} \cdot [c_{i+1} + d_{i+1}\cdot f(i)]\\ & = 1 + \frac{i}{n}\cdot f(i-1) + \frac{n-i}{n} \cdot c_{i+1} + \frac{n-i}{n} \cdot d_{i+1} \cdot f(i)\\ & = \frac{1+\frac{n-i}{n}\cdot c_{i+1}}{1-\frac{n-i}{n}\cdot d_{i+1}} + \frac{i}{n-(n-i) \cdot d_{i+1}}f(i-1)\\ & = \frac{n+(n-i)\cdot c_{i+1}}{n-(n-i)\cdot d_{i+1}} + \frac{i}{n-(n-i) \cdot d_{i+1}}f(i-1)\\ & = c_{i} + d_{i} \cdot f(i-1) \end{align} $ 237 238 So, $c_{i} = \frac{n+(n-i)\cdot c_{i+1}}{n-(n-i)\cdot d_{i+1}}$ and $d_{i} = \frac{i}{n-(n-i) \cdot d_{i+1}}$. 239 240 Now, $f(i) = c_i + d_i \cdot f(i-1)$ and $f(i-1) = a_{i-1} + b_{i-1} \cdot f(i)$. By solving these two equations, we find that $f(i) = \frac{c_i+d_i \cdot a_{i-1}}{1-d_i \cdot b_{i-1}}$. 241 242 Time Complexity: $\mathcal{O}(n\cdot \log m)$. 243 244 **Alternative Solution** 245 246 After some calculations, it can be shown that $f(1) = 2^n - 1$. Now we know $f(0) = 0$ and $f(1) = 2^n - 1$. 247 248 From the relation between $f(i)$, $f(i-1)$ and $f(i-2)$, we can write $f(i) = \frac{n\cdot f(i-1) - i \cdot f(i-2) - n}{n-i+1}$. 249 250 **Code** 251 252 ``` 253 #include <bits/stdc++.h> 254 using namespace std; 255 256 #define mod 998244353 257 #define N 1000005 258 259 template<int MOD> 260 struct ModInt { 261 unsigned x; 262 ModInt() : x(0) { } 263 ModInt(signed sig) : x(sig) { } 264 ModInt(signed long long sig) : x(sig%MOD) { } 265 int get() const { return (int)x; } 266 ModInt pow(ll p) { ModInt res = 1, a = *this; while (p) { if (p & 1) res *= a; a *= a; p >>= 1; } return res; } 267 268 ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; } 269 ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; } 270 ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; } 271 ModInt &operator/=(ModInt that) { return (*this) *= that.pow(MOD - 2); } 272 273 ModInt operator+(ModInt that) const { return ModInt(*this) += that; } 274 ModInt operator-(ModInt that) const { return ModInt(*this) -= that; } 275 ModInt operator*(ModInt that) const { return ModInt(*this) *= that; } 276 ModInt operator/(ModInt that) const { return ModInt(*this) /= that; } 277 bool operator<(ModInt that) const { return x < that.x; } 278 friend ostream& operator<<(ostream &os, ModInt a) { os << a.x; return os; } 279 }; 280 typedef ModInt<998244353> mint; 281 282 mint a[N], b[N], c[N], d[N]; 283 284 285 int main(){ 286 ios::sync_with_stdio(false); 287 cin.tie(0); 288 289 int t; 290 cin >> t; 291 while(t--){ 292 int n; 293 cin >> n; 294 295 string s1, s2; 296 cin >> s1 >> s2; 297 298 int diff = 0; 299 for(int i = 0; i < n; i++){ 300 diff += s1[i]!=s2[i]; 301 } 302 303 c[n] = 1, d[n] = 1, a[1] = 1, b[1] = ((mint) n-1)/n; 304 305 for(int i = 2; i <= n; i++){ 306 a[i] = ((mint) n + a[i-1]*i)/((mint) n - b[i-1]*i); 307 b[i] = ((mint) n-i)/((mint) n - b[i-1]*i); 308 } 309 310 for(int i = n-1; i >= 1; i--){ 311 c[i] = ((mint) n + c[i+1]*(n-i))/((mint) n - d[i+1]*(n-i)); 312 d[i] = (mint) i / ((mint) n - d[i+1]*(n-i)); 313 } 314 315 mint ans = (c[diff]+d[diff]*a[diff-1])/((mint) 1 - d[diff]*b[diff-1]); 316 317 cout << ans << endl; 318 } 319 320 return 0; 321 } 322 ``` 323 324 **Alternative Code** 325 326 ``` 327 #include <bits/stdc++.h> 328 using namespace std; 329 330 #define ll long long 331 332 template<int MOD> 333 struct ModInt { 334 unsigned x; 335 ModInt() : x(0) { } 336 ModInt(signed sig) : x(sig) { } 337 ModInt(signed long long sig) : x(sig%MOD) { } 338 int get() const { return (int)x; } 339 ModInt pow(ll p) { ModInt res = 1, a = *this; while (p) { if (p & 1) res *= a; a *= a; p >>= 1; } return res; } 340 341 ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; } 342 ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; } 343 ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; } 344 ModInt &operator/=(ModInt that) { return (*this) *= that.pow(MOD - 2); } 345 346 ModInt operator+(ModInt that) const { return ModInt(*this) += that; } 347 ModInt operator-(ModInt that) const { return ModInt(*this) -= that; } 348 ModInt operator*(ModInt that) const { return ModInt(*this) *= that; } 349 ModInt operator/(ModInt that) const { return ModInt(*this) /= that; } 350 bool operator<(ModInt that) const { return x < that.x; } 351 friend ostream& operator<<(ostream &os, ModInt a) { os << a.x; return os; } 352 }; 353 typedef ModInt<998244353> mint; 354 355 int main(){ 356 ios::sync_with_stdio(false); 357 cin.tie(0); 358 cout.tie(0); 359 360 mint two = 2; 361 362 int t; 363 cin >> t; 364 while(t--){ 365 int n; 366 cin >> n; 367 368 string a, b; 369 cin >> a >> b; 370 371 int cnt = 0; 372 for(int i = 0; i < n; i++){ 373 if(a[i]!=b[i]) cnt++; 374 } 375 376 vector<mint> dp(n+2); 377 dp[0] = two.pow(n); 378 dp[1] = dp[0]-1; 379 dp[0] = 0; 380 381 for(long long i = 2; i < n; i++){ 382 mint x = i-1; 383 x /= n; 384 dp[i] = (dp[i-1]-x*dp[i-2]-1)*n/(n-i+1); 385 } 386 387 dp[n] = dp[n-1]+1; 388 389 cout << dp[cnt] << '\n'; 390 } 391 392 return 0; 393 } 394 ``` 395 396 [1778E - The Tree Has Fallen!](/contest/1778/problem/E "Codeforces Round 848 (Div. 2)") 397 398 **Tutorial** 399 400 Tutorial is loading... 401 402 **Code** 403 404 ``` 405 #include <bits/stdc++.h> 406 using namespace std; 407 408 #define ll long long 409 #define pb push_back 410 #define nn '\n' 411 #define fastio std::ios_base::sync_with_stdio(false); cin.tie(NULL); 412 413 const int sz = 2e5 + 10, d = 30; 414 vector <int> g[sz], Tree[sz]; 415 int a[sz], discover_time[sz], finish_time[sz], nodeOf[sz], tim; 416 417 struct BASIS { 418 int basis[d]; 419 int sz; 420 421 void init() { 422 for(int i = 0; i < d; i++) basis[i] = 0; 423 sz = 0; 424 } 425 426 void insertVector(int mask) { 427 for (int i = d-1; i >= 0; i--) { 428 if (((mask>>i)&1) == 0) continue; 429 430 if (!basis[i]) { 431 basis[i] = mask; 432 ++sz; 433 return; 434 } 435 mask ^= basis[i]; 436 } 437 } 438 439 void mergeBasis(const BASIS &from) { 440 for(int i = d-1; i >= 0; i--) { 441 if(!from.basis[i]) 442 continue; 443 444 insertVector(from.basis[i]); 445 } 446 } 447 448 int findMax() { 449 int ret = 0; 450 for(int i = d-1; i >= 0; i--) { 451 if(!basis[i] || (ret>>i & 1)) 452 continue; 453 454 ret ^= basis[i]; 455 } 456 return ret; 457 } 458 } in[sz], out, pre[sz], suf[sz]; 459 460 void in_dfs(int u, int p) 461 { 462 in[u].insertVector(a[u]); 463 discover_time[u] = ++tim; 464 nodeOf[tim] = u; 465 466 for(auto &v : g[u]) { 467 if(v == p) 468 continue; 469 470 Tree[u].pb(v); 471 in_dfs(v, u); 472 473 in[u].mergeBasis(in[v]); 474 } 475 finish_time[u] = tim; 476 } 477 478 inline bool in_subtree(int sub_root, int v) 479 { 480 return discover_time[sub_root] <= discover_time[v] 481 && finish_time[sub_root] >= finish_time[v]; 482 } 483 484 int findChildOnPath(int sub_root, int v) 485 { 486 int lo = 0, hi = (int)Tree[sub_root].size()-1; 487 488 while(lo <= hi) { 489 int mid = lo+hi>>1, node = Tree[sub_root][mid]; 490 491 if(finish_time[node] < discover_time[v]) 492 lo = mid + 1; 493 else if(discover_time[node] > discover_time[v]) 494 hi= mid - 1; 495 else 496 return node; 497 } 498 } 499 500 void init(int n) { 501 502 for(int i = 0; i <= n+5; i++) { 503 g[i].clear(), Tree[i].clear(); 504 in[i].init(); 505 pre[i].init(), suf[i].init(); 506 } 507 tim = 0; 508 } 509 510 int main() 511 { 512 fastio; 513 514 int t; 515 cin >> t; 516 517 while(t--) { 518 int n; cin >> n; 519 520 init(n); 521 522 for(int i = 1; i <= n; i++) cin >> a[i]; 523 524 for(int i = 1; i < n; i++) { 525 int u, v; 526 cin >> u >> v; 527 g[u].pb(v); g[v].pb(u); 528 } 529 530 in_dfs(1, -1); 531 532 for(int i = 1; i <= n; i++) { 533 pre[i].insertVector(a[ nodeOf[i] ]); 534 pre[i].mergeBasis(pre[i-1]); 535 } 536 537 for(int i = n; i >= 1; i--) { 538 suf[i].insertVector(a[ nodeOf[i] ]); 539 suf[i].mergeBasis(suf[i+1]); 540 } 541 542 int q; cin >> q; 543 544 while(q--) { 545 int root, v; 546 cin >> root >> v; 547 548 if(root == v) { 549 cout << in[1].findMax() << nn; 550 } 551 else if(in_subtree(v, root)) { 552 int child = findChildOnPath(v, root); 553 554 out.init(); 555 out.mergeBasis(pre[discover_time[child]-1]); 556 out.mergeBasis(suf[finish_time[child]+1]); 557 cout << out.findMax() << nn; 558 } 559 else 560 cout << in[v].findMax() << nn; 561 } 562 } 563 564 return 0; 565 } 566 ``` 567 568 [1778F - Maximizing Root](/contest/1778/problem/F "Codeforces Round 848 (Div. 2)") 569 570 **Tutorial** 571 572 Tutorial is loading... 573 574 **Code** 575 576 ``` 577 #include <bits/stdc++.h> 578 using namespace std; 579 580 const int N = 100005; 581 const int mod = 998244353; 582 583 int val[N]; 584 vector<int> g[N]; 585 vector<int> divisor[N]; 586 int subtree_gcd[N], par[N]; 587 588 int dp[N][1003]; 589 int gcdd[1003][1003]; 590 591 inline long long ___gcd(long long a, long long b){ 592 if(gcdd[a][b]) return gcdd[a][b]; 593 594 return gcdd[a][b] = __gcd(a, b); 595 } 596 597 inline long long lcm(long long a, long long b){ 598 return (a/___gcd(a, b))*b; 599 } 600 601 void dfs(int u, int p){ 602 par[u] = p; 603 subtree_gcd[u] = val[u]; 604 for(int v: g[u]){ 605 if(v==p) continue; 606 dfs(v, u); 607 subtree_gcd[u] = ___gcd(subtree_gcd[u], subtree_gcd[v]); 608 } 609 } 610 611 612 int solve(int u, int d, int p){ 613 if(subtree_gcd[u]%d==0) return 0; 614 if((val[u]*val[u])%d) return (1<<30); 615 616 617 if(dp[u][d]!=-1) return dp[u][d]; 618 619 long long req = d/___gcd(d, subtree_gcd[u]); 620 621 long long res = (1<<30); 622 for(int div: divisor[val[u]]){ 623 if((val[u]*div)%d==0 && d%div==0){ 624 long long r = 1; 625 for(int v: g[u]){ 626 if(v==p) continue; 627 r += solve(v, lcm(d/div, div), u); 628 } 629 res = min(res, r); 630 } 631 } 632 633 return dp[u][d] = min(res, (1LL<<30)); 634 } 635 636 int main(){ 637 ios::sync_with_stdio(false); 638 cin.tie(nullptr); 639 640 for(int i = 2; i < 1001; i++){ 641 for(int j = i; j < 1001; j+=i){ 642 divisor[j].push_back(i); 643 } 644 } 645 646 int t; 647 cin >> t; 648 649 while(t--){ 650 int n, k; 651 cin >> n >> k; 652 653 for(int i = 0; i <= n; i++){ 654 g[i].clear(); 655 } 656 657 for(int i = 1; i <= n; i++){ 658 cin >> val[i]; 659 } 660 661 for(int i = 0; i <= n; i++){ 662 for(int d: divisor[val[1]]){ 663 dp[i][d] = -1; 664 } 665 } 666 667 for(int i = 0; i < n-1; i++){ 668 int u, v; 669 cin >> u >> v; 670 g[u].push_back(v); 671 g[v].push_back(u); 672 } 673 674 dfs(1, 0); 675 676 int ans = val[1]; 677 678 for(int d: divisor[val[1]]){ 679 int req = 0; 680 int f = 1; 681 for(int v: g[1]){ 682 int x = solve(v, d, par[v]); 683 if(x>n) f = 0; 684 req += x; 685 } 686 687 if(!f) continue; 688 689 req++; 690 if(req<=k){ 691 ans = max(ans, val[1]*d); 692 } 693 } 694 695 cout << ans << "\n"; 696 } 697 698 return 0; 699 } 700 ```