1603.md (12153B)
1 Source: https://codeforces.com/blog/entry/96460 2 3 Thanks for participating in my contest [](https://emoji.gg/emoji/8771_blobheart). I hope you liked the problems. I would love to hear your feedback in the comments. 4 5 If you find anything wrong in the editorial which is more likely to happen because I have written a rather long editorial to make you understand the solutions better, then comment below. 6 7 Also, don't forget to upvote to pay for the editorial. See you in my next contest! 8 9 Tutorial is loading... 10 11 **Code** 12 13 ``` 14 #include<bits/stdc++.h> 15 using namespace std; 16 17 int main() { 18 int t; cin >> t; 19 while (t--) { 20 int n; cin >> n; 21 int ans = 0; 22 for (int i = 1; i <= n; i++) { 23 int k; cin >> k; 24 ans = max(ans, k - i); 25 } 26 cout << ans << '\n'; 27 } 28 return 0; 29 } 30 ``` 31 32 Tutorial is loading... 33 34 **Code** 35 36 ``` 37 #include<bits/stdc++.h> 38 using namespace std; 39 40 int main() { 41 ios_base::sync_with_stdio(0); 42 cin.tie(0); 43 int t; cin >> t; 44 while (t--) { 45 int n; cin >> n; 46 vector<int> a(n + 1); 47 bool inc = true; 48 for (int i = 1; i <= n; i++) { 49 cin >> a[i]; 50 inc &= a[i] > a[i - 1]; 51 } 52 if (n % 2 == 0 or !inc) { 53 cout << "YES\n"; 54 } 55 else { 56 cout << "NO\n"; 57 } 58 } 59 return 0; 60 } 61 ``` 62 63 Tutorial is loading... 64 65 **Code** 66 67 ``` 68 #include<bits/stdc++.h> 69 using namespace std; 70 71 int main() { 72 ios_base::sync_with_stdio(0); 73 cin.tie(0); 74 int t; cin >> t; 75 while (t--) { 76 int n; cin >> n; 77 bool ok = true; 78 for (int i = 1; i <= n; i++) { 79 int x; cin >> x; 80 bool found = false; 81 for (int j = i + 1; j >= 2; j--) { // this loop will run not more than 22 times, in practice its much lower than that 82 if (x % j) { 83 found = true; 84 break; 85 } 86 } 87 ok &= found; 88 } 89 if (ok) { 90 cout << "YES\n"; 91 } 92 else { 93 cout << "NO\n"; 94 } 95 } 96 return 0; 97 } 98 ``` 99 100 Tutorial is loading... 101 102 **Code** 103 104 ``` 105 #include<bits/stdc++.h> 106 using namespace std; 107 108 int main() { 109 ios_base::sync_with_stdio(0); 110 cin.tie(0); 111 int t; cin >> t; 112 while (t--) { 113 int x, y; cin >> x >> y; 114 if (x <= y) { 115 cout << y - y % x / 2 << '\n'; 116 } 117 else { 118 cout << x + y << '\n'; 119 } 120 } 121 return 0; 122 } 123 ``` 124 125 Tutorial is loading... 126 127 **Code** 128 129 ``` 130 #include<bits/stdc++.h> 131 using namespace std; 132 133 const int N = 1e5 + 9, mod = 998244353; 134 vector<int> v[2]; 135 int dp[2][N]; 136 int a[N]; 137 int32_t main() { 138 ios_base::sync_with_stdio(0); 139 cin.tie(0); 140 int t; cin >> t; 141 while (t--) { 142 int n; cin >> n; 143 for (int i = 1; i <= n; i++) { 144 cin >> a[i]; 145 } 146 long long ans = 0; 147 for (int i = n; i >= 1; i--) { 148 int k = i & 1; 149 v[k].push_back(a[i]); 150 dp[k][a[i]] = 1; 151 int last = a[i]; 152 for (auto x: v[k ^ 1]) { 153 int y = dp[k ^ 1][x]; 154 int split = (a[i] + x - 1) / x; 155 int st = a[i] / split; 156 ans += 1LL * (split - 1) * y * i; 157 dp[k][st] += y; 158 if (last != st) { 159 v[k].push_back(st), last = st; 160 } 161 } 162 for (auto x: v[k ^ 1]) dp[k ^ 1][x] = 0; 163 v[k ^ 1].clear(); 164 ans %= mod; 165 } 166 cout << ans << '\n'; 167 for (auto x: v[0]) dp[0][x] = 0; 168 for (auto x: v[1]) dp[1][x] = 0; 169 v[0].clear(); v[1].clear(); 170 } 171 return 0; 172 } 173 ``` 174 175 Tutorial is loading... 176 177 **Code (1D1D DP)** 178 179 ``` 180 #include<bits/stdc++.h> 181 using namespace std; 182 183 const int N = 1e5 + 9; 184 const long long inf = 1e12; 185 using ll = long long; 186 int phi[N]; 187 void totient() { 188 for (int i = 1; i < N; i++) phi[i] = i; 189 for (int i = 2; i < N; i++) { 190 if (phi[i] == i) { 191 for (int j = i; j < N; j += i) phi[j] -= phi[j] / i; 192 } 193 } 194 } 195 ll a[N], s1[N][320], s2[N][320]; 196 int root[N]; 197 ll c(int l, int r) { 198 if (l > r) return inf; 199 ll ans = 0; 200 if (r / l <= root[r]) { 201 return s1[r][r / l] - a[r / l] * (l - 1 - r / ((r / l) + 1)); 202 } 203 else { 204 return s2[r][l]; 205 } 206 return ans; 207 } 208 ll dp[N][17]; 209 int32_t main() { 210 ios_base::sync_with_stdio(0); 211 cin.tie(0); 212 totient(); 213 for (int i = 1; i < N; i++) { 214 a[i] = a[i - 1] + phi[i]; 215 } 216 for (int i = 1; i < N; i++) { 217 root[i] = 0; 218 for (int j = 1; j * j <= i; j++) { 219 s1[i][j] = s1[i][j - 1] + a[j] * (i / j - i / (j + 1)); 220 root[i] = j; 221 } 222 s2[i][i / (root[i] + 1) + 1] = s1[i][root[i]]; 223 for (int j = i / (root[i] + 1); j >= 1; j--) { 224 s2[i][j] = s2[i][j + 1] + a[i / j]; 225 } 226 } 227 int n = 100000; 228 dp[0][0] = 0; 229 for (int i = 1; i <= n; i++) { 230 dp[i][0] = inf; 231 } 232 for (int k = 1; (1 << k) <= n; k++) { 233 dp[0][k] = 0; 234 vector<pair<int, int> > v; // (start pos, best j) 235 v.push_back(make_pair(0, 0)); 236 for (int x = 1; x <= n; x++) { 237 int j = (--lower_bound(v.begin(), v.end(), make_pair(x + 1, 0)))->second; 238 dp[x][k] = dp[j][k - 1] + c(j + 1, x); 239 for (int i = (int)v.size() - 1; i >= 0; i--) { 240 int y = v[i].first, oldj = v[i].second; 241 if (y > x && dp[x][k - 1] + c(x + 1, y) < dp[oldj][k - 1] + c(oldj + 1, y)) v.pop_back(); 242 else { 243 int l = y + 1, r = n + 1; 244 while (l < r) { 245 int mid = (l + r) / 2; 246 if (dp[x][k - 1] + c(x + 1, mid) < dp[oldj][k - 1] + c(oldj + 1, mid)) r = mid; 247 else l = mid + 1; 248 } 249 if (r != n + 1) v.push_back(make_pair(r, x)); 250 break; 251 } 252 } 253 if (v.size() == 0) v.push_back(make_pair(0, x)); 254 } 255 } 256 int q; cin >> q; 257 while (q--) { 258 int n, k; cin >> n >> k; 259 if (k >= 20 or (1 << k) > n) { 260 cout << n << '\n'; 261 } 262 else { 263 cout << dp[n][k] << '\n'; 264 } 265 } 266 return 0; 267 } 268 ``` 269 270 **Code (D&C DP)** 271 272 ``` 273 #include<bits/stdc++.h> 274 using namespace std; 275 276 const int N = 1e5 + 9; 277 const long long inf = 1e12; 278 using ll = long long; 279 int phi[N]; 280 void totient() { 281 for (int i = 1; i < N; i++) phi[i] = i; 282 for (int i = 2; i < N; i++) { 283 if (phi[i] == i) { 284 for (int j = i; j < N; j += i) phi[j] -= phi[j] / i; 285 } 286 } 287 } 288 ll a[N]; 289 ll c(int l, int r) { 290 if (l > r) return inf; 291 ll ans = 0; 292 for (int i = l, last; i <= r; i = last + 1) { 293 last = r / (r / i); 294 int x = 0; 295 if (i >= l) x = last - i + 1; 296 else if (last >= l) x = last - l + 1; 297 ans += a[r / i] * x; 298 } 299 return ans; 300 } 301 ll dp[N][17]; 302 void yo(int i, int l, int r, int optl, int optr) { 303 if(l > r) return; 304 int mid = (l + r) / 2; 305 dp[mid][i] = inf; 306 int opt = optl; 307 ll cost = c(min(mid, optr) + 1, mid); 308 for(int k = min(mid, optr); k >= optl ; k--) { 309 ll cc = dp[k][i - 1] + cost; 310 if (cc <= dp[mid][i]) { 311 dp[mid][i] = cc; 312 opt = k; 313 } 314 if (k <= mid) { 315 if (cost == inf) cost = a[mid / k]; 316 else cost += a[mid / k]; 317 } 318 } 319 yo(i, l, mid - 1, optl, opt); 320 yo(i, mid + 1, r, opt, optr); 321 } 322 int32_t main() { 323 ios_base::sync_with_stdio(0); 324 cin.tie(0); 325 totient(); 326 for (int i = 1; i < N; i++) { 327 a[i] = a[i - 1] + phi[i]; 328 } 329 int n = 100000; 330 dp[0][0] = 0; 331 for (int i = 1; i <= n; i++) { 332 dp[i][0] = inf; 333 } 334 for(int i = 1; i <= n; i++) dp[i][1] = 1LL * i * (i + 1) / 2; 335 for(int i = 2; i <= 16; i++) yo(i, 1, n, 1, n); 336 int q; cin >> q; 337 while (q--) { 338 int n, k; cin >> n >> k; 339 if (k >= 20 or (1 << k) > n) { 340 cout << n << '\n'; 341 } 342 else { 343 cout << dp[n][k] << '\n'; 344 } 345 } 346 return 0; 347 } 348 ``` 349 350 Tutorial is loading... 351 352 **Code** 353 354 ``` 355 #include<bits/stdc++.h> 356 using namespace std; 357 358 const int N = 205; 359 int mod; 360 361 int power(long long n, long long k) { 362 int ans = 1 % mod; n %= mod; if (n < 0) n += mod; 363 while (k) { 364 if (k & 1) ans = (long long) ans * n % mod; 365 n = (long long) n * n % mod; 366 k >>= 1; 367 } 368 return ans; 369 } 370 int dp[N][N][40], fac[N], ifac[N]; 371 int vis[N][N][40]; 372 int n, a1; 373 /* 374 number of solutions to the equation b1 + b2 + ... bn <= a1 375 s.t. 0<=bi<=n+1-a1 376 and there is at least 1 number >= n + 1 - a1, 377 at least 2 numbers >= (n - a1), ..., at least (n - a1) numbers >= 2 378 */ 379 int yo(int i, int sum, int k) { // k <= 2 * sqrt(n) 380 if (i == n) return fac[n]; 381 if (k == 0) return 1LL * fac[n] * ifac[n - i] % mod; 382 if (vis[i][sum][k] == a1) return dp[i][sum][k]; 383 vis[i][sum][k] = a1; 384 int &ans = dp[i][sum][k]; 385 ans = 0; 386 int r = (a1 - sum) / k; 387 for (int cnt = r; cnt >= 0; cnt--) { 388 if (k > 1 and i + cnt < n - a1 + 1 - k + 1) continue; 389 ans += 1LL * yo(i + cnt, sum + cnt * k, k - 1) * ifac[cnt] % mod; 390 ans %= mod; 391 } 392 return ans; 393 } 394 int32_t main() { 395 ios_base::sync_with_stdio(0); 396 cin.tie(0); 397 cin >> n >> mod; 398 fac[0] = 1; 399 ifac[0] = 1; 400 for (int i = 1; i < N; i++) { 401 fac[i] = 1LL * fac[i - 1] * i % mod; 402 ifac[i] = power(fac[i], mod - 2); 403 } 404 int ans = 0; 405 int lim = 2 * sqrt(n) + 1; 406 for (a1 = max(1, n - lim); a1 <= n; a1++) { 407 ans += yo(0, 0, n + 1 - a1); 408 ans %= mod; 409 } 410 ans %= mod; 411 cout << ans << '\n'; 412 return 0; 413 } 414 ``` 415 416 Tutorial is loading... 417 418 **Code** 419 420 ``` 421 #include<bits/stdc++.h> 422 using namespace std; 423 424 const int N = 1e7 + 9, mod = 998244353; 425 template <const int32_t MOD> 426 struct modint { 427 int32_t value; 428 modint() = default; 429 modint(int32_t value_) : value(value_) {} 430 inline modint<MOD> operator + (modint<MOD> other) const { int32_t c = this->value + other.value; return modint<MOD>(c >= MOD ? c - MOD : c); } 431 inline modint<MOD> operator - (modint<MOD> other) const { int32_t c = this->value - other.value; return modint<MOD>(c < 0 ? c + MOD : c); } 432 inline modint<MOD> operator * (modint<MOD> other) const { int32_t c = (int64_t)this->value * other.value % MOD; return modint<MOD>(c < 0 ? c + MOD : c); } 433 inline modint<MOD> & operator += (modint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; } 434 inline modint<MOD> & operator -= (modint<MOD> other) { this->value -= other.value; if (this->value < 0) this->value += MOD; return *this; } 435 inline modint<MOD> & operator *= (modint<MOD> other) { this->value = (int64_t)this->value * other.value % MOD; if (this->value < 0) this->value += MOD; return *this; } 436 inline modint<MOD> operator - () const { return modint<MOD>(this->value ? MOD - this->value : 0); } 437 modint<MOD> pow(uint64_t k) const { modint<MOD> x = *this, y = 1; for (; k; k >>= 1) { if (k & 1) y *= x; x *= x; } return y; } 438 modint<MOD> inv() const { return pow(MOD - 2); } // MOD must be a prime 439 inline modint<MOD> operator / (modint<MOD> other) const { return *this * other.inv(); } 440 inline modint<MOD> operator /= (modint<MOD> other) { return *this *= other.inv(); } 441 inline bool operator == (modint<MOD> other) const { return value == other.value; } 442 inline bool operator != (modint<MOD> other) const { return value != other.value; } 443 inline bool operator < (modint<MOD> other) const { return value < other.value; } 444 inline bool operator > (modint<MOD> other) const { return value > other.value; } 445 }; 446 template <int32_t MOD> modint<MOD> operator * (int64_t value, modint<MOD> n) { return modint<MOD>(value) * n; } 447 template <int32_t MOD> modint<MOD> operator * (int32_t value, modint<MOD> n) { return modint<MOD>(value % MOD) * n; } 448 template <int32_t MOD> istream & operator >> (istream & in, modint<MOD> &n) { return in >> n.value; } 449 template <int32_t MOD> ostream & operator << (ostream & out, modint<MOD> n) { return out << n.value; } 450 451 using mint = modint<mod>; 452 453 mint pw[N]; 454 mint genius(int n, int k) { 455 if (k == 0) return 1; 456 vector<mint> c(k, 0), d(k + 1, 0); 457 d[k] = 1; 458 for (int i = k - 1; i >= 0; i--) { 459 c[i] = pw[i] * d[i + 1]; 460 d[i] = (pw[i] - 1) * d[i + 1]; 461 } 462 mint ans = 0, pwn = mint(2).pow(n), cur = 1; 463 for (int i = 0; i < k; i++) { 464 ans += ((k - 1 - i) & 1 ? mod - 1 : 1) * c[i] * cur; 465 cur *= pwn; 466 } 467 return ans; 468 } 469 mint f(int n, int k) { 470 if (k == 0 or n > k) return 0; 471 mint ans = 1; 472 for (int i = 0; i < n; i++) { 473 ans *= pw[k] - pw[i]; 474 } 475 return ans; 476 } 477 int32_t main() { 478 ios_base::sync_with_stdio(0); 479 cin.tie(0); 480 pw[0] = 1; 481 for (int i = 1; i < N; i++) { 482 pw[i] = pw[i - 1] * 2; 483 } 484 int t; cin >> t; 485 while (t--) { 486 int n, k, x; cin >> n >> k >> x; 487 if (x) { 488 cout << genius(n, k) << '\n'; 489 } 490 else { 491 cout << f(n, k) << '\n'; 492 } 493 } 494 return 0; 495 } 496 ```