1511.md (8865B)
1 Source: https://codeforces.com/blog/entry/89634 2 3 [1511A - Review Site](/contest/1511/problem/A "Educational Codeforces Round 107 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (adedalic)** 12 13 ``` 14 fun main() { 15 repeat(readLine()!!.toInt()) { 16 readLine()!!.toInt() 17 println(readLine()!!.split(' ').count { it != "2" }) 18 } 19 } 20 ``` 21 22 [1511B - GCD Length](/contest/1511/problem/B "Educational Codeforces Round 107 (Rated for Div. 2)") 23 24 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 25 26 **Tutorial** 27 28 Tutorial is loading... 29 30 **Solution (awoo)** 31 32 ``` 33 for t in range(int(input())): 34 a, b, c = map(int, input().split()) 35 print("1" + "0" * (a - 1), "1" * (b - c + 1) + "0" * (c - 1)) 36 ``` 37 38 [1511C - Yet Another Card Deck](/contest/1511/problem/C "Educational Codeforces Round 107 (Rated for Div. 2)") 39 40 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 41 42 **Tutorial** 43 44 Tutorial is loading... 45 46 **Solution (Neon)** 47 48 ``` 49 #include <bits/stdc++.h> 50 51 using namespace std; 52 53 int main() { 54 int n, q; 55 scanf("%d%d", &n, &q); 56 vector<int> a(n); 57 for (int& x : a) scanf("%d", &x); 58 while (q--) { 59 int x; 60 scanf("%d", &x); 61 int p = find(a.begin(), a.end(), x) - a.begin(); 62 printf("%d ", p + 1); 63 rotate(a.begin(), a.begin() + p, a.begin() + p + 1); 64 } 65 } 66 ``` 67 68 [1511D - Min Cost String](/contest/1511/problem/D "Educational Codeforces Round 107 (Rated for Div. 2)") 69 70 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 71 72 **Tutorial** 73 74 Tutorial is loading... 75 76 **Solution (Neon)** 77 78 ``` 79 #include <bits/stdc++.h> 80 81 using namespace std; 82 83 int n, k; 84 int cur[26]; 85 vector<int> path; 86 87 void dfs(int v) { 88 while (cur[v] < k) { 89 int u = cur[v]++; 90 dfs(u); 91 path.push_back(u); 92 } 93 } 94 95 int main() { 96 scanf("%d%d", &n, &k); 97 dfs(0); 98 printf("a"); 99 for (int i = 0; i < n - 1; ++i) 100 printf("%c", path[i % path.size()] + 'a'); 101 } 102 ``` 103 104 [1511E - Colorings and Dominoes](/contest/1511/problem/E "Educational Codeforces Round 107 (Rated for Div. 2)") 105 106 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 107 108 **Tutorial** 109 110 Tutorial is loading... 111 112 **Solution (BledDest)** 113 114 ``` 115 #include <bits/stdc++.h> 116 117 using namespace std; 118 119 const int N = 300043; 120 const int MOD = 998244353; 121 122 int add(int x, int y) 123 { 124 x += y; 125 while(x >= MOD) 126 x -= MOD; 127 while(x < 0) 128 x += MOD; 129 return x; 130 } 131 132 int sub(int x, int y) 133 { 134 return add(x, MOD - y); 135 } 136 137 int mul(int x, int y) 138 { 139 return (x * 1ll * y) % MOD; 140 } 141 142 int binpow(int x, int y) 143 { 144 int z = 1; 145 while(y > 0) 146 { 147 if(y % 2 == 1) 148 z = mul(z, x); 149 x = mul(x, x); 150 y /= 2; 151 } 152 return z; 153 } 154 155 int inv(int x) 156 { 157 return binpow(x, MOD - 2); 158 } 159 160 int divide(int x, int y) 161 { 162 return mul(x, inv(y)); 163 } 164 165 string s[N]; 166 int p[N]; 167 int n, m; 168 char buf[N]; 169 170 int main() 171 { 172 scanf("%d %d", &n, &m); 173 for(int i = 0; i < n; i++) 174 { 175 scanf("%s", buf); 176 s[i] = buf; 177 } 178 p[0] = divide(1, 2); 179 for(int i = 1; i < N; i++) 180 if(i % 2 == 1) 181 p[i] = sub(p[i - 1], divide(1, binpow(2, i))); 182 else 183 p[i] = add(p[i - 1], divide(1, binpow(2, i))); 184 int ans = 0; 185 int w = 0; 186 for(int i = 0; i < n; i++) 187 for(int j = 0; j < m; j++) 188 if(s[i][j] != '*') 189 w = add(w, 1); 190 for(int i = 0; i < n; i++) 191 { 192 int c = 0; 193 for(int j = 0; j < m; j++) 194 { 195 if(s[i][j] == '*') 196 c = 0; 197 else 198 c++; 199 if(c > 0) 200 ans = add(ans, p[c]); 201 } 202 } 203 for(int j = 0; j < m; j++) 204 { 205 int c = 0; 206 for(int i = 0; i < n; i++) 207 { 208 if(s[i][j] == '*') 209 c = 0; 210 else 211 c++; 212 if(c > 0) 213 ans = add(ans, p[c]); 214 } 215 } 216 ans = mul(ans, binpow(2, w)); 217 cout << ans << endl; 218 } 219 ``` 220 221 [1511F - Chainword](/contest/1511/problem/F "Educational Codeforces Round 107 (Rated for Div. 2)") 222 223 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 224 225 **Tutorial** 226 227 Tutorial is loading... 228 229 **Solution (awoo)** 230 231 ``` 232 #include <bits/stdc++.h> 233 234 #define forn(i, n) for (int i = 0; i < int(n); i++) 235 236 using namespace std; 237 238 const int MOD = 998244353; 239 const int K = 161; 240 const int AL = 26; 241 242 struct node{ 243 int nxt[AL]; 244 bool term; 245 node(){ 246 memset(nxt, -1, sizeof(nxt)); 247 term = false; 248 }; 249 int& operator [](const int x){ 250 return nxt[x]; 251 } 252 }; 253 254 vector<node> trie; 255 256 int tot; 257 258 void add(const string &s){ 259 int cur = 0; 260 int d = 1; 261 for (const char &c : s){ 262 ++d; 263 if (trie[cur][c - 'a'] == -1){ 264 trie[cur][c - 'a'] = trie.size(); 265 trie.push_back(node()); 266 tot += d; 267 } 268 cur = trie[cur][c - 'a']; 269 } 270 trie[cur].term = true; 271 } 272 273 int add(int a, int b){ 274 a += b; 275 if (a >= MOD) 276 a -= MOD; 277 return a; 278 } 279 280 int mul(int a, int b){ 281 return a * 1ll * b % MOD; 282 } 283 284 typedef array<array<int, K>, K> mat; 285 286 mat operator *(const mat &a, const mat &b){ 287 mat c; 288 forn(i, K) forn(j, K) c[i][j] = 0; 289 forn(i, K) forn(j, K) forn(k, K) 290 c[i][j] = add(c[i][j], mul(a[i][k], b[k][j])); 291 return c; 292 } 293 294 mat binpow(mat a, long long b){ 295 mat res; 296 forn(i, K) forn(j, K) res[i][j] = i == j; 297 while (b){ 298 if (b & 1) 299 res = res * a; 300 a = a * a; 301 b >>= 1; 302 } 303 return res; 304 } 305 306 map<pair<int, int>, int> num; 307 queue<pair<int, int>> q; 308 309 int get(int v, int u){ 310 if (v > u) swap(v, u); 311 if (!num.count({v, u})){ 312 int k = num.size(); 313 assert(k < K); 314 num[{v, u}] = k; 315 q.push({v, u}); 316 } 317 return num[{v, u}]; 318 } 319 320 int main() { 321 int n; 322 long long m; 323 cin >> n >> m; 324 trie = vector<node>(1, node()); 325 tot = 1; 326 forn(i, n){ 327 string s; 328 cin >> s; 329 add(s); 330 } 331 q.push({0, 0}); 332 num[q.front()] = 0; 333 mat init; 334 forn(i, K) forn(j, K) init[i][j] = 0; 335 while (!q.empty()){ 336 int v = q.front().first; 337 int u = q.front().second; 338 q.pop(); 339 int x = get(v, u); 340 forn(c, AL){ 341 int tov = trie[v][c]; 342 int tou = trie[u][c]; 343 if (tov == -1 || tou == -1) continue; 344 ++init[x][get(tov, tou)]; 345 if (trie[tov].term) ++init[x][get(0, tou)]; 346 if (trie[tou].term) ++init[x][get(tov, 0)]; 347 if (trie[tov].term && trie[tou].term) ++init[x][0]; 348 } 349 } 350 init = binpow(init, m); 351 printf("%d\n", init[0][0]); 352 return 0; 353 } 354 ``` 355 356 [1511G - Chips on a Board](/contest/1511/problem/G "Educational Codeforces Round 107 (Rated for Div. 2)") 357 358 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 359 360 **Tutorial** 361 362 Tutorial is loading... 363 364 **Solution (BledDest)** 365 366 ``` 367 #include <bits/stdc++.h> 368 369 using namespace std; 370 371 const int N = 200043; 372 const int K = 10; 373 const int Z = 1 << K; 374 375 int rem[Z]; 376 int t[N]; 377 378 int get(int r) 379 { 380 int result = 0; 381 for (; r >= 0; r = (r & (r + 1)) - 1) 382 result ^= t[r]; 383 return result; 384 } 385 386 void change(int i, int delta) 387 { 388 for (; i < N; i = (i | (i + 1))) 389 t[i] ^= delta; 390 } 391 392 int get(int l, int r) 393 { 394 return get(r) - get(l - 1); 395 } 396 397 int ans[N]; 398 int c[N]; 399 int cnt[N]; 400 int n, m; 401 int ls[N]; 402 int rs[N]; 403 vector<int> qs[N]; 404 vector<int> qs2[N]; 405 406 int main() 407 { 408 scanf("%d %d", &n, &m); 409 for(int i = 0; i < n; i++) 410 { 411 scanf("%d", &c[i]); 412 cnt[c[i]]++; 413 } 414 int q; 415 scanf("%d", &q); 416 for(int i = 0; i < q; i++) 417 { 418 int l, r; 419 scanf("%d %d", &l, &r); 420 ls[i] = l; 421 rs[i] = r; 422 qs[l].push_back(i); 423 qs2[r + 1].push_back(i); 424 } 425 for(int i = m; i >= 1; i--) 426 { 427 for(int j = 0; j < cnt[i]; j++) 428 { 429 rem[i % (1 << K)]++; 430 int r = i; 431 while(true) 432 { 433 int l = r - Z + 1; 434 l = max(1, l); 435 if(l > r) 436 break; 437 int diff = i - l; 438 diff >>= K; 439 change(l, diff); 440 change(r + 1, diff); 441 r -= Z; 442 } 443 } 444 for(auto x : qs[i]) 445 { 446 int cur = (get(i)) << K; 447 for(int k = 0; k < Z; k++) 448 { 449 int dist = (k - i) % Z; 450 if(dist < 0) 451 dist += Z; 452 if(rem[k] & 1) 453 cur ^= dist; 454 } 455 ans[x] ^= cur; 456 } 457 for(auto x : qs2[i]) 458 { 459 int cur = (get(ls[x])) << K; 460 for(int k = 0; k < Z; k++) 461 { 462 int dist = (k - ls[x]) % Z; 463 if(dist < 0) 464 dist += Z; 465 if(rem[k] & 1) 466 cur ^= dist; 467 } 468 ans[x] ^= cur; 469 } 470 } 471 for(int i = 0; i < q; i++) 472 if(ans[i] == 0) 473 printf("B"); 474 else 475 printf("A"); 476 } 477 ```