1295.md (9847B)
1 Source: https://codeforces.com/blog/entry/73467 2 3 [1295A - Display The Number](/contest/1295/problem/A "Educational Codeforces Round 81 (Rated for Div. 2)") 4 5 Idea: [adedalic](/profile/adedalic "International Master adedalic") 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 if(n % 2 == 1): 18 print(7, end='') 19 n -= 3 20 while(n > 0): 21 print(1, end='') 22 n -= 2 23 print() 24 ``` 25 26 [1295B - Infinite Prefixes](/contest/1295/problem/B "Educational Codeforces Round 81 (Rated for Div. 2)") 27 28 Idea: [Roms](/profile/Roms "Master Roms") 29 30 **Tutorial** 31 32 Tutorial is loading... 33 34 **Solution (adedalic)** 35 36 ``` 37 #include<bits/stdc++.h> 38 39 using namespace std; 40 41 typedef long long li; 42 43 int n, x; 44 string s; 45 46 inline bool read() { 47 if(!(cin >> n >> x >> s)) 48 return false; 49 return true; 50 } 51 52 inline void solve() { 53 int ans = 0; 54 bool infAns = false; 55 56 int cntZeros = (int)count(s.begin(), s.end(), '0'); 57 int total = cntZeros - (n - cntZeros); 58 59 int bal = 0; 60 for(int i = 0; i < n; i++) { 61 if(total == 0) { 62 if(bal == x) 63 infAns = true; 64 } 65 else if(abs(x - bal) % abs(total) == 0) { 66 if((x - bal) / total >= 0) 67 ans++; 68 } 69 70 if(s[i] == '0') 71 bal++; 72 else 73 bal--; 74 } 75 76 if(infAns) ans = -1; 77 cout << ans << endl; 78 } 79 80 int main() { 81 #ifdef _DEBUG 82 freopen("input.txt", "r", stdin); 83 #endif 84 ios_base::sync_with_stdio(false); 85 cin.tie(0), cout.tie(0); 86 cout << fixed << setprecision(15); 87 88 int tc; cin >> tc; 89 while(tc--) { 90 read(); 91 solve(); 92 } 93 94 return 0; 95 } 96 ``` 97 98 [1295C - Obtain The String](/contest/1295/problem/C "Educational Codeforces Round 81 (Rated for Div. 2)") 99 100 Idea: [Roms](/profile/Roms "Master Roms") 101 102 **Tutorial** 103 104 Tutorial is loading... 105 106 **Solution (Roms)** 107 108 ``` 109 #include<bits/stdc++.h> 110 using namespace std; 111 112 const int N = int(2e5) + 99; 113 const int INF = int(1e9) + 99; 114 115 int tc; 116 string s, t; 117 int nxt[N][26]; 118 119 int main() { 120 cin >> tc; 121 while(tc--){ 122 cin >> s >> t; 123 for(int i = 0; i < s.size() + 5; ++i) 124 for(int j = 0; j < 26; ++j) 125 nxt[i][j] = INF; 126 127 for(int i = int(s.size()) - 1; i >= 0; --i){ 128 for(int j = 0; j < 26; ++j) 129 nxt[i][j] = nxt[i + 1][j]; 130 nxt[i][s[i] - 'a'] = i; 131 } 132 133 int res = 1, pos = 0; 134 for(int i = 0; i < t.size(); ++i){ 135 if(pos == s.size()){ 136 pos = 0; 137 ++res; 138 } 139 if(nxt[pos][t[i] - 'a'] == INF){ 140 pos = 0; 141 ++res; 142 } 143 if(nxt[pos][t[i] - 'a'] == INF && pos == 0){ 144 res = INF; 145 break; 146 } 147 pos = nxt[pos][t[i] - 'a'] + 1; 148 149 } 150 151 if(res >= INF) cout << -1 << endl; 152 else cout << res << endl; 153 } 154 return 0; 155 } 156 ``` 157 158 [1295D - Same GCDs](/contest/1295/problem/D "Educational Codeforces Round 81 (Rated for Div. 2)") 159 160 Idea: [adedalic](/profile/adedalic "International Master adedalic") 161 162 **Tutorial** 163 164 Tutorial is loading... 165 166 **Solution (adedalic)** 167 168 ``` 169 fun gcd(a : Long, b : Long) : Long { 170 return if (a == 0L) b else gcd(b % a, a) 171 } 172 fun phi(a : Long) : Long { 173 var (tmp, ans) = listOf(a, a) 174 var d = 2L 175 while (d * d <= tmp) { 176 var cnt = 0 177 while (tmp % d == 0L) { 178 tmp /= d 179 cnt++ 180 } 181 if (cnt > 0) ans -= ans / d 182 d++ 183 } 184 if (tmp > 1L) ans -= ans / tmp 185 return ans 186 } 187 188 fun main() { 189 val t = readLine()!!.toInt() 190 for (tc in 1..t) { 191 val (a, m) = readLine()!!.split(' ').map { it.toLong() } 192 println(phi(m / gcd(a, m))) 193 } 194 } 195 ``` 196 197 [1295E - Permutation Separation](/contest/1295/problem/E "Educational Codeforces Round 81 (Rated for Div. 2)") 198 199 Idea: [adedalic](/profile/adedalic "International Master adedalic") 200 201 **Tutorial** 202 203 Tutorial is loading... 204 205 **Solution (adedalic)** 206 207 ``` 208 #include<bits/stdc++.h> 209 using namespace std; 210 211 const int N = int(2e5) + 99; 212 213 int n; 214 int p[N]; 215 int rp[N]; 216 int a[N]; 217 218 long long b[N]; 219 long long t[4 * N]; 220 long long add[4 * N]; 221 222 void build(int v, int l, int r){ 223 if(r - l == 1){ 224 t[v] = b[l]; 225 return; 226 } 227 228 int mid = (l + r) / 2; 229 build(v * 2 + 1, l, mid); 230 build(v * 2 + 2, mid, r); 231 t[v] = min(t[v * 2 + 1], t[v * 2 + 2]); 232 } 233 234 void push(int v, int l, int r){ 235 if(add[v] != 0){ 236 if(r - l > 1) 237 for(int i = v+v+1; i < v+v+3; ++i){ 238 add[i] += add[v]; 239 t[i] += add[v]; 240 } 241 add[v] = 0; 242 } 243 } 244 245 void upd(int v, int l, int r, int L, int R, int x){ 246 if(L >= R) return; 247 if(l == L && r == R){ 248 add[v] += x; 249 t[v] += x; 250 push(v, l, r); 251 return; 252 } 253 254 push(v, l, r); 255 int mid = (l + r) / 2; 256 upd(v * 2 + 1, l, mid, L, min(mid, R), x); 257 upd(v * 2 + 2, mid, r, max(mid, L), R, x); 258 259 t[v] = min(t[v * 2 + 1], t[v * 2 + 2]); 260 } 261 262 void upd(int l, int r, int x){ 263 upd(0, 0, n, l, r, x); 264 } 265 266 long long get(int v, int l, int r, int L, int R){ 267 if(L >= R) return 1e18; 268 269 push(v, l, r); 270 if(l == L && r == R) 271 return t[v]; 272 273 int mid = (l + r) / 2; 274 return min(get(v * 2 + 1, l, mid, L, min(R, mid)), 275 get(v * 2 + 2, mid, r, max(L, mid), R)); 276 } 277 278 long long get(int l, int r){ 279 return get(0, 0, n, l, r); 280 } 281 282 int main() { 283 scanf("%d", &n); 284 for(int i = 0; i < n; ++i){ 285 scanf("%d", p + i); 286 --p[i]; 287 rp[p[i]] = i; 288 } 289 for(int i = 0; i < n; ++i) 290 scanf("%d", a + i); 291 292 b[0] = a[0]; 293 for(int i = 1; i < n; ++i) 294 b[i] = a[i] + b[i - 1]; 295 build(0, 0, n); 296 297 long long res = get(0, n - 1); 298 //for(int i = 0; i < n; ++i) cout << get(i, i+1) << ' ';cout << endl; 299 for(int i = 0; i < n; ++i){ 300 int pos = rp[i]; 301 upd(pos, n, -a[pos]); 302 upd(0, pos, a[pos]); 303 res = min(res, get(0, n - 1)); 304 //for(int i = 0; i < n; ++i) cout << get(i, i+1) << ' ';cout << endl; 305 } 306 307 cout << res << endl; 308 return 0; 309 } 310 ``` 311 312 [1295F - Good Contest](/contest/1295/problem/F "Educational Codeforces Round 81 (Rated for Div. 2)") 313 314 Idea: [Roms](/profile/Roms "Master Roms") 315 316 **Tutorial** 317 318 Tutorial is loading... 319 320 **Solution (BledDest)** 321 322 ``` 323 #include <bits/stdc++.h> 324 325 using namespace std; 326 327 const int MOD = 998244353; 328 329 int add(int x, int y) 330 { 331 x += y; 332 while(x >= MOD) x -= MOD; 333 while(x < 0) x += MOD; 334 return x; 335 } 336 337 int mul(int x, int y) 338 { 339 return (x * 1ll * y) % MOD; 340 } 341 342 int binpow(int x, int y) 343 { 344 int z = 1; 345 while(y) 346 { 347 if(y & 1) z = mul(z, x); 348 x = mul(x, x); 349 y >>= 1; 350 } 351 return z; 352 } 353 354 int inv(int x) 355 { 356 return binpow(x, MOD - 2); 357 } 358 359 int divide(int x, int y) 360 { 361 return mul(x, inv(y)); 362 } 363 364 typedef vector<int> poly; 365 366 void norm(poly& p) 367 { 368 while(p.size() > 0 && p.back() == 0) 369 p.pop_back(); 370 } 371 372 poly operator +(const poly& a, const poly& b) 373 { 374 poly c = a; 375 while(c.size() < b.size()) c.push_back(0); 376 for(int i = 0; i < b.size(); i++) c[i] = add(c[i], b[i]); 377 norm(c); 378 return c; 379 } 380 381 poly operator +(const poly& a, int b) 382 { 383 return a + poly(1, b); 384 } 385 386 poly operator +(int a, const poly& b) 387 { 388 return b + a; 389 } 390 391 poly operator *(const poly& a, int b) 392 { 393 poly c = a; 394 for(int i = 0; i < c.size(); i++) c[i] = mul(c[i], b); 395 norm(c); 396 return c; 397 } 398 399 poly operator /(const poly& a, int b) 400 { 401 return a * inv(b); 402 } 403 404 poly operator *(const poly& a, const poly& b) 405 { 406 poly c(a.size() + b.size() - 1); 407 for(int i = 0; i < a.size(); i++) 408 for(int j = 0; j < b.size(); j++) 409 c[i + j] = add(c[i + j], mul(a[i], b[j])); 410 411 norm(c); 412 return c; 413 } 414 415 poly interpolate(const vector<int>& x, const vector<int>& y) 416 { 417 int n = int(x.size()) - 1; 418 vector<vector<int> > f(n + 1); 419 f[0] = y; 420 for(int i = 1; i <= n; i++) 421 for(int j = 0; j <= n - i; j++) 422 f[i].push_back(divide(add(f[i - 1][j + 1], -f[i - 1][j]), add(x[i + j], -x[j]))); 423 424 poly cur = poly(1, 1); 425 poly res; 426 for(int i = 0; i <= n; i++) 427 { 428 res = res + cur * f[i][0]; 429 cur = cur * poly({add(0, -x[i]), 1}); 430 } 431 432 return res; 433 } 434 435 int eval(const poly& a, int x) 436 { 437 int res = 0; 438 for(int i = int(a.size()) - 1; i >= 0; i--) 439 res = add(mul(res, x), a[i]); 440 return res; 441 } 442 443 poly sumFromL(const poly& a, int L, int n) 444 { 445 vector<int> x; 446 for(int i = 0; i <= n; i++) 447 x.push_back(L + i); 448 vector<int> y; 449 int cur = 0; 450 for(int i = 0; i <= n; i++) 451 { 452 cur = add(cur, eval(a, x[i])); 453 y.push_back(cur); 454 } 455 return interpolate(x, y); 456 } 457 458 int sumOverSegment(const poly& a, int L, int R) 459 { 460 return eval(sumFromL(a, L, a.size()), R - 1); 461 } 462 463 int main() { 464 int n; 465 cin >> n; 466 vector<int> L(n), R(n); 467 for(int i = 0; i < n; i++) 468 { 469 cin >> L[i] >> R[i]; 470 R[i]++; 471 } 472 reverse(L.begin(), L.end()); 473 reverse(R.begin(), R.end()); 474 475 vector<int> coord = {0, MOD - 2}; 476 for(int i = 0; i < n; i++) 477 { 478 coord.push_back(L[i]); 479 coord.push_back(R[i]); 480 } 481 sort(coord.begin(), coord.end()); 482 coord.erase(unique(coord.begin(), coord.end()), coord.end()); 483 vector<int> cL = coord, cR = coord; 484 cL.pop_back(); 485 cR.erase(cR.begin()); 486 int cnt = coord.size() - 1; 487 vector<poly> cur(cnt); 488 for(int i = 0; i < cnt; i++) 489 if(cL[i] >= L[0] && cR[i] <= R[0]) 490 cur[i] = poly(1, inv(R[0] - L[0])); 491 for(int i = 1; i < n; i++) 492 { 493 vector<poly> nxt(cnt); 494 int curSum = 0; 495 for(int j = 0; j < cnt; j++) 496 { 497 nxt[j] = sumFromL(cur[j], cL[j], i) + curSum; 498 curSum = add(curSum, sumOverSegment(cur[j], cL[j], cR[j])); 499 } 500 for(int j = 0; j < cnt; j++) 501 nxt[j] = nxt[j] * (cL[j] >= L[i] && cR[j] <= R[i] ? inv(R[i] - L[i]) : 0); 502 cur = nxt; 503 } 504 int ans = 0; 505 for(int i = 0; i < cnt; i++) 506 ans = add(ans, sumOverSegment(cur[i], cL[i], cR[i])); 507 508 cout << ans << endl; 509 } 510 ```