848.md (25205B)
1 Source: https://codeforces.com/blog/entry/54233 2 3 Hi, dear contestants! 4 5 With the end of Codeforces Round #431 ([Div. 1](//codeforces.com/contest/848) and [Div. 2](//codeforces.com/contest/849)), some might be complaining behind the screen that problems are too tricky or hard, or have been struggling with some supposedly solvable problem... Yes, this time problems seem hard, but anyways, I hope they provided you with something, say rating, fun, ideas, or experience. I don't want to see anyone losing confidence because of failure (bad luck) in a single contest — please, don't do so. 6 7 Here are the hints, tutorials and codes for the problems. Feel free to discuss about problems in the comments, and point out if something is incorrect or unclear. Thank you! 8 9 ### [849A - Odds and Ends](/contest/849/problem/A "Codeforces Round 431 (Div. 2)") 10 11 by [cyand1317](/profile/cyand1317 "Grandmaster cyand1317") 12 13 **Hint** 14 15 What will the whole array satisfy? Is that a sufficient condition? 16 17 **Tutorial** 18 19 Tutorial is loading... 20 21 **Model solution** 22 23 ``` 24 #include <cstdio> 25 static const int MAXN = 102; 26 27 int n; 28 int a[MAXN]; 29 30 int main() 31 { 32 scanf("%d", &n); 33 for (int i = 0; i < n; ++i) scanf("%d", &a[i]); 34 35 puts((n % 2 == 1) && (a[0] % 2 == 1) && (a[n - 1] % 2 == 1) ? "Yes" : "No"); 36 return 0; 37 } 38 ``` 39 40 ### [849B - Tell Your World](/contest/849/problem/B "Codeforces Round 431 (Div. 2)") 41 42 by [cyand1317](/profile/cyand1317 "Grandmaster cyand1317") 43 44 **Hint** 45 46 First way: consider the first three points. What cases are there? 47 48 Second way: consider the first point. Either it's on a single line alone, or the line that passes through it passes through another point. Iterate over this point. 49 50 **Tutorial** 51 52 Tutorial is loading... 53 54 **Tommyr7's solution (first idea)** 55 56 ``` 57 #include <bits/stdc++.h> 58 #define eps 1e-7 59 using namespace std; 60 int read() 61 { 62 int x=0,f=1;char ch=getchar(); 63 while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} 64 while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 65 return x*f; 66 } 67 int n,a[1007]; 68 bool vis[1007]; 69 bool check(double k,int b) 70 { 71 memset(vis,false,sizeof(vis)); 72 int cnt=0; 73 for (int i=1;i<=n;i++) 74 { 75 if (a[i]-b==1LL*k*(i-1)) 76 { 77 vis[i]=true; 78 ++cnt; 79 } 80 } 81 if (cnt==n) return false; 82 if (cnt==n-1) return true; 83 int pos1=0; 84 for (int i=1;i<=n;i++) 85 if (!vis[i]&&pos1==0) pos1=i; 86 for (int i=pos1+1;i<=n;i++) 87 if (!vis[i]) 88 { 89 if (fabs((double)(a[i]-a[pos1])/(i-pos1)-k)>eps) return false; 90 } 91 return true; 92 } 93 int main() 94 { 95 n=read(); 96 for (int i=1;i<=n;i++) 97 a[i]=read(); 98 bool ans=false; 99 ans|=check(1.0*(a[2]-a[1]),a[1]); 100 ans|=check(0.5*(a[3]-a[1]),a[1]); 101 ans|=check(1.0*(a[3]-a[2]),a[2]*2-a[3]); 102 if (ans) printf("Yes\n"); else printf("No\n"); 103 return 0; 104 } 105 ``` 106 107 **Model solution (second idea)** 108 109 ``` 110 #include <cstdio> 111 #include <algorithm> 112 static const int MAXN = 1004; 113 114 int n; 115 int y[MAXN]; 116 117 bool on_first[MAXN]; 118 119 bool check() 120 { 121 for (int i = 1; i < n; ++i) { 122 for (int j = 0; j < n; ++j) { 123 if ((long long)i * (y[j] - y[0]) == (long long)j * (y[i] - y[0])) 124 on_first[j] = true; 125 else on_first[j] = false; 126 } 127 int start_idx = -1; 128 bool valid = true; 129 for (int j = 0; j < n; ++j) if (!on_first[j]) { 130 if (start_idx == -1) { 131 start_idx = j; 132 } else if ((long long)i * (y[j] - y[start_idx]) != (long long)(j - start_idx) * (y[i] - y[0])) { 133 valid = false; break; 134 } 135 } 136 if (valid && start_idx != -1) return true; 137 } 138 return false; 139 } 140 141 int main() 142 { 143 scanf("%d", &n); 144 for (int i = 0; i < n; ++i) scanf("%d", &y[i]); 145 146 bool ans = false; 147 ans |= check(); 148 std::reverse(y, y + n); 149 ans |= check(); 150 151 puts(ans ? "Yes" : "No"); 152 return 0; 153 } 154 ``` 155 156 ### [848A - From Y to Y](/contest/848/problem/A "Codeforces Round 431 (Div. 1)") 157 158 by [cyand1317](/profile/cyand1317 "Grandmaster cyand1317") 159 160 **Hint** 161 162 For a given string, how to calculate the cost? 163 164 **More** 165 166 For each letter, count how many times it appears in the original string. 167 168 **Tutorial** 169 170 Tutorial is loading... 171 172 **Kalinin's solution** 173 174 ``` 175 #include <bits/stdc++.h> 176 177 using namespace std; 178 179 using ll = long long; 180 using ld = long double; 181 using D = double; 182 using uint = unsigned int; 183 template<typename T> 184 using pair2 = pair<T, T>; 185 186 #ifdef WIN32 187 #define LLD "%I64d" 188 #else 189 #define LLD "%lld" 190 #endif 191 192 #define pb push_back 193 #define mp make_pair 194 #define all(x) (x).begin(),(x).end() 195 #define fi first 196 #define se second 197 198 int main() 199 { 200 int k; 201 scanf("%d", &k); 202 for (int i = 0; i < 26; i++) 203 { 204 int cnt = 1; 205 while ((cnt + 1) * cnt / 2 <= k) cnt++; 206 k -= cnt * (cnt - 1) / 2; 207 for (int j = 0; j < cnt; j++) printf("%c", 'a' + i); 208 } 209 return 0; 210 } 211 ``` 212 213 **Model solution with knapsack (!)** 214 215 ``` 216 #include <cstdio> 217 #include <vector> 218 static const int MAXK = 100002; 219 static const int INF = 0x3fffffff; 220 221 int f[MAXK]; 222 int pred[MAXK]; 223 224 int main() 225 { 226 f[0] = 0; 227 for (int i = 1; i < MAXK; ++i) f[i] = INF; 228 for (int i = 0; i < MAXK; ++i) pred[i] = -1; 229 230 for (int i = 0; i < MAXK; ++i) if (f[i] != INF) { 231 for (int j = 2; i + j * (j - 1) / 2 < MAXK; ++j) 232 if (f[i + j * (j - 1) / 2] > f[i] + 1) { 233 f[i + j * (j - 1) / 2] = f[i] + 1; 234 pred[i + j * (j - 1) / 2] = j; 235 } 236 } else printf("Assertion failed at %d\n", i); 237 238 int k; 239 scanf("%d", &k); 240 if (k == 0) { puts("a"); return 0; } 241 std::vector<int> v; 242 for (; k > 0; k -= pred[k] * (pred[k] - 1) / 2) { 243 v.push_back(pred[k]); 244 } 245 for (int i = 0; i < v.size(); ++i) { 246 for (int j = 0; j < v[i]; ++j) putchar('a' + i); 247 } 248 putchar('\n'); 249 250 return 0; 251 } 252 ``` 253 254 ### [848B - Rooter's Song](/contest/848/problem/B "Codeforces Round 431 (Div. 1)") 255 256 by [cyand1317](/profile/cyand1317 "Grandmaster cyand1317") 257 258 **Hint** 259 260 When do dancers collide? What changes and what keeps the same? 261 262 **Next** 263 264 Group dancers by *p* - *t*. What happens next? 265 266 **Tutorial** 267 268 Tutorial is loading... 269 270 **Model solution** 271 272 ``` 273 #include <cstdio> 274 #include <algorithm> 275 #include <vector> 276 static const int MAXN = 100004; 277 static const int MAXW = 100003; 278 static const int MAXT = 100002; 279 280 int n, w, h; 281 int g[MAXN], p[MAXN], t[MAXN]; 282 283 std::vector<int> s[MAXW + MAXT]; 284 int ans_x[MAXN], ans_y[MAXN]; 285 286 int main() 287 { 288 scanf("%d%d%d", &n, &w, &h); 289 for (int i = 0; i < n; ++i) { 290 scanf("%d%d%d", &g[i], &p[i], &t[i]); 291 s[p[i] - t[i] + MAXT].push_back(i); 292 } 293 294 std::vector<int> xs, ys; 295 for (int i = 0; i < MAXW + MAXT; ++i) if (!s[i].empty()) { 296 for (int u : s[i]) { 297 if (g[u] == 1) xs.push_back(p[u]); 298 else ys.push_back(p[u]); 299 } 300 std::sort(xs.begin(), xs.end()); 301 std::sort(ys.begin(), ys.end()); 302 std::sort(s[i].begin(), s[i].end(), [] (int u, int v) { 303 if (g[u] != g[v]) return (g[u] == 2); 304 else return (g[u] == 2 ? p[u] > p[v] : p[u] < p[v]); 305 }); 306 for (int j = 0; j < xs.size(); ++j) { 307 ans_x[s[i][j]] = xs[j]; 308 ans_y[s[i][j]] = h; 309 } 310 for (int j = 0; j < ys.size(); ++j) { 311 ans_x[s[i][j + xs.size()]] = w; 312 ans_y[s[i][j + xs.size()]] = ys[ys.size() - j - 1]; 313 } 314 xs.clear(); 315 ys.clear(); 316 } 317 318 for (int i = 0; i < n; ++i) printf("%d %d\n", ans_x[i], ans_y[i]); 319 320 return 0; 321 } 322 ``` 323 324 ### [848C - Goodbye Souvenir](/contest/848/problem/C "Codeforces Round 431 (Div. 1)") 325 326 by [adedalic](/profile/adedalic "Master adedalic") 327 328 **Hint** 329 330 Difference between last occurrence and first occurrence equals the sum of differences between pairs of adjacent occurrences. Handle this with some segment tree, or even non-standard size block decomposition, say sizes of *O*(*n*2 / 3). 331 332 **Tutorial** 333 334 Tutorial is loading... 335 336 **Model solution** 337 338 ``` 339 #include <bits/stdc++.h> 340 341 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 342 #define forn(i, n) fore(i, 0, n) 343 344 #define all(a) (a).begin(), (a).end() 345 #define sqr(a) ((a) * (a)) 346 #define sz(a) int(a.size()) 347 #define mp make_pair 348 #define pb push_back 349 350 #define x first 351 #define y second 352 353 using namespace std; 354 355 template<class A, class B> ostream& operator << (ostream &out, const pair<A, B> &p) { 356 return out << "(" << p.first << ", " << p.second << ")"; 357 } 358 359 template<class A> ostream& operator << (ostream &out, const vector<A> &v) { 360 out << "["; 361 forn(i, sz(v)) { 362 if(i > 0) 363 out << " "; 364 out << v[i]; 365 } 366 return out << "]"; 367 } 368 369 mt19937 myRand(time(NULL)); 370 371 typedef long long li; 372 typedef long double ld; 373 typedef pair<int, int> pt; 374 375 inline int gett() { 376 return clock() * 1000 / CLOCKS_PER_SEC; 377 } 378 379 const ld EPS = 1e-9; 380 const int INF = int(1e9); 381 const li INF64 = li(INF) * INF; 382 const ld PI = 3.1415926535897932384626433832795; 383 384 const int N = 100 * 1000 + 555; 385 386 int n, m, aa[N], a[N]; 387 int qt[N], qx[N], qy[N]; 388 389 inline bool read() { 390 if(!(cin >> n >> m)) 391 return false; 392 393 forn(i, n) 394 assert(scanf("%d", &aa[i]) == 1); 395 396 forn(i, m) { 397 assert(scanf("%d%d%d", &qt[i], &qx[i], &qy[i]) == 3); 398 qx[i]--; 399 } 400 401 return true; 402 } 403 404 vector<int> vars[4 * N]; 405 vector<li> f[4 * N]; 406 li sumAll[4 * N]; 407 408 inline void addValF(int k, int pos, int val) { 409 sumAll[k] += val; 410 for(; pos < sz(f[k]); pos |= pos + 1) 411 f[k][pos] += val; 412 } 413 414 inline li sum(int k, int pos) { 415 li ans = 0; 416 for(; pos >= 0; pos = (pos & (pos + 1)) - 1) 417 ans += f[k][pos]; 418 419 return ans; 420 } 421 422 inline li getSumF(int k, int pos) { 423 return sumAll[k] - sum(k, pos - 1); 424 } 425 426 li getSumST(int v, int l, int r, int lf, int rg, int val) { 427 if(l >= r || lf >= rg) 428 return 0; 429 430 if(l == lf && r == rg) { 431 int pos = int(lower_bound(all(vars[v]), val) - vars[v].begin()); 432 return getSumF(v, pos); 433 } 434 435 int mid = (l + r) >> 1; 436 437 li ans = 0; 438 if(lf < mid) 439 ans += getSumST(2 * v + 1, l, mid, lf, min(mid, rg), val); 440 if(rg > mid) 441 ans += getSumST(2 * v + 2, mid, r, max(lf, mid), rg, val); 442 443 return ans; 444 } 445 446 void addValST(int k, int v, int l, int r, int pos, int pos2, int val) { 447 if(l >= r) 448 return; 449 450 if(!k) 451 vars[v].pb(pos2); 452 else { 453 int cpos = int(lower_bound(all(vars[v]), pos2) - vars[v].begin()); 454 addValF(v, cpos, val); 455 } 456 457 if(l + 1 == r) { 458 assert(l == pos); 459 return; 460 } 461 462 int mid = (l + r) >> 1; 463 464 if(pos < mid) 465 addValST(k, 2 * v + 1, l, mid, pos, pos2, val); 466 else 467 addValST(k, 2 * v + 2, mid, r, pos, pos2, val); 468 } 469 470 int pr[N]; 471 set<int> ids[N]; 472 473 void build(int k, int v, int l, int r) { 474 fore(i, l, r) 475 if(!k) 476 vars[v].pb(pr[i]); 477 else { 478 int pos = int(lower_bound(all(vars[v]), pr[i]) - vars[v].begin()); 479 addValF(v, pos, i - pr[i]); 480 } 481 482 if(l + 1 == r) 483 return; 484 485 int mid = (l + r) >> 1; 486 487 build(k, 2 * v + 1, l, mid); 488 build(k, 2 * v + 2, mid, r); 489 } 490 491 inline void eraseSets(int k, int pos) { 492 addValST(k, 0, 0, n, pos, pr[pos], -(pos - pr[pos])); 493 ids[ a[pos] ].erase(pos); 494 495 auto it2 = ids[ a[pos] ].lower_bound(pos); 496 497 if(it2 != ids[ a[pos] ].end()) { 498 int np = *it2; 499 assert(a[np] == a[pos]); 500 assert(pr[np] == pos); 501 502 addValST(k, 0, 0, n, np, pr[np], -(np - pr[np])); 503 504 pr[np] = pr[pos]; 505 addValST(k, 0, 0, n, np, pr[np], +(np - pr[np])); 506 } 507 508 a[pos] = -1; 509 pr[pos] = -1; 510 } 511 512 inline void insertSets(int k, int pos, int nval) { 513 auto it2 = ids[nval].lower_bound(pos); 514 assert(it2 == ids[nval].end() || *it2 > pos); 515 516 if(it2 != ids[nval].end()) { 517 int np = *it2; 518 assert(a[np] == nval); 519 520 addValST(k, 0, 0, n, np, pr[np], -(np - pr[np])); 521 522 pr[np] = pos; 523 addValST(k, 0, 0, n, np, pr[np], +(np - pr[np])); 524 } 525 526 pr[pos] = -1; 527 if(it2 != ids[nval].begin()) { 528 auto it1 = it2; it1--; 529 assert(*it1 < pos); 530 531 pr[pos] = *it1; 532 } 533 addValST(k, 0, 0, n, pos, pr[pos], +(pos - pr[pos])); 534 535 ids[nval].insert(pos); 536 a[pos] = nval; 537 } 538 539 inline void precalc() { 540 forn(v, 4 * N) { 541 sort(all(vars[v])); 542 vars[v].erase(unique(all(vars[v])), vars[v].end()); 543 544 f[v].assign(sz(vars[v]), 0); 545 sumAll[v] = 0; 546 } 547 } 548 549 inline void solve() { 550 forn(k, 2) { 551 if(k) precalc(); 552 553 forn(i, N) 554 ids[i].clear(); 555 forn(i, n) 556 a[i] = aa[i]; 557 558 vector<int> ls(n + 1, -1); 559 forn(i, n) { 560 pr[i] = ls[ a[i] ]; 561 ls[ a[i] ] = i; 562 563 ids[ a[i] ].insert(i); 564 } 565 566 build(k, 0, 0, n); 567 568 // cerr << k << " " << clock() << endl; 569 570 forn(q, m) { 571 if(qt[q] == 1) { 572 eraseSets(k, qx[q]); 573 insertSets(k, qx[q], qy[q]); 574 } else 575 if(k) printf("%I64d\n", getSumST(0, 0, n, qx[q], qy[q], qx[q])); 576 } 577 578 // cerr << k << " " << clock() << endl; 579 } 580 } 581 582 int main(){ 583 #ifdef _DEBUG 584 freopen("input.txt", "r", stdin); 585 freopen("output.txt", "w", stdout); 586 587 int t = gett(); 588 #endif 589 590 srand(time(NULL)); 591 cout << fixed << setprecision(10); 592 593 while(read()) { 594 solve(); 595 596 #ifdef _DEBUG 597 cerr << "TIME = " << gett() - t << endl; 598 t = gett(); 599 #endif 600 } 601 return 0; 602 } 603 ``` 604 605 ### [848D - Shake It!](/contest/848/problem/D "Codeforces Round 431 (Div. 1)") 606 607 by [cyand1317](/profile/cyand1317 "Grandmaster cyand1317") 608 609 **Hint** 610 611 Use DP. *f*[*i*][*j*] keeps the number of subgraphs with *i* operations and a minimum cut of *j*. The transition may be in a knapsack-like manner. Add more functions (say another *g*[*i*][*j*]) if needed to make it faster. 612 613 There are more than one way to do DP, you can also read about other nice solutions here and here. 614 615 **Tutorial** 616 617 Tutorial is loading... 618 619 **Model solution** 620 621 ``` 622 #include <cstdio> 623 #include <cstring> 624 typedef long long int64; 625 static const int MAXN = 53; 626 static const int MODULUS = 1e9 + 7; 627 #define _ % MODULUS 628 #define __ %= MODULUS 629 630 int n, m; 631 // f[# of operations][mincut] -- total number of graphs 632 // g[# of operations][mincut] -- number of ordered pairs of two graphs 633 int64 f[MAXN][MAXN] = {{ 0 }}, g[MAXN][MAXN] = {{ 0 }}; 634 int64 h[MAXN][MAXN]; 635 636 inline int64 qpow(int64 base, int exp) { 637 int64 ans = 1; 638 for (; exp; exp >>= 1, (base *= base)__) if (exp & 1) (ans *= base)__; 639 return ans; 640 } 641 int64 inv[MAXN]; 642 643 int main() 644 { 645 for (int i = 0; i < MAXN; ++i) inv[i] = qpow(i, MODULUS - 2); 646 647 scanf("%d%d", &n, &m); 648 649 f[0][1] = 1; 650 for (int i = 1; i <= n; ++i) { 651 for (int j = 1; j <= i + 1; ++j) { 652 // Calculate g[i][*] 653 // pair(i)(j) = graph(p)(r) in series with graph(q)(s) 654 // where p+q == i-1, min(r, s) == j 655 for (int p = 0; p <= i - 1; ++p) { 656 int q = i - 1 - p; 657 for (int r = j; r <= p + 1; ++r) 658 (g[i][j] += (int64)f[p][r] * f[q][j])__; 659 for (int s = j + 1; s <= q + 1; ++s) 660 (g[i][j] += (int64)f[p][j] * f[q][s])__; 661 } 662 // Update all f with g[i][*] 663 // Iterate over the number of times pair(i)(j) is appended in parallel, let it be t 664 // h is used as a temporary array 665 memset(h, 0, sizeof h); 666 for (int p = 0; p <= n; ++p) 667 for (int q = 1; q <= p + 1; ++q) { 668 int64 comb = 1; 669 for (int t = 1; p + t * i <= n; ++t) { 670 comb = comb * (g[i][j] + t - 1)_ * inv[t]_; 671 (h[p + t * i][q + t * j] += f[p][q] * comb)__; 672 } 673 } 674 for (int p = 0; p <= n; ++p) 675 for (int q = 1; q <= p + 1; ++q) 676 (f[p][q] += h[p][q])__; 677 } 678 } 679 680 printf("%lld\n", f[n][m]); 681 682 return 0; 683 } 684 ``` 685 686 ### [848E - Days of Floral Colours](/contest/848/problem/E "Codeforces Round 431 (Div. 1)") 687 688 by [cyand1317](/profile/cyand1317 "Grandmaster cyand1317") 689 690 **Hint** 691 692 Break the circle down into semicircles. Then there will be 1D/1D recurrences over several functions. 693 694 **Last insight** 695 696 Use FFT in a divide-and-conquer manner to optimize it. 697 698 **Tutorial** 699 700 Tutorial is loading... 701 702 **O(n^2) solution** 703 704 ``` 705 #include <cstdio> 706 typedef long long int64; 707 static const int MAXN = 50004; 708 static const int MODULUS = 998244353; 709 #define _ % MODULUS 710 #define __ %= MODULUS 711 712 int n; 713 int64 g[MAXN]; 714 int64 f0[MAXN], f1[MAXN], f2[MAXN]; 715 716 int main() 717 { 718 scanf("%d", &n); 719 720 g[0] = 1; 721 g[2] = 1; 722 for (int i = 4; i <= n; i += 2) g[i] = (g[i - 4] + g[i - 2])_; 723 724 f0[0] = 0; 725 f1[0] = 1; 726 f2[0] = 4; 727 for (int i = 1; i <= n; ++i) { 728 f0[i] = g[i] * i _ * i _; 729 for (int j = 1; j <= i - 2; ++j) { 730 f0[i] += g[j] * j _ * j _ * f0[i - j - 1]_; 731 f0[i] += g[j - 1] * j _ * j _ * f1[i - j - 2]_; 732 } 733 f1[i] = g[i] * (i + 1)_ * (i + 1)_ + f0[i - 1]; 734 for (int j = 1; j <= i - 2; ++j) { 735 f1[i] += g[j] * (j + 1)_ * (j + 1)_ * f0[i - j - 1]_; 736 f1[i] += g[j - 1] * (j + 1)_ * (j + 1)_ * f1[i - j - 2]_; 737 } 738 f0[i]__; f1[i]__; 739 } 740 for (int i = 1; i <= n; ++i) { 741 f2[i] = g[i] * (i + 2)_ * (i + 2)_ + f1[i - 1]; 742 for (int j = 1; j <= i - 1; ++j) { 743 f2[i] += g[j] * (j + 1)_ * (j + 1)_ * f1[i - j - 1]_; 744 f2[i] += g[j - 1] * (j + 1)_ * (j + 1)_ * f2[i - j - 2]_; 745 } 746 f2[i]__; 747 } 748 749 int64 ans = 0; 750 751 ans += (g[n - 1] + g[n - 3]) * (n - 1)_ * (n - 1)_ * n _; 752 for (int i = 2; i <= n - 2; ++i) { 753 ans += g[i - 1] * (i - 1)_ * (i - 1)_ * f0[n - i - 1]_ * i _; 754 ans += g[i - 2] * (i - 1)_ * (i - 1)_ * f1[n - i - 2]_ * 2 * i _; 755 if (i >= 3 && i <= n - 3) 756 ans += g[i - 3] * (i - 1)_ * (i - 1)_ * f2[n - i - 3]_ * i _; 757 } 758 759 printf("%lld\n", ans _); 760 761 return 0; 762 } 763 ``` 764 765 **Model solution** 766 767 ``` 768 #include <cstdio> 769 #include <cstring> 770 typedef long long int64; 771 static const int LOGN = 18; 772 static const int MAXN = 1 << LOGN; 773 static const int MODULUS = 998244353; 774 static const int PRIMITIVE = 2192; 775 #define _ % MODULUS 776 #define __ %= MODULUS 777 template <typename T> inline void swap(T &a, T &b) { static T t; t = a; a = b; b = t; } 778 779 int n; 780 int64 g[MAXN]; 781 int64 g0[MAXN], g1[MAXN], g2[MAXN]; 782 int64 f0[MAXN], f1[MAXN], f2[MAXN]; 783 784 int64 q0[MAXN], q1[MAXN]; 785 int64 t1[MAXN], t2[MAXN], t3[MAXN], t4[MAXN]; 786 787 inline int qpow(int64 base, int exp) 788 { 789 int64 ans = 1; 790 for (; exp; exp >>= 1) { if (exp & 1) (ans *= base)__; (base *= base)__; } 791 return ans; 792 } 793 794 int bitrev[LOGN][MAXN]; 795 int root[2][LOGN]; 796 inline void fft(int n, int64 *a, int direction) 797 { 798 int s = __builtin_ctz(n); 799 int64 u, v, r, w; 800 for (int i = 0; i < n; ++i) if (i < bitrev[s][i]) swap(a[i], a[bitrev[s][i]]); 801 for (int i = 1; i <= n; i <<= 1) 802 for (int j = 0; j < n; j += i) { 803 r = root[direction == -1][__builtin_ctz(i)]; 804 w = 1; 805 for (int k = j; k < j + (i >> 1); ++k) { 806 u = a[k]; 807 v = (a[k + (i >> 1)] * w)_; 808 a[k] = (u + v)_; 809 a[k + (i >> 1)] = (u - v + MODULUS)_; 810 w = (w * r)_; 811 } 812 } 813 } 814 815 inline void convolve(int n, int64 *a, int64 *b, int64 *c) 816 { 817 static int64 a1[MAXN], b1[MAXN]; 818 memcpy(a1, a, n * 2 * sizeof(int64)); 819 memcpy(b1, b, n * 2 * sizeof(int64)); 820 memset(a + n, 0, n * sizeof(int64)); 821 memset(b + n, 0, n * sizeof(int64)); 822 fft(n * 2, a, +1); 823 fft(n * 2, b, +1); 824 int64 q = qpow(n * 2, MODULUS - 2); 825 for (int i = 0; i < n * 2; ++i) c[i] = a[i] * b[i]_; 826 fft(n * 2, c, -1); 827 for (int i = 0; i < n; ++i) c[i] = c[i] * q _; 828 memcpy(a, a1, n * 2 * sizeof(int64)); 829 memcpy(b, b1, n * 2 * sizeof(int64)); 830 } 831 832 // Calcukates f0 and f1. 833 void solve_1(int l, int r) 834 { 835 if (l == r) { 836 (f0[l] += g0[l])__; 837 (f1[l] += g1[l])__; 838 return; 839 } 840 841 int m = (l + r) >> 1; 842 843 solve_1(l, m); 844 845 int len = 1; 846 while (len < r - l + 1) len <<= 1; 847 for (int i = 0; i < len; ++i) q0[i] = (i + l <= m ? f0[i + l] : 0); 848 for (int i = 0; i < len; ++i) q1[i] = (i + l <= m ? f1[i + l] : 0); 849 for (int i = len; i < len * 2; ++i) q0[i] = q1[i] = 0; 850 convolve(len, g0, q0, t1); 851 convolve(len, g1, q0, t2); 852 convolve(len, g1, q1, t3); 853 convolve(len, g2, q1, t4); 854 855 for (int i = 0; i < len; ++i) { 856 if (i + l >= m + 1 - 1 && i + l <= r - 1) { 857 (f0[i + l + 1] += t1[i])__; 858 (f1[i + l + 1] += t2[i])__; 859 } 860 if (i + l >= m + 1 - 3 && i + l <= r - 3) { 861 (f0[i + l + 3] += t3[i])__; 862 (f1[i + l + 3] += t4[i])__; 863 } 864 } 865 866 solve_1(m + 1, r); 867 } 868 869 // Calculates f2. 870 void solve_2(int l, int r) 871 { 872 if (l == r) { 873 (f2[l] += (g2[l] + (l >= 1 ? t1[l - 1] : 0)))__; 874 return; 875 } 876 877 int m = (l + r) >> 1; 878 879 solve_2(l, m); 880 881 int len = 1; 882 while (len < r - l + 1) len <<= 1; 883 for (int i = 0; i < len; ++i) q0[i] = (i + l <= m ? f2[i + l] : 0); 884 for (int i = len; i < len * 2; ++i) q0[i] = 0; 885 convolve(len, g2, q0, t2); 886 887 for (int i = 0; i < len; ++i) { 888 if (i + l >= m + 1 - 3 && i + l <= r - 3) { 889 (f2[i + l + 3] += t2[i])__; 890 } 891 } 892 893 solve_2(m + 1, r); 894 } 895 896 int main() 897 { 898 for (int s = 0; s < LOGN; ++s) 899 for (int i = 0; i < (1 << s); ++i) 900 bitrev[s][i] = (bitrev[s][i >> 1] >> 1) | ((i & 1) << (s - 1)); 901 for (int i = 0; i < LOGN; ++i) { 902 root[0][i] = qpow(PRIMITIVE, MAXN >> i); 903 root[1][i] = qpow(PRIMITIVE, MAXN - (MAXN >> i)); 904 } 905 906 scanf("%d", &n); 907 908 g[0] = 1; 909 g[2] = 1; 910 for (int i = 4; i <= n; i += 2) g[i] = (g[i - 4] + g[i - 2])_; 911 for (int i = 0; i <= n; ++i) { 912 g0[i] = g[i] * i _ * i _; 913 g1[i] = g[i] * (i + 1)_ * (i + 1)_; 914 g2[i] = g[i] * (i + 2)_ * (i + 2)_; 915 } 916 917 solve_1(0, n); 918 919 int len = 1; 920 while (len < n) len <<= 1; 921 convolve(len, g1, f1, t1); 922 solve_2(0, n); 923 924 int64 ans = 0; 925 926 ans += (g[n - 1] + g[n - 3]) * (n - 1)_ * (n - 1)_ * n _; 927 for (int i = 2; i <= n - 2; ++i) { 928 ans += g0[i - 1] * f0[n - i - 1]_ * i _; 929 ans += g1[i - 2] * f1[n - i - 2]_ * 2 * i _; 930 if (i >= 3 && i <= n - 3) 931 ans += g2[i - 3] * f2[n - i - 3]_ * i _; 932 } 933 934 printf("%lld\n", ans _); 935 936 return 0; 937 } 938 ``` 939 940 ## Behind the scene and random things (read if tired of problemsolving) 941 942 **Expand** 943 944 Perhaps some may have noticed that at the end of editorial of #418 it's written that 945 946 > Probably it will be for Ha... 947 948 Yes, I had had ideas for the last four problems for Div. 2 by that time. Then I came up with Div. 2 A when lying on bed one night, seems I underestimated its trickiness :/ 949 950 (1 September 2017 is also when the story of **Ha**rry Potter ends, so to me seems like a great coincidence?) 951 952 After my unsuccessful performance at the National Olympiad (that's another thing to talk about), on that evening when everything seemed dull, I changed Div. 1 E to what it looks like now — it used to be Div. 1 C or so. "I'm poor at problemsolving. This is the hardest I can come up with," I thought, "and if it doesn't qualify then I'd better give up on holding a round with Div. 1." 953 954 Then in early August I created the proposal with all problems. After it was reviewed, some of them were changed, moved or replaced, and I ended up having no Div. 1 D. I had an idea and put it to Div. 1 D, but we had difficulty distinguishing different complexities, so it was set aside and replaced with the problem from [adedalic](/profile/adedalic "Master adedalic"). Schoolwork kept disrupting me from working on preparation, but I managed to allocate time to do it all for my own problems (except tutorials, :P). [adedalic](/profile/adedalic "Master adedalic")'s problem is prepared by him and [KAN](/profile/KAN "Grandmaster KAN"), thank you! 955 956 Then two hours before the contest, it was suggested that swapping Div. 1 C and Div. 1 D would be good. I had't had enough time to test the new problem myself, but I thought the second division may prefer data structures to multidimensional DP and agreed. Then Div. 1 contestants jump from A to C and had unfavourable luck... My sympathy, hope you have enjoyed the problems themselves. 957 958 These are random fragments of the story behind this round. It wouldn't have been possible without you, dear contestants and members of the community. My deep gratitude! 959 960 Also, the problems feature songs created by songwriters and the voice of Hatsune Miku. Let it be happy or sad, separation or reunion, the problems are all inspired by the songs at the very beginning (not necessarily contents though, for example 2A and 1E are just related to the songs in title). Here's the list if you're interested. 961 962 * [*ODDS&ENDS*](http://vocadb.net/S/15662) by ryo 963 * [*Tell Your World*](http://vocadb.net/S/8395) by kz 964 * [*from Y to Y*](http://vocadb.net/S/4230) by OneRoom 965 * [*Rooter's Song*](http://vocadb.net/S/71159) by DECO*27 966 * [*Sayonara Souvenir*](http://vocadb.net/S/110348) (Goodbye Souvenir) by Toa 967 * [*shake it!*](http://vocadb.net/S/11593) by emon(Tes.) 968 * [*Hanairo Biyori*](http://vocadb.net/S/39300) (Flower Colored Weather) by Natsume Chiaki 969 970 Thank you for reading. Next round? Perhaps something more traditional, who knows? Believe me, I'll try harder if this happens. 971 972 Cheers! \(^ ^)/ 973 974 --- 975 976 **UPD** Packages for problems are uploaded. They are in Polygon format and contain everything including statements, tests & generators, validators & checkers, and solutions. You can download them from [Google Drive](https://drive.google.com/drive/folders/0B5z87ZbXNZyEcXBtSVhWbDJEN00?usp=sharing) or [Baidu Drive](https://pan.baidu.com/s/1eSJ68gE).