2182.md (10120B)
1 Source: https://codeforces.com/blog/entry/149733 2 3 [2182A - New Year String](/contest/2182/problem/A "Educational Codeforces Round 186 (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 n = int(input()) 17 s = input() 18 if '2025' in s and not '2026' in s: 19 print(1) 20 else: 21 print(0) 22 ``` 23 24 [2182B - New Year Cake](/contest/2182/problem/B "Educational Codeforces Round 186 (Rated for Div. 2)") 25 26 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 27 28 **Tutorial** 29 30 Tutorial is loading... 31 32 **Solution (BledDest)** 33 34 ``` 35 t = int(input()) 36 for i in range(t): 37 a, b = map(int, input().split()) 38 if a < b: 39 a, b = b, a 40 x, y = 0, 0 41 ans = 0 42 cur = 1 43 while True: 44 x, y = y + cur, x 45 if x <= a and y <= b: 46 ans += 1 47 cur *= 2 48 else: 49 break 50 print(ans) 51 ``` 52 53 [2182C - Production of Snowmen](/contest/2182/problem/C "Educational Codeforces Round 186 (Rated for Div. 2)") 54 55 Idea: [Roms](/profile/Roms "Master Roms") 56 57 **Tutorial** 58 59 Tutorial is loading... 60 61 **Solution (BledDest)** 62 63 ``` 64 def good(x, y, n, k): 65 ans = True 66 for i in range(n): 67 if x[i] <= y[(i + k) % n]: 68 ans = False 69 return ans 70 71 t = int(input()) 72 for _ in range(t): 73 n = int(input()) 74 a = list(map(int, input().split())) 75 b = list(map(int, input().split())) 76 c = list(map(int, input().split())) 77 k1, k2 = 0, 0 78 for i in range(n): 79 if good(b, a, n, i): 80 k1 += 1 81 if good(c, b, n, i): 82 k2 += 1 83 print(k1 * k2 * n) 84 ``` 85 86 [2182D - Christmas Tree Decoration](/contest/2182/problem/D "Educational Codeforces Round 186 (Rated for Div. 2)") 87 88 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 89 90 **Tutorial** 91 92 Tutorial is loading... 93 94 **Solution (Neon)** 95 96 ``` 97 #include <bits/stdc++.h> 98 99 using namespace std; 100 101 const int N = 55; 102 const int MOD = 998244353; 103 104 int mul(int x, int y) { 105 return x * 1LL * y % MOD; 106 } 107 108 int binpow(int x, int y) { 109 int z = 1; 110 while (y > 0) { 111 if (y & 1) z = mul(z, x); 112 x = mul(x, x); 113 y >>= 1; 114 } 115 return z; 116 } 117 118 int main() { 119 vector<int> f(N, 1); 120 for (int i = 1; i < N; ++i) 121 f[i] = (f[i - 1] * 1LL * i) % MOD; 122 123 int t; 124 cin >> t; 125 while (t--) { 126 int n; 127 cin >> n; 128 vector<int> a(n + 1); 129 for (int &x : a) cin >> x; 130 int k = accumulate(a.begin(), a.end(), 0) / n; 131 int z = 0, bad = 0; 132 for (int i = 1; i <= n; ++i) { 133 int x = min(a[i], k); 134 a[i] -= x; 135 a[0] -= k - x; 136 z += a[i] == 0; 137 bad |= a[i] > 1 || a[0] < 0; 138 } 139 bad |= a[0] > z; 140 int ans = bad ? 0 : f[z]; 141 if (!bad) { 142 ans = mul(ans, f[n - z + a[0]]); 143 ans = mul(ans, binpow(f[a[0]], MOD - 2)); 144 } 145 cout << ans << '\n'; 146 } 147 } 148 ``` 149 150 [2182E - New Year's Gifts](/contest/2182/problem/E "Educational Codeforces Round 186 (Rated for Div. 2)") 151 152 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 153 154 **Tutorial** 155 156 Tutorial is loading... 157 158 **Solution (Neon)** 159 160 ``` 161 #include <bits/stdc++.h> 162 163 using namespace std; 164 165 void solve() { 166 int n, m; 167 long long k; 168 cin >> n >> m >> k; 169 vector<vector<int>> ev(m); 170 for (int i = 0; i < m; ++i) { 171 int x; cin >> x; 172 ev[x - 1].push_back(-1); 173 } 174 for (int i = 0; i < n; ++i) { 175 int x, y, z; 176 cin >> x >> y >> z; 177 ev[x - 1].push_back(z - y); 178 k -= y; 179 } 180 int ans = 0; 181 multiset<int> s; 182 for (int i = 0; i < m; ++i) { 183 reverse(ev[i].begin(), ev[i].end()); 184 for (int x : ev[i]) { 185 if (x == -1) { 186 if (!s.empty()) { 187 s.erase(--s.end()); 188 ++ans; 189 } 190 } else { 191 s.insert(x); 192 } 193 } 194 } 195 while (!s.empty() && *s.begin() <= k) { 196 k -= *s.begin(); 197 s.erase(s.begin()); 198 ++ans; 199 } 200 cout << ans << '\n'; 201 } 202 203 int main() { 204 ios::sync_with_stdio(false); cin.tie(0); 205 int t; 206 cin >> t; 207 while (t--) solve(); 208 } 209 ``` 210 211 [2182F1 - Christmas Reindeer (easy version)](/contest/2182/problem/F1 "Educational Codeforces Round 186 (Rated for Div. 2)") 212 213 [2182F2 - Christmas Reindeer (hard version)](/contest/2182/problem/F2 "Educational Codeforces Round 186 (Rated for Div. 2)") 214 215 Idea: [Roms](/profile/Roms "Master Roms") 216 217 **Tutorial** 218 219 Tutorial is loading... 220 221 **Solution (BledDest)** 222 223 ``` 224 #include<bits/stdc++.h> 225 226 using namespace std; 227 228 const int MOD = 998244353; 229 const int LOGN = 61; 230 231 int add(int x, int y) 232 { 233 x += y; 234 if(x >= MOD) x -= MOD; 235 if(x < 0) x += MOD; 236 return x; 237 } 238 239 int sub(int x, int y) 240 { 241 return add(x, -y); 242 } 243 244 int mul(int x, int y) 245 { 246 return (x * 1ll * y) % MOD; 247 } 248 249 int binpow(int x, int y) 250 { 251 int z = 1; 252 while(y > 0) 253 { 254 if(y % 2 == 1) z = mul(z, x); 255 x = mul(x, x); 256 y /= 2; 257 } 258 return z; 259 } 260 261 vector<int> get_required(long long x) 262 { 263 vector<int> ans(LOGN); 264 int cnt = 0; 265 for(int i = LOGN - 1; i >= 0; i--) 266 { 267 if((x >> i) & 1) 268 { 269 ans[i + cnt]++; 270 cnt++; 271 } 272 } 273 return ans; 274 } 275 276 void solve() 277 { 278 int n, m; 279 cin >> n >> m; 280 vector<int> freq(LOGN); 281 for(int i = 0; i < n; i++) 282 { 283 int x; 284 cin >> x; 285 freq[x]++; 286 } 287 288 int max_n = n + m + 111; 289 290 vector<int> fact(max_n, 1); 291 for(int i = 1; i < max_n; i++) 292 fact[i] = mul(fact[i - 1], i); 293 vector<int> inv_fact(max_n); 294 for(int i = 0; i < max_n; i++) 295 inv_fact[i] = binpow(fact[i], MOD - 2); 296 vector<int> pow2(max_n, 1); 297 for(int i = 1; i < max_n; i++) 298 pow2[i] = mul(pow2[i - 1], 2); 299 300 auto choose = [&](int x, int y) 301 { 302 if(x < y || x < 0 || y < 0) return 0; 303 return mul(fact[x], mul(inv_fact[y], inv_fact[x - y])); 304 }; 305 306 auto sum_greater = [&](int x, int y) 307 { 308 if(y >= x) return 0; 309 int ans = pow2[x]; 310 for(int i = 0; i <= y; i++) 311 ans = sub(ans, choose(x, i)); 312 return ans; 313 }; 314 315 for(int i = 0; i < m; i++) 316 { 317 int t; 318 long long x; 319 cin >> t >> x; 320 if(t == 1) 321 freq[x]++; 322 else if(t == 2) 323 freq[x]--; 324 else 325 { 326 auto req = get_required(x); 327 int ans = 0; 328 int cur = 1; 329 int cnt_less = 0; 330 for(int i = 0; i < LOGN; i++) cnt_less += freq[i]; 331 for(int i = LOGN - 1; i >= 0; i--) 332 { 333 cnt_less -= freq[i]; 334 ans = add(ans, mul(cur, mul(sum_greater(freq[i], req[i]), pow2[cnt_less]))); 335 cur = mul(cur, choose(freq[i], req[i])); 336 } 337 ans = add(ans, cur); 338 cout << ans << "\n"; 339 } 340 } 341 } 342 343 int main() 344 { 345 ios_base::sync_with_stdio(0); 346 cin.tie(0); 347 int t = 1; 348 //cin >> t; 349 for(int i = 0; i < t; i++) solve(); 350 } 351 ``` 352 353 [2182G - Short Garland](/contest/2182/problem/G "Educational Codeforces Round 186 (Rated for Div. 2)") 354 355 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 356 357 **Tutorial** 358 359 Tutorial is loading... 360 361 **Solution (awoo)** 362 363 ``` 364 #include <bits/stdc++.h> 365 366 #define forn(i, n) for (int i = 0; i < int(n); i++) 367 368 using namespace std; 369 370 const int MOD = 998244353; 371 372 int add(int a, int b){ 373 a += b; 374 if (a >= MOD) a -= MOD; 375 if (a < 0) a += MOD; 376 return a; 377 } 378 379 int mul(int a, int b){ 380 return a * 1ll * b % MOD; 381 } 382 383 int binpow(int a, int b){ 384 int res = 1; 385 while (b){ 386 if (b & 1) 387 res = mul(res, a); 388 a = mul(a, a); 389 b >>= 1; 390 } 391 return res; 392 } 393 394 int n, k; 395 vector<vector<int>> g; 396 397 struct dpar{ 398 vector<int> dp; 399 int ml, ad; 400 dpar(){ 401 ml = 1, ad = 0; 402 dp.clear(); 403 } 404 int& operator [](int k){ 405 return dp[max(0, int(dp.size()) - k - 1)]; 406 } 407 int get(int k){ 408 int x = dp[max(0, int(dp.size()) - k - 1)]; 409 return add(mul(x, ml), ad); 410 } 411 }; 412 413 vector<dpar> dp; 414 vector<int> fact; 415 416 void dfs(int v){ 417 int bst = -1; 418 vector<int> val; 419 for (int u : g[v]){ 420 dfs(u); 421 dp[u].dp.push_back(add(0, mul(binpow(dp[u].ml, MOD - 2), -dp[u].ad))); 422 if (bst == -1 || dp[u].dp.size() > dp[bst].dp.size()) 423 bst = u; 424 val.push_back(dp[u].get(k - 1)); 425 } 426 if (val.empty()){ 427 dp[v].dp.push_back(1); 428 return; 429 } 430 431 vector<int> pr(val.size() + 1, 1), su(val.size() + 1, 1); 432 forn(i, val.size()){ 433 pr[i + 1] = mul(pr[i], val[i]); 434 su[val.size() - i - 1] = mul(su[val.size() - i], val[val.size() - i - 1]); 435 } 436 437 swap(dp[v], dp[bst]); 438 { 439 int i = find(g[v].begin(), g[v].end(), bst) - g[v].begin(); 440 int cur = mul(fact[g[v].size() - 1], mul(pr[i], su[i + 1])); 441 if (cur == 0){ 442 int mx = 1; 443 for (int u : g[v]) mx = max(mx, int(dp[u].dp.size())); 444 dp[v].dp.assign(mx, 0); 445 dp[v].ml = 1, dp[v].ad = 0; 446 } 447 else{ 448 dp[v].ml = mul(dp[v].ml, cur); 449 dp[v].ad = mul(dp[v].ad, cur); 450 } 451 } 452 453 int rev = binpow(dp[v].ml, MOD - 2); 454 forn(i, g[v].size()){ 455 int u = g[v][i]; 456 if (u == bst) continue; 457 int cur = mul(fact[g[v].size() - 1], mul(pr[i], su[i + 1])); 458 int tot = mul(cur, dp[u].get(n)); 459 dp[v].ad = add(dp[v].ad, tot); 460 forn(j, dp[u].dp.size()){ 461 dp[v][j] = add(dp[v][j], -mul(rev, tot)); 462 dp[v][j] = add(dp[v][j], mul(mul(cur, dp[u].get(j)), rev)); 463 } 464 } 465 } 466 467 int main() { 468 cin.tie(0); 469 ios::sync_with_stdio(false); 470 int t; 471 cin >> t; 472 while (t--){ 473 cin >> n >> k; 474 g.assign(n, {}); 475 for (int i = 1; i < n; ++i){ 476 int p; 477 cin >> p; 478 --p; 479 g[p].push_back(i); 480 } 481 dp.assign(n, {}); 482 fact.resize(n + 1, 1); 483 for (int i = 1; i <= n; ++i) 484 fact[i] = mul(fact[i - 1], i); 485 dfs(0); 486 cout << dp[0].get(n) << '\n'; 487 } 488 return 0; 489 } 490 ```