codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

849.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).