711.md (11687B)
1 Source: https://codeforces.com/blog/entry/46830 2 3 Here are the editorials for all the problems. Hope you enjoyed them and found them interesting! 4 5 Tutorial is loading... 6 7 **Code** 8 9 ``` 10 #include <bits/stdc++.h> 11 #include <ext/pb_ds/assoc_container.hpp> 12 #include <ext/pb_ds/tree_policy.hpp> 13 14 using namespace std; 15 using namespace __gnu_pbds; 16 17 #define fi first 18 #define se second 19 #define mp make_pair 20 #define pb push_back 21 #define fbo find_by_order 22 #define ook order_of_key 23 24 typedef long long ll; 25 typedef pair<int,int> ii; 26 typedef vector<int> vi; 27 typedef long double ld; 28 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 29 typedef set<int>::iterator sit; 30 typedef map<int,int>::iterator mit; 31 typedef vector<int>::iterator vit; 32 33 const int INF = 1e9 + 7; 34 const int MOD = 1e9 + 7; 35 const int N = 1000; 36 char bus[N][5]; 37 38 void printbus(int n) 39 { 40 for(int i = 0; i < n; i++) 41 { 42 for(int j = 0; j < 5; j++) 43 { 44 cout << bus[i][j]; 45 } 46 cout << '\n'; 47 } 48 } 49 50 void yes() 51 { 52 cout << "YES" << '\n'; 53 } 54 55 void no() 56 { 57 cout << "NO" << '\n'; 58 } 59 60 int main() 61 { 62 ios_base::sync_with_stdio(0); cin.tie(0); 63 int n; cin >> n; 64 for(int i = 0; i < n; i++) 65 { 66 for(int j = 0; j < 5; j++) 67 { 68 cin >> bus[i][j]; 69 } 70 } 71 bool possible = false; 72 for(int i = 0; i < n; i++) 73 { 74 for(int j = 0; j < 2; j++) 75 { 76 if(bus[i][j*3] == 'O' && bus[i][j*3+1] == 'O') 77 { 78 bus[i][j*3] = '+'; 79 bus[i][j*3+1] = '+'; 80 possible = true; 81 break; 82 } 83 } 84 if(possible) break; 85 } 86 if(!possible) 87 { 88 no(); 89 return 0; 90 } 91 else 92 { 93 yes(); 94 printbus(n); 95 return 0; 96 } 97 return 0; 98 } 99 ``` 100 101 Tutorial is loading... 102 103 **Code** 104 105 ``` 106 #include <bits/stdc++.h> 107 #include <ext/pb_ds/assoc_container.hpp> 108 #include <ext/pb_ds/tree_policy.hpp> 109 110 using namespace std; 111 using namespace __gnu_pbds; 112 113 #define fi first 114 #define se second 115 #define mp make_pair 116 #define pb push_back 117 #define fbo find_by_order 118 #define ook order_of_key 119 120 typedef long long ll; 121 typedef pair<int,int> ii; 122 typedef vector<int> vi; 123 typedef long double ld; 124 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 125 typedef set<int>::iterator sit; 126 typedef map<int,int>::iterator mit; 127 typedef vector<int>::iterator vit; 128 129 const int INF = 1e9 + 7; 130 const int MOD = 1e9 + 7; 131 const int LG = 20; 132 133 ll a[1001][1001]; 134 ll r[1001]; //row sum 135 ll c[1001]; //column sum 136 int n; 137 138 void no() 139 { 140 cout << -1 << '\n'; 141 } 142 143 int main() 144 { 145 ios_base::sync_with_stdio(0); cin.tie(0); 146 cin >> n; 147 int x, y; ll diagonal1 = 0; ll diagonal2 = 0; 148 for(int i = 0; i < n; i++) 149 { 150 for(int j = 0; j < n; j++) 151 { 152 cin >> a[i][j]; 153 if(a[i][j] == 0) 154 { 155 x = i; y = j; 156 } 157 else 158 { 159 r[i] += a[i][j]; 160 c[j] += a[i][j]; 161 if(i == j) 162 { 163 diagonal1 += a[i][j]; 164 } 165 if(i + j == n - 1) 166 { 167 diagonal2 += a[i][j]; 168 } 169 } 170 } 171 } 172 if(n == 1) 173 { 174 cout << 1 << '\n'; 175 return 0; 176 } 177 ll commonsum = r[0]; 178 if(x == 0) commonsum = r[1]; 179 //cout << commonsum << '\n'; 180 ll rowsum = -1; ll colsum = -1; ll d1sum = -1; ll d2sum = -1; 181 for(int i = 0; i < n; i++) 182 { 183 if(i != x) 184 { 185 if(r[i] != commonsum) 186 { 187 no(); 188 return 0; 189 } 190 } 191 else 192 { 193 rowsum = r[i]; 194 } 195 } 196 for(int i = 0; i < n; i++) 197 { 198 if(i != y) 199 { 200 if(c[i] != commonsum) 201 { 202 no(); return 0; 203 } 204 } 205 else 206 { 207 colsum = c[i]; 208 } 209 } 210 bool isdiagonal1 = false; bool isdiagonal2 = false; 211 if(x == y) isdiagonal1 = true; 212 if(x + y == n - 1) isdiagonal2 = true; 213 if(!isdiagonal1) 214 { 215 if(diagonal1 != commonsum) 216 { 217 no(); 218 return 0; 219 } 220 } 221 else 222 { 223 d1sum = diagonal1; 224 } 225 if(!isdiagonal2) 226 { 227 if(diagonal2 != commonsum) 228 { 229 no(); 230 return 0; 231 } 232 } 233 else 234 { 235 d2sum = diagonal2; 236 } 237 if(rowsum == colsum) 238 { 239 if(isdiagonal1 && d1sum != rowsum) 240 { 241 no(); 242 return 0; 243 } 244 if(isdiagonal2 && d2sum != rowsum) 245 { 246 no(); 247 return 0; 248 } 249 ll value = commonsum - rowsum; 250 if(value > 0) 251 { 252 cout << value << '\n'; 253 return 0; 254 } 255 else 256 { 257 no(); 258 return 0; 259 } 260 } 261 else 262 { 263 no(); 264 return 0; 265 } 266 } 267 ``` 268 269 Tutorial is loading... 270 271 **Code (O(nkm^2))** 272 273 ``` 274 #include <bits/stdc++.h> 275 #include <ext/pb_ds/assoc_container.hpp> 276 #include <ext/pb_ds/tree_policy.hpp> 277 278 using namespace std; 279 using namespace __gnu_pbds; 280 281 #define fi first 282 #define se second 283 #define mp make_pair 284 #define pb push_back 285 #define fbo find_by_order 286 #define ook order_of_key 287 288 typedef long long ll; 289 typedef pair<int,int> ii; 290 typedef vector<int> vi; 291 typedef long double ld; 292 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 293 typedef set<int>::iterator sit; 294 typedef map<int,int>::iterator mit; 295 typedef vector<int>::iterator vit; 296 297 const int N = 101; 298 const int MOD = 1e9 + 7; 299 const ll INF = ll(1e18); 300 301 ll dp[N][N][N]; 302 int c[N]; 303 ll cost[N][N]; 304 305 int main() 306 { 307 ios_base::sync_with_stdio(0); cin.tie(0); 308 int n, m, k; cin >> n >> m >> k; 309 for(int i = 1; i <= n; i++) 310 { 311 cin >> c[i]; 312 } 313 for(int i = 0; i <= n; i++) 314 { 315 for(int j = 0; j <= k; j++) 316 { 317 for(int a = 0; a <= m; a++) 318 { 319 dp[i][j][a] = INF; 320 } 321 } 322 } 323 for(int i = 1; i <= n; i++) 324 { 325 for(int j = 1; j <= m; j++) 326 { 327 cin >> cost[i][j]; 328 } 329 } 330 if(c[1] == 0) 331 { 332 for(int i = 1; i <= m; i++) 333 { 334 dp[1][1][i] = cost[1][i]; 335 } 336 } 337 else 338 { 339 dp[1][1][c[1]] = 0; 340 } 341 for(int i = 2; i <= n; i++) 342 { 343 for(int j = 1; j <= k; j++) 344 { 345 if(c[i] == 0) 346 { 347 for(int a = 1; a <= m; a++) 348 { 349 dp[i][j][a] = min(dp[i][j][a], dp[i-1][j][a] + cost[i][a]); 350 for(int b = 1; b <= m; b++) 351 { 352 if(b != a) dp[i][j][a] = min(dp[i][j][a], dp[i-1][j-1][b] + cost[i][a]); 353 } 354 } 355 } 356 else 357 { 358 dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j][c[i]]); 359 for(int b = 1; b <= m; b++) 360 { 361 if(b != c[i]) dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j-1][b]); 362 } 363 //cout << i << ' ' << j << ' ' << c[i] << ' ' << dp[i][j][c[i]] << '\n'; 364 } 365 } 366 } 367 ll ans = INF; 368 for(int i = 1; i <= m; i++) 369 { 370 ans = min(ans, dp[n][k][i]); 371 } 372 if(ans >= INF) ans = -1; 373 cout << ans; 374 } 375 ``` 376 377 **Code (O(nkm))** 378 379 ``` 380 #include <bits/stdc++.h> 381 #include <ext/pb_ds/assoc_container.hpp> 382 #include <ext/pb_ds/tree_policy.hpp> 383 384 using namespace std; 385 using namespace __gnu_pbds; 386 387 #define fi first 388 #define se second 389 #define mp make_pair 390 #define pb push_back 391 #define fbo find_by_order 392 #define ook order_of_key 393 394 typedef long long ll; 395 typedef pair<int,int> ii; 396 typedef vector<int> vi; 397 typedef long double ld; 398 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 399 typedef set<int>::iterator sit; 400 typedef map<int,int>::iterator mit; 401 typedef vector<int>::iterator vit; 402 403 const int N = 101; 404 const int MOD = 1e9 + 7; 405 const ll INF = ll(1e18); 406 407 ll dp[N][N][N]; 408 int c[N]; 409 ll cost[N][N]; 410 ll idx[N][N]; 411 ll m1[N][N]; 412 ll m2[N][N]; 413 414 int main() 415 { 416 ios_base::sync_with_stdio(0); cin.tie(0); 417 int n, m, k; cin >> n >> m >> k; 418 for(int i = 1; i <= n; i++) 419 { 420 cin >> c[i]; 421 } 422 for(int i = 0; i <= n; i++) 423 { 424 for(int j = 0; j <= k; j++) 425 { 426 m1[i][j] = INF; m2[i][j] = INF; idx[i][j] = -1; 427 for(int a = 0; a <= m; a++) 428 { 429 dp[i][j][a] = INF; 430 } 431 } 432 } 433 for(int i = 1; i <= n; i++) 434 { 435 for(int j = 1; j <= m; j++) 436 { 437 cin >> cost[i][j]; 438 } 439 } 440 if(c[1] == 0) 441 { 442 for(int i = 1; i <= m; i++) 443 { 444 dp[1][1][i] = cost[1][i]; 445 if(dp[1][1][i] <= m1[1][1]) 446 { 447 if(dp[1][1][i] == m1[1][1]) 448 { 449 idx[1][1] = -2; 450 } 451 else 452 { 453 idx[1][1] = i; 454 } 455 m2[1][1] = m1[1][1]; 456 m1[1][1] = dp[1][1][i]; 457 } 458 else if(dp[1][1][i] <= m2[1][1]) 459 { 460 m2[1][1] = dp[1][1][i]; 461 } 462 } 463 } 464 else 465 { 466 dp[1][1][c[1]] = 0; 467 m1[1][1] = 0; idx[1][1] = c[1]; 468 } 469 for(int i = 2; i <= n; i++) 470 { 471 for(int j = 1; j <= k; j++) 472 { 473 if(c[i] == 0) 474 { 475 for(int a = 1; a <= m; a++) 476 { 477 dp[i][j][a] = min(dp[i][j][a], dp[i-1][j][a] + cost[i][a]); 478 ll tmp = INF; 479 if(a == idx[i-1][j-1]) 480 { 481 tmp = m2[i-1][j-1]; 482 } 483 else 484 { 485 tmp = m1[i-1][j-1]; 486 } 487 dp[i][j][a] = min(dp[i][j][a], tmp + cost[i][a]); 488 } 489 } 490 else 491 { 492 dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j][c[i]]); 493 for(int b = 1; b <= m; b++) 494 { 495 if(b != c[i]) dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j-1][b]); 496 } 497 //cout << i << ' ' << j << ' ' << c[i] << ' ' << dp[i][j][c[i]] << '\n'; 498 } 499 for(int a = 1; a <= m; a++) 500 { 501 if(dp[i][j][a] <= m1[i][j]) 502 { 503 if(dp[i][j][a] == m1[i][j]) 504 { 505 idx[i][j] = -2; 506 } 507 else 508 { 509 idx[i][j] = a; 510 } 511 m2[i][j] = m1[i][j]; 512 m1[i][j] = dp[i][j][a]; 513 } 514 else if(dp[i][j][a] <= m2[i][j]) 515 { 516 m2[i][j] = dp[i][j][a]; 517 } 518 } 519 } 520 } 521 ll ans = INF; 522 for(int i = 1; i <= m; i++) 523 { 524 ans = min(ans, dp[n][k][i]); 525 } 526 if(ans >= INF) ans = -1; 527 cout << ans; 528 } 529 ``` 530 531 Tutorial is loading... 532 533 **Code** 534 535 ``` 536 #include <bits/stdc++.h> 537 #include <ext/pb_ds/assoc_container.hpp> 538 #include <ext/pb_ds/tree_policy.hpp> 539 540 using namespace std; 541 using namespace __gnu_pbds; 542 543 #define fi first 544 #define se second 545 #define mp make_pair 546 #define pb push_back 547 #define fbo find_by_order 548 #define ook order_of_key 549 550 typedef long long ll; 551 typedef pair<int,int> ii; 552 typedef vector<int> vi; 553 typedef long double ld; 554 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 555 typedef set<int>::iterator sit; 556 typedef map<int,int>::iterator mit; 557 typedef vector<int>::iterator vit; 558 559 const int INF = 1e9 + 7; 560 const int MOD = 1e9 + 7; 561 const int N = 1e6 + 3; 562 563 int a[N]; 564 int visited[N]; 565 ll ans; 566 vector<int> cycles; 567 ll dp[N]; 568 int cyclecnt; 569 570 void dfs2(int u) 571 { 572 cycles[cyclecnt]++; 573 visited[u] = 3; 574 if(visited[a[u]] == 3) return ; 575 dfs2(a[u]); 576 } 577 578 void dfs(int u) 579 { 580 visited[u] = 2; 581 if(visited[a[u]] == 0) 582 { 583 dfs(a[u]); 584 } 585 else if(visited[a[u]] == 1) 586 { 587 visited[u] = 1; 588 return ; 589 } 590 else 591 { 592 cycles.pb(0); 593 dfs2(u); 594 cyclecnt++; 595 } 596 visited[u] = 1; 597 } 598 599 int main() 600 { 601 //ios_base::sync_with_stdio(0); cin.tie(0); 602 int n; scanf("%d", &n); 603 for(int i = 1; i <= n; i++) 604 { 605 scanf("%d", a + i); 606 } 607 dp[0] = 1; 608 for(int i = 1; i <= n; i++) 609 { 610 dp[i] = (dp[i-1]*2LL)%MOD; 611 } 612 ans = 1; 613 memset(visited, 0, sizeof(visited)); 614 for(int i = 1; i <= n; i++) 615 { 616 if(visited[i] == 0) 617 { 618 dfs(i); 619 } 620 } 621 ll cnt = n; 622 for(int i = 0; i < cycles.size(); i++) 623 { 624 cnt -= cycles[i]; 625 ans = (ans*(dp[cycles[i]]-2+MOD))%MOD; 626 } 627 ans = (ans*dp[cnt])%MOD; 628 if(ans < 0) ans += MOD; 629 int ans2 = ans; 630 printf("%d\n", ans2); 631 return 0; 632 } 633 ``` 634 635 Tutorial is loading... 636 637 **Code** 638 639 ``` 640 #include <bits/stdc++.h> 641 642 using namespace std; 643 644 typedef long long ll; 645 typedef vector<int> vi; 646 647 const int MOD = 1e6 + 3; 648 649 ll power(ll base, ll exp) 650 { 651 ll ans = 1; 652 while(exp) 653 { 654 if(exp&1) ans = (ans*base)%MOD; 655 base = (base*base)%MOD; 656 exp>>=1; 657 } 658 return ans; 659 } 660 661 int main() 662 { 663 ios_base::sync_with_stdio(false); cin.tie(0); 664 ll n, k; 665 cin >> n >> k; 666 if(n <= 63 && k > (1LL<<n)) 667 { 668 cout << 1 << " " << 1; 669 return 0; 670 } 671 ll v2 = 0; 672 int digits = __builtin_popcountll(k - 1); 673 v2 = k - 1 - digits; 674 ll ntmp = n % (MOD - 1); 675 if(ntmp < 0) ntmp += (MOD - 1); 676 ll ktmp = k % (MOD - 1); 677 if(ktmp < 0) ktmp += (MOD - 1); 678 ll v2tmp = v2 % (MOD - 1); 679 if(v2tmp < 0) v2tmp += (MOD - 1); 680 ll exponent = ntmp*(ktmp - 1) - v2tmp; 681 exponent %= (MOD - 1); 682 if(exponent < 0) exponent += MOD - 1; 683 ll denom = power(2, exponent); 684 ll numpart = 0; 685 if(k - 1 >= MOD) 686 { 687 numpart = 0; 688 } 689 else 690 { 691 ll prod = 1; 692 ll ntmp2 = power(2, ntmp); 693 prod = power(2, v2tmp); 694 prod = power(prod, MOD - 2); 695 if(prod < 0) prod += MOD; 696 for(ll y = 1; y <= k - 1; y++) 697 { 698 prod = (prod * (ntmp2 - y))%MOD; 699 } 700 numpart = prod; 701 } 702 ll num = (denom - numpart)%MOD; 703 num %= MOD; denom %= MOD; 704 if(num < 0) num += MOD; 705 if(denom < 0) denom += MOD; 706 cout << num << " " << denom; 707 return 0; 708 } 709 ```