1671.md (11901B)
1 Source: https://codeforces.com/blog/entry/102181 2 3 [1671A - String Building](/contest/1671/problem/A "Educational Codeforces Round 127 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 t = int(input()) 15 for i in range(t): 16 s = input() 17 ans = True 18 n = len(s) 19 for j in range(n): 20 if (j == 0 or s[j] != s[j - 1]) and (j == n - 1 or s[j] != s[j + 1]): 21 ans = False 22 print('YES' if ans else 'NO') 23 ``` 24 25 [1671B - Consecutive Points Segment](/contest/1671/problem/B "Educational Codeforces Round 127 (Rated for Div. 2)") 26 27 Idea: [vovuh](/profile/vovuh "Master vovuh") 28 29 **Tutorial** 30 31 Tutorial is loading... 32 33 **Solution (vovuh)** 34 35 ``` 36 for i in range(int(input())): 37 n = int(input()) 38 x = list(map(int, input().split())) 39 print('YES' if x[-1] - x[0] - n + 1 <= 2 else 'NO') 40 ``` 41 42 [1671C - Dolce Vita](/contest/1671/problem/C "Educational Codeforces Round 127 (Rated for Div. 2)") 43 44 Idea: [vovuh](/profile/vovuh "Master vovuh") and [BledDest](/profile/BledDest "International Grandmaster BledDest") 45 46 **Tutorial** 47 48 Tutorial is loading... 49 50 **Solution (adedalic)** 51 52 ``` 53 fun main() { 54 repeat(readLine()!!.toInt()) { 55 val (n, x) = readLine()!!.split(' ').map { it.toInt() } 56 val a = readLine()!!.split(' ').map { it.toInt() }.sorted() 57 58 var sum = a.sumOf { it.toLong() } 59 var prevDay = -1L 60 var ans = 0L 61 for (i in n - 1 downTo 0) { 62 val curDay = if (x - sum >= 0) (x - sum) / (i + 1) else -1 63 ans += (i + 1) * (curDay - prevDay) 64 prevDay = curDay 65 sum -= a[i] 66 } 67 println(ans) 68 } 69 } 70 ``` 71 72 [1671D - Insert a Progression](/contest/1671/problem/D "Educational Codeforces Round 127 (Rated for Div. 2)") 73 74 Idea: [vovuh](/profile/vovuh "Master vovuh") and [BledDest](/profile/BledDest "International Grandmaster BledDest") 75 76 **Tutorial** 77 78 Tutorial is loading... 79 80 **Solution (awoo)** 81 82 ``` 83 #include <bits/stdc++.h> 84 85 #define forn(i, n) for (int i = 0; i < int(n); i++) 86 87 using namespace std; 88 89 int main() { 90 int t; 91 scanf("%d", &t); 92 forn(_, t){ 93 int n, x; 94 scanf("%d%d", &n, &x); 95 vector<int> a(n); 96 forn(i, n) scanf("%d", &a[i]); 97 long long ans = 1e18; 98 long long cur = 0; 99 forn(i, n - 1){ 100 cur += abs(a[i] - a[i + 1]); 101 } 102 forn(_, 2){ 103 long long mn = abs(a[0] - 1); 104 ans = min(ans, cur + abs(a[0] - x) + (x - 1)); 105 forn(i, n - 1){ 106 ans = min(ans, cur + mn - abs(a[i] - a[i + 1]) + abs(a[i] - x) + abs(a[i + 1] - x)); 107 ans = min(ans, cur - abs(a[i] - a[i + 1]) + abs(a[i] - x) + abs(a[i + 1] - 1) + (x - 1)); 108 mn = min(mn, 0ll - abs(a[i] - a[i + 1]) + abs(a[i] - 1) + abs(a[i + 1] - 1)); 109 } 110 ans = min(ans, cur + mn + abs(a.back() - x)); 111 reverse(a.begin(), a.end()); 112 } 113 printf("%lld\n", ans); 114 } 115 return 0; 116 } 117 ``` 118 119 [1671E - Preorder](/contest/1671/problem/E "Educational Codeforces Round 127 (Rated for Div. 2)") 120 121 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 122 123 **Tutorial** 124 125 Tutorial is loading... 126 127 **Solution (BledDest)** 128 129 ``` 130 #include <bits/stdc++.h> 131 132 using namespace std; 133 134 mt19937 rnd(42); 135 136 const int MOD = 998244353; 137 const int K = 3; 138 139 int add(int x, int y, int mod = MOD) 140 { 141 x += y; 142 while(x >= mod) x -= mod; 143 while(x < 0) x += mod; 144 return x; 145 } 146 147 int sub(int x, int y, int mod = MOD) 148 { 149 return add(x, -y, mod); 150 } 151 152 int mul(int x, int y, int mod = MOD) 153 { 154 return (x * 1ll * y) % mod; 155 } 156 157 int binpow(int x, int y, int mod = MOD) 158 { 159 int z = 1; 160 while(y > 0) 161 { 162 if(y % 2 == 1) z = mul(z, x, mod); 163 y /= 2; 164 x = mul(x, x, mod); 165 } 166 return z; 167 } 168 169 bool prime(int x) 170 { 171 for(int i = 2; i * 1ll * i <= x; i++) 172 if(x % i == 0) 173 return false; 174 return true; 175 } 176 177 int get_base() 178 { 179 int x = rnd() % 10000 + 4444; 180 while(!prime(x)) x++; 181 return x; 182 } 183 184 int get_modulo() 185 { 186 int x = rnd() % int(1e9) + int(1e8); 187 while(!prime(x)) x++; 188 return x; 189 } 190 191 typedef array<int, K> hs; 192 193 hs base, modulo; 194 195 void generate_hs() 196 { 197 for(int i = 0; i < K; i++) 198 { 199 base[i] = get_base(); 200 modulo[i] = get_modulo(); 201 } 202 } 203 204 hs operator+(const hs& a, const hs& b) 205 { 206 hs c; 207 for(int i = 0; i < K; i++) 208 { 209 c[i] = add(a[i], b[i], modulo[i]); 210 } 211 return c; 212 } 213 214 hs operator-(const hs& a, const hs& b) 215 { 216 hs c; 217 for(int i = 0; i < K; i++) 218 { 219 c[i] = sub(a[i], b[i], modulo[i]); 220 } 221 return c; 222 } 223 224 hs operator*(const hs& a, const hs& b) 225 { 226 hs c; 227 for(int i = 0; i < K; i++) 228 { 229 c[i] = mul(a[i], b[i], modulo[i]); 230 } 231 return c; 232 } 233 234 hs operator^(const hs& a, const hs& b) 235 { 236 hs c; 237 for(int i = 0; i < K; i++) 238 { 239 c[i] = binpow(a[i], b[i], modulo[i]); 240 } 241 return c; 242 } 243 244 hs char_hash(char c) 245 { 246 hs res; 247 for(int i = 0; i < K; i++) 248 res[i] = c - 'A' + 1; 249 return res; 250 } 251 252 const int N = 18; 253 const int V = 1 << N; 254 string s; 255 char buf[V + 43]; 256 int n; 257 int ans[V + 43]; 258 hs vertex_hash[V + 43]; 259 260 bool is_leaf(int x) 261 { 262 return (x * 2 + 1) >= ((1 << n) - 1); 263 } 264 265 void rec(int x) 266 { 267 vertex_hash[x] = char_hash(s[x]); 268 ans[x] = 1; 269 if(is_leaf(x)) 270 { 271 return; 272 } 273 rec(x * 2 + 1); 274 rec(x * 2 + 2); 275 vertex_hash[x] = vertex_hash[x] + (base ^ vertex_hash[2 * x + 1]) + (base ^ vertex_hash[2 * x + 2]); 276 ans[x] = mul(ans[2 * x + 1], ans[2 * x + 2]); 277 if(vertex_hash[2 * x + 1] != vertex_hash[2 * x + 2]) 278 ans[x] = mul(ans[x], 2); 279 } 280 281 int main() 282 { 283 generate_hs(); 284 scanf("%d", &n); 285 scanf("%s", buf); 286 s = buf; 287 rec(0); 288 cout << ans[0] << endl; 289 } 290 ``` 291 292 [1671F - Permutation Counting](/contest/1671/problem/F "Educational Codeforces Round 127 (Rated for Div. 2)") 293 294 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 295 296 **Tutorial** 297 298 Tutorial is loading... 299 300 **Solution (BledDest)** 301 302 ``` 303 #include <bits/stdc++.h> 304 305 using namespace std; 306 307 const int K = 13; 308 const int MOD = 998244353; 309 310 int n, k, x; 311 312 int cnt[K][K][K]; 313 int dp[K][2 * K][K][K]; 314 315 int add(int x, int y) 316 { 317 x += y; 318 while(x >= MOD) x -= MOD; 319 while(x < 0) x += MOD; 320 return x; 321 } 322 323 int sub(int x, int y) 324 { 325 return add(x, -y); 326 } 327 328 int mul(int x, int y) 329 { 330 return (x * 1ll * y) % MOD; 331 } 332 333 int binpow(int x, int y) 334 { 335 int z = 1; 336 while(y > 0) 337 { 338 if(y % 2 == 1) z = mul(z, x); 339 y /= 2; 340 x = mul(x, x); 341 } 342 return z; 343 } 344 345 void precalc() 346 { 347 cnt[2][1][1] = 1; 348 cnt[3][1][2] = 2; 349 cnt[3][2][3] = 1; 350 cnt[4][1][3] = 3; 351 cnt[4][1][4] = 1; 352 cnt[4][2][3] = 1; 353 cnt[4][2][4] = 4; 354 cnt[4][2][5] = 3; 355 cnt[4][3][6] = 1; 356 cnt[5][1][4] = 4; 357 cnt[5][1][5] = 2; 358 cnt[5][1][6] = 2; 359 cnt[5][2][4] = 4; 360 cnt[5][2][5] = 12; 361 cnt[5][2][6] = 12; 362 cnt[5][2][7] = 9; 363 cnt[5][2][8] = 3; 364 cnt[5][3][5] = 2; 365 cnt[5][3][6] = 4; 366 cnt[5][3][7] = 6; 367 cnt[5][3][8] = 6; 368 cnt[5][3][9] = 4; 369 cnt[5][4][10] = 1; 370 cnt[6][1][5] = 5; 371 cnt[6][1][6] = 3; 372 cnt[6][1][7] = 4; 373 cnt[6][1][8] = 3; 374 cnt[6][1][9] = 1; 375 cnt[6][2][5] = 10; 376 cnt[6][2][6] = 28; 377 cnt[6][2][7] = 35; 378 cnt[6][2][8] = 35; 379 cnt[6][2][9] = 30; 380 cnt[6][2][10] = 17; 381 cnt[6][2][11] = 8; 382 cnt[6][3][5] = 1; 383 cnt[6][3][6] = 13; 384 cnt[6][3][7] = 29; 385 cnt[6][3][8] = 41; 386 cnt[6][3][9] = 44; 387 cnt[6][3][10] = 45; 388 cnt[6][3][11] = 30; 389 cnt[6][4][7] = 1; 390 cnt[6][4][8] = 4; 391 cnt[6][4][9] = 7; 392 cnt[6][4][10] = 7; 393 cnt[6][4][11] = 11; 394 cnt[7][1][6] = 6; 395 cnt[7][1][7] = 4; 396 cnt[7][1][8] = 6; 397 cnt[7][1][9] = 6; 398 cnt[7][1][10] = 6; 399 cnt[7][1][11] = 2; 400 cnt[7][2][6] = 20; 401 cnt[7][2][7] = 55; 402 cnt[7][2][8] = 80; 403 cnt[7][2][9] = 95; 404 cnt[7][2][10] = 101; 405 cnt[7][2][11] = 94; 406 cnt[7][3][6] = 6; 407 cnt[7][3][7] = 50; 408 cnt[7][3][8] = 118; 409 cnt[7][3][9] = 186; 410 cnt[7][3][10] = 230; 411 cnt[7][3][11] = 260; 412 cnt[7][4][7] = 3; 413 cnt[7][4][8] = 18; 414 cnt[7][4][9] = 48; 415 cnt[7][4][10] = 85; 416 cnt[7][4][11] = 113; 417 cnt[7][5][10] = 2; 418 cnt[7][5][11] = 4; 419 cnt[8][1][7] = 7; 420 cnt[8][1][8] = 5; 421 cnt[8][1][9] = 8; 422 cnt[8][1][10] = 9; 423 cnt[8][1][11] = 11; 424 cnt[8][2][7] = 35; 425 cnt[8][2][8] = 96; 426 cnt[8][2][9] = 155; 427 cnt[8][2][10] = 207; 428 cnt[8][2][11] = 250; 429 cnt[8][3][7] = 21; 430 cnt[8][3][8] = 145; 431 cnt[8][3][9] = 358; 432 cnt[8][3][10] = 616; 433 cnt[8][3][11] = 859; 434 cnt[8][4][7] = 1; 435 cnt[8][4][8] = 26; 436 cnt[8][4][9] = 124; 437 cnt[8][4][10] = 313; 438 cnt[8][4][11] = 567; 439 cnt[8][5][9] = 3; 440 cnt[8][5][10] = 16; 441 cnt[8][5][11] = 53; 442 cnt[9][1][8] = 8; 443 cnt[9][1][9] = 6; 444 cnt[9][1][10] = 10; 445 cnt[9][1][11] = 12; 446 cnt[9][2][8] = 56; 447 cnt[9][2][9] = 154; 448 cnt[9][2][10] = 268; 449 cnt[9][2][11] = 389; 450 cnt[9][3][8] = 56; 451 cnt[9][3][9] = 350; 452 cnt[9][3][10] = 898; 453 cnt[9][3][11] = 1654; 454 cnt[9][4][8] = 8; 455 cnt[9][4][9] = 126; 456 cnt[9][4][10] = 552; 457 cnt[9][4][11] = 1404; 458 cnt[9][5][9] = 4; 459 cnt[9][5][10] = 48; 460 cnt[9][5][11] = 204; 461 cnt[9][6][11] = 1; 462 cnt[10][1][9] = 9; 463 cnt[10][1][10] = 7; 464 cnt[10][1][11] = 12; 465 cnt[10][2][9] = 84; 466 cnt[10][2][10] = 232; 467 cnt[10][2][11] = 427; 468 cnt[10][3][9] = 126; 469 cnt[10][3][10] = 742; 470 cnt[10][3][11] = 1967; 471 cnt[10][4][9] = 36; 472 cnt[10][4][10] = 448; 473 cnt[10][4][11] = 1887; 474 cnt[10][5][9] = 1; 475 cnt[10][5][10] = 43; 476 cnt[10][5][11] = 357; 477 cnt[10][6][11] = 6; 478 cnt[11][1][10] = 10; 479 cnt[11][1][11] = 8; 480 cnt[11][2][10] = 120; 481 cnt[11][2][11] = 333; 482 cnt[11][3][10] = 252; 483 cnt[11][3][11] = 1428; 484 cnt[11][4][10] = 120; 485 cnt[11][4][11] = 1302; 486 cnt[11][5][10] = 10; 487 cnt[11][5][11] = 252; 488 cnt[11][6][11] = 5; 489 cnt[12][1][11] = 11; 490 cnt[12][2][11] = 165; 491 cnt[12][3][11] = 462; 492 cnt[12][4][11] = 330; 493 cnt[12][5][11] = 55; 494 cnt[12][6][11] = 1; 495 } 496 497 int inv[K]; 498 499 int C(int n, int k) 500 { 501 if(n < 0 || n < k || k < 0) return 0; 502 int res = 1; 503 for(int i = n; i > n - k; i--) 504 res = mul(res, i); 505 for(int i = 1; i <= k; i++) 506 res = mul(res, inv[i]); 507 return res; 508 } 509 510 void prepare() 511 { 512 for(int i = 1; i < K; i++) 513 inv[i] = binpow(i, MOD - 2); 514 precalc(); 515 dp[0][0][0][0] = 1; 516 for(int i = 0; i < K; i++) 517 for(int j = 0; j < 2 * K; j++) 518 for(int a = 0; a < K - 2; a++) 519 for(int b = 0; b < K - 2; b++) 520 { 521 if(dp[i][j][a][b] == 0) continue; 522 for(int add_cnt = 2; add_cnt < K; add_cnt++) 523 for(int add_desc = 1; add_desc <= K - 2; add_desc++) 524 for(int add_inv = 1; add_inv <= K - 2; add_inv++) 525 { 526 if(j + add_cnt >= 2 * K || a + add_desc > K - 2 || b + add_inv > K - 2) continue; 527 int& nw = dp[i + 1][j + add_cnt][a + add_desc][b + add_inv]; 528 nw = add(nw, mul(dp[i][j][a][b], cnt[add_cnt][add_desc][add_inv])); 529 } 530 } 531 } 532 533 void solve() 534 { 535 scanf("%d %d %d", &n, &k, &x); 536 if(k == 0 && x == 0) 537 { 538 puts("1"); 539 return; 540 } 541 int ans = 0; 542 for(int i = 1; i < K; i++) 543 for(int j = 1; j < 2 * K; j++) 544 if(dp[i][j][x][k] != 0) 545 { 546 ans = add(ans, mul(dp[i][j][x][k], C(n - j + i, i))); 547 } 548 printf("%d\n", ans); 549 } 550 551 int main() 552 { 553 prepare(); 554 int t; 555 scanf("%d", &t); 556 for(int i = 0; i < t; i++) 557 solve(); 558 } 559 ```