1613.md (8746B)
1 Source: https://codeforces.com/blog/entry/97467 2 3 [1613A - Long Comparison](/contest/1613/problem/A "Educational Codeforces Round 118 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (awoo)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main(){ 19 int t; 20 cin >> t; 21 while (t--){ 22 long long x1, x2; 23 int p1, p2; 24 cin >> x1 >> p1 >> x2 >> p2; 25 int mn = min(p1, p2); 26 p1 -= mn; 27 p2 -= mn; 28 if (p1 >= 7) 29 cout << ">" << endl; 30 else if (p2 >= 7) 31 cout << "<" << endl; 32 else{ 33 for (int i = 0; i < p1; ++i) x1 *= 10; 34 for (int i = 0; i < p2; ++i) x2 *= 10; 35 if (x1 < x2) 36 cout << "<" << endl; 37 else if (x1 > x2) 38 cout << ">" << endl; 39 else 40 cout << "=" << endl; 41 } 42 } 43 } 44 ``` 45 46 [1613B - Absent Remainder](/contest/1613/problem/B "Educational Codeforces Round 118 (Rated for Div. 2)") 47 48 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 49 50 **Tutorial** 51 52 Tutorial is loading... 53 54 **Solution (Neon)** 55 56 ``` 57 #include <bits/stdc++.h> 58 59 using namespace std; 60 61 int main() { 62 int t; 63 cin >> t; 64 while (t--) { 65 int n; 66 cin >> n; 67 vector<int> a(n); 68 for (int &x : a) cin >> x; 69 int mn = *min_element(a.begin(), a.end()); 70 for (int i = 0, k = 0; k < n / 2; ++i) if (a[i] != mn) { 71 cout << a[i] << ' ' << mn << '\n'; 72 k += 1; 73 } 74 } 75 } 76 ``` 77 78 [1613C - Poisoned Dagger](/contest/1613/problem/C "Educational Codeforces Round 118 (Rated for Div. 2)") 79 80 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 81 82 **Tutorial** 83 84 Tutorial is loading... 85 86 **Solution (Neon)** 87 88 ``` 89 #include <bits/stdc++.h> 90 91 using namespace std; 92 93 using li = long long; 94 95 int main() { 96 int t; 97 cin >> t; 98 while (t--) { 99 int n; 100 li h; 101 cin >> n >> h; 102 vector<li> a(n); 103 for (li &x : a) cin >> x; 104 li l = 1, r = 1e18; 105 while (l <= r) { 106 li m = (l + r) / 2; 107 li sum = m; 108 for (int i = 0; i < n - 1; ++i) 109 sum += min(m, a[i + 1] - a[i]); 110 if (sum < h) l = m + 1; 111 else r = m - 1; 112 } 113 cout << r + 1 << '\n'; 114 } 115 } 116 ``` 117 118 [1613D - MEX Sequences](/contest/1613/problem/D "Educational Codeforces Round 118 (Rated for Div. 2)") 119 120 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 121 122 **Tutorial** 123 124 Tutorial is loading... 125 126 **Solution (Neon)** 127 128 ``` 129 #include <bits/stdc++.h> 130 131 using namespace std; 132 133 const int MOD = 998244353; 134 135 int add(int x, int y) { 136 x += y; 137 if (x >= MOD) x -= MOD; 138 return x; 139 } 140 141 int main() { 142 int t; 143 scanf("%d", &t); 144 while (t--) { 145 int n; 146 scanf("%d", &n); 147 vector<int> dp1(n + 2), dp2(n + 2); 148 dp1[0] = 1; 149 while (n--) { 150 int x; 151 scanf("%d", &x); 152 dp1[x + 1] = add(dp1[x + 1], dp1[x + 1]); 153 dp1[x + 1] = add(dp1[x + 1], dp1[x]); 154 if (x > 0) dp2[x - 1] = add(dp2[x - 1], dp2[x - 1]); 155 if (x > 0) dp2[x - 1] = add(dp2[x - 1], dp1[x - 1]); 156 dp2[x + 1] = add(dp2[x + 1], dp2[x + 1]); 157 } 158 int ans = 0; 159 for (int x : dp1) ans = add(ans, x); 160 for (int x : dp2) ans = add(ans, x); 161 printf("%d\n", add(ans, MOD - 1)); 162 } 163 } 164 ``` 165 166 [1613E - Crazy Robot](/contest/1613/problem/E "Educational Codeforces Round 118 (Rated for Div. 2)") 167 168 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 169 170 **Tutorial** 171 172 Tutorial is loading... 173 174 **Solution (awoo)** 175 176 ``` 177 #include <bits/stdc++.h> 178 179 #define forn(i, n) for (int i = 0; i < int(n); i++) 180 181 using namespace std; 182 183 struct cell{ 184 int x, y; 185 }; 186 187 int dx[] = {-1, 0, 1, 0}; 188 int dy[] = {0, 1, 0, -1}; 189 190 int main() { 191 int t; 192 cin >> t; 193 while (t--){ 194 int n, m; 195 cin >> n >> m; 196 vector<string> s(n); 197 int lx = -1, ly = -1; 198 forn(i, n){ 199 cin >> s[i]; 200 forn(j, m) if (s[i][j] == 'L'){ 201 lx = i; 202 ly = j; 203 } 204 } 205 auto in = [&](int x, int y){ 206 return 0 <= x && x < n && 0 <= y && y < m; 207 }; 208 vector<vector<int>> d(n, vector<int>(m, 0)); 209 forn(x, n) forn(y, m) if (s[x][y] == '.'){ 210 forn(i, 4){ 211 int nx = x + dx[i]; 212 int ny = y + dy[i]; 213 d[x][y] += in(nx, ny) && s[nx][ny] != '#'; 214 } 215 } 216 queue<cell> q; 217 vector<vector<char>> used(n, vector<char>(m, 0)); 218 q.push({lx, ly}); 219 used[lx][ly] = true; 220 while (!q.empty()){ 221 int x = q.front().x; 222 int y = q.front().y; 223 q.pop(); 224 forn(i, 4){ 225 int nx = x + dx[i]; 226 int ny = y + dy[i]; 227 if (!in(nx, ny) || s[nx][ny] == '#' || used[nx][ny]) continue; 228 --d[nx][ny]; 229 if (d[nx][ny] <= 1){ 230 used[nx][ny] = true; 231 q.push({nx, ny}); 232 } 233 } 234 } 235 forn(i, n){ 236 forn(j, m) if (s[i][j] == '.' && used[i][j]) 237 s[i][j] = '+'; 238 cout << s[i] << "\n"; 239 } 240 } 241 return 0; 242 } 243 ``` 244 245 [1613F - Tree Coloring](/contest/1613/problem/F "Educational Codeforces Round 118 (Rated for Div. 2)") 246 247 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 248 249 **Tutorial** 250 251 Tutorial is loading... 252 253 **Solution (BledDest)** 254 255 ``` 256 #include <bits/stdc++.h> 257 258 using namespace std; 259 260 #define forn(i, n) for (int i = 0; i < int(n); ++i) 261 #define fore(i, l, r) for (int i = int(l); i < int(r); ++i) 262 #define sz(a) int((a).size()) 263 264 const int MOD = 998244353; 265 266 struct Mint 267 { 268 int val; 269 270 bool operator==(const Mint& other) 271 { 272 return val == other.val; 273 } 274 275 Mint operator+(const Mint& other) 276 { 277 int res = val + other.val; 278 while(res >= MOD) res -= MOD; 279 while(res < 0) res += MOD; 280 return Mint(res); 281 } 282 283 Mint operator-(const Mint& other) 284 { 285 int res = val - other.val; 286 while(res >= MOD) res -= MOD; 287 while(res < 0) res += MOD; 288 return Mint(res); 289 } 290 291 Mint operator*(const Mint& other) 292 { 293 return Mint((val * 1ll * other.val) % MOD); 294 } 295 296 Mint pow(int y) 297 { 298 Mint z(1); 299 Mint x(val); 300 while(y > 0) 301 { 302 if(y % 2 == 1) z = z * x; 303 x = x * x; 304 y /= 2; 305 } 306 return z; 307 } 308 309 Mint operator/(const Mint& other) 310 { 311 return Mint(val) * Mint(other.val).pow(MOD - 2); 312 } 313 314 Mint() { 315 val = 0; 316 }; 317 Mint(int x) 318 { 319 while(x >= MOD) x -= MOD; 320 while(x < 0) x += MOD; 321 val = x; 322 }; 323 }; 324 325 ostream& operator<<(ostream& out, const Mint& x) 326 { 327 return out << x.val; 328 } 329 330 const int g = 3; 331 const int LOGN = 19; 332 333 vector<Mint> w[LOGN]; 334 vector<int> rv[LOGN]; 335 336 void prepare() { 337 Mint wb = Mint(g).pow((MOD - 1) / (1 << LOGN)); 338 forn(st, LOGN - 1) { 339 w[st].assign(1 << st, 1); 340 Mint bw = wb.pow(1 << (LOGN - st - 1)); 341 Mint cw = 1; 342 forn(k, 1 << st) { 343 w[st][k] = cw; 344 cw = cw * bw; 345 } 346 } 347 forn(st, LOGN) { 348 rv[st].assign(1 << st, 0); 349 if (st == 0) { 350 rv[st][0] = 0; 351 continue; 352 } 353 int h = (1 << (st - 1)); 354 forn(k, 1 << st) 355 rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h); 356 } 357 } 358 359 void ntt(vector<Mint> &a, bool inv) { 360 int n = sz(a); 361 int ln = __builtin_ctz(n); 362 forn(i, n) { 363 int ni = rv[ln][i]; 364 if (i < ni) swap(a[i], a[ni]); 365 } 366 forn(st, ln) { 367 int len = 1 << st; 368 for (int k = 0; k < n; k += (len << 1)) { 369 fore(pos, k, k + len){ 370 Mint l = a[pos]; 371 Mint r = a[pos + len] * w[st][pos - k]; 372 a[pos] = l + r; 373 a[pos + len] = l - r; 374 } 375 } 376 } 377 if (inv) { 378 Mint rn = Mint(n).pow(MOD - 2); 379 forn(i, n) a[i] = a[i] * rn; 380 reverse(a.begin() + 1, a.end()); 381 } 382 } 383 384 vector<Mint> mul(vector<Mint> a, vector<Mint> b) { 385 int cnt = 1 << (32 - __builtin_clz(sz(a) + sz(b) - 1)); 386 a.resize(cnt); 387 b.resize(cnt); 388 ntt(a, false); 389 ntt(b, false); 390 vector<Mint> c(cnt); 391 forn(i, cnt) c[i] = a[i] * b[i]; 392 ntt(c, true); 393 return c; 394 } 395 396 vector<Mint> norm(vector<Mint> a) 397 { 398 while(a.size() > 1 && a.back() == Mint(0)) 399 a.pop_back(); 400 return a; 401 } 402 403 const int N = 250043; 404 vector<int> G[N]; 405 int d[N]; 406 407 Mint fact[N * 2]; 408 Mint rev[N * 2]; 409 410 void dfs(int x, int p) 411 { 412 if(p != x) d[p]++; 413 for(auto y : G[x]) if(y != p) dfs(y, x); 414 } 415 416 Mint C(int n, int k) 417 { 418 return fact[n] * rev[k] * rev[n - k]; 419 } 420 421 int main() 422 { 423 prepare(); 424 fact[0] = Mint(1); 425 for(int i = 1; i < N * 2; i++) fact[i] = fact[i - 1] * i; 426 for(int i = 0; i < N * 2; i++) rev[i] = Mint(1) / fact[i]; 427 int n; 428 scanf("%d", &n); 429 for(int i = 0; i < n - 1; i++) 430 { 431 int x, y; 432 scanf("%d %d", &x, &y); 433 --x; 434 --y; 435 G[x].push_back(y); 436 G[y].push_back(x); 437 } 438 dfs(0, 0); 439 vector<vector<Mint>> cur; 440 for(int i = 0; i < n; i++) 441 if(d[i] > 0) 442 cur.push_back(vector<Mint>({Mint(1), Mint(d[i])})); 443 while(cur.size() > 1) 444 { 445 vector<vector<Mint>> ncur; 446 for(int i = 0; i + 1 < cur.size(); i += 2) 447 ncur.push_back(norm(mul(cur[i], cur[i + 1]))); 448 if(cur.size() % 2 == 1) ncur.push_back(cur.back()); 449 cur = ncur; 450 } 451 Mint ans = 0; 452 for(int i = 0; i < cur[0].size(); i++) 453 { 454 if(i % 2 == 0) ans = ans + cur[0][i] * fact[n - i]; 455 else ans = ans - cur[0][i] * fact[n - i]; 456 } 457 cout << ans << endl; 458 } 459 ```