979.md (13802B)
1 Source: https://codeforces.com/blog/entry/59462 2 3 Hi Codeforces! 4 5 This is the editorial of [Codeforces Round 482 (Div. 2)](/contest/979 "Codeforces Round 482 (Div. 2)"). I hope you guys enjoy it. 6 7 [979A - Pizza, Pizza, Pizza!!!](/contest/979/problem/A "Codeforces Round 482 (Div. 2)") 8 9 **Solution** 10 11 If *n* = 0, the answer is obviously 0. 12 13 If *n* + 1 is even, we can make  diametric cuts. Otherwise, the only way is to make *n* + 1 cuts. 14 15 Time complexity: *O*(1). 16 17 **Code** 18 19 ``` 20 #include <stdio.h> 21 using namespace std; 22 23 long long n; 24 25 int main() 26 { 27 scanf("%I64d", &n); 28 n++; 29 if (n == 1) printf("0"); else if (n % 2 == 0) printf("%I64d", n / 2); else printf("%I64d", n); 30 return 0; 31 } 32 ``` 33 34 [979B - Treasure Hunt](/contest/979/problem/B "Codeforces Round 482 (Div. 2)") 35 36 **Solution** 37 38 We all knew that the substrings with length 1 appear at most in the string. So, to make a string as beautiful as possible, we will choose the letter that firstly appears at most in the string and replace all the other letters with the chosen letter. 39 40 There is some cases. If *n* is less than or equal to the number of remaining letters, just add *n* to the beauty. If *n* is even after replacing all letters with the chosen, we can choose an arbitrary letter, replace it with some other letter, return it back and repeat the work till *n* reach 0. Otherwise, we will not replace all the other letters. Instead, we will replace the letters until there is 1 letter left (now *n* is even) then replace that one with another letter different from our chosen letter. After that, replace that letter with our chosen letter. Now *n* is even again, we repeat the work discussed above. 41 42 In conclusion, let's call our string *s*, our chosen letter *a* and its number of occurrences in the string *f**a*, then our answer is *min*(*f**a* + *n*, |*s*|). Be careful with *n* = 1. 43 44 Time complexity: , where  is the total length of the three strings. 45 46 **Code** 47 48 ``` 49 #include <bits/stdc++.h> 50 51 using namespace std; 52 53 int a[256], b[256], c[256], n, ma, mb, mc; 54 string p, q, r; 55 56 int main() { 57 cin >> n >> p >> q >> r; 58 for (char x: p) ma = max(ma, ++a[x]); 59 for (char x: q) mb = max(mb, ++b[x]); 60 for (char x: r) mc = max(mc, ++c[x]); 61 if (n == 1 && ma == (int)p.length()) p.pop_back(); 62 if (n == 1 && mb == (int)q.length()) q.pop_back(); 63 if (n == 1 && mc == (int)r.length()) r.pop_back(); 64 ma = min(ma + n, (int)p.length()); 65 mb = min(mb + n, (int)q.length()); 66 mc = min(mc + n, (int)r.length()); 67 if (ma > mb && ma > mc) { 68 puts("Kuro"); 69 return 0; 70 } 71 if (mb > ma && mb > mc) { 72 puts("Shiro"); 73 return 0; 74 } 75 if (mc > ma && mc > mb) { 76 puts("Katie"); 77 return 0; 78 } 79 puts("Draw"); 80 return 0; 81 } 82 ``` 83 84 [979C - Kuro and Walking Route](/contest/979/problem/C "Codeforces Round 482 (Div. 2)") 85 86 **Solution** 87 88 We can consider the city as a graph, in which every town is a vertex and every road connecting two towns is an edge. Since *m* < *n*, we can deduce that this graph is a tree. Now, instead of finding the number of pairs that Kuro can choose, we can find the number of pairs that Kuro cannot choose. In other words, we must find the number of pairs of vertices (*u*, *v*), in which the shortest path from *u* to *v* passes through *x* and then through *y*. But how can we do this? 89 90 If we take vertex *y* as the root of the tree, we can see that every pair of vertices that Kuro cannot choose begins from any node within the subtree of node *x*, and finishes at any node but within the subtree of node *z*, which *z* is a direct child of *y* lying on the shortest path from *x* to *y*. In total, the number of pairs of vertices that we are looking for is equal of *n*·(*n* - 1) - *s*[*x*]·(*s*[*y*] - *s*[*z*]), which *s*[*i*] denotes the size of the subtree of node *i*. We can implement this using simple DFS. 91 92 Time complexity: *O*(*n*). 93 94 **Code** 95 96 ``` 97 #include <iostream> 98 #include <cstdio> 99 #include <vector> 100 using namespace std; 101 102 const int MAXN = 3e5; 103 104 int n, m, u, v, x, y, sub_size[MAXN + 5]; 105 bool vis[MAXN + 5], chk_sub[MAXN + 5]; 106 vector<int> adj[MAXN + 5]; 107 108 int DFS(int u) 109 { 110 vis[u] = true; sub_size[u] = 1; 111 if (u == x) 112 chk_sub[u] = true; 113 else chk_sub[u] = false; 114 for (int v: adj[u]) 115 if (!vis[v]) 116 { 117 sub_size[u] += DFS(v); 118 chk_sub[u] |= chk_sub[v]; 119 } 120 return sub_size[u]; 121 } 122 123 int main() 124 { 125 scanf("%d%d%d", &n, &x, &y); 126 m = n - 1; 127 while (m--) 128 { 129 scanf("%d%d", &u, &v); 130 adj[u].push_back(v); 131 adj[v].push_back(u); 132 } 133 DFS(y); 134 135 long long fin; 136 for (int v: adj[y]) 137 if (chk_sub[v]) 138 { 139 fin = sub_size[y] - sub_size[v]; 140 break; 141 } 142 143 printf("%I64d", 1LL * n * (n - 1) - fin * sub_size[x]); 144 return 0; 145 } 146 ``` 147 148 [979D - Kuro and GCD and XOR and SUM](/contest/979/problem/D "Codeforces Round 482 (Div. 2)") 149 150 **Solution** 151 152 We first look at the condition . This condition holds iff both *x**i* and *v* are divisible by *k**i*. Therefore, if , we return `-1` immediately, else we only consider numbers in *a* that are divisible by *k**i*. 153 154 Finding the maximum XOR of *x**i* with *v* in the array *a* reminds us of a classic problem, where the data structure trie is used to descend from the higher bit positions to the lower bit positions. But since we only consider *v* such that  and *x**i* + *v* ≤ *s**i*, we build 105 tries, where the *i**th* trie holds information of numbers in *a* that are divisible by *i*, and we only descend to a branch in the trie if the branch is not empty and the minimum value in the branch is ≤ *s**i* - *x**i*. 155 156 Adding a number into *a* is trivial by now: we update every *u**th* trie where *u* divides the number we need to add into the array. Notice that we only add a number if the number doesn't exist in the array yet. 157 158 Time complexity: *O*(*MAXlog*(*MAX*) + *qlog*(*MAX*)2). 159 160 **Code** 161 162 ``` 163 #include <iostream> 164 #include <cstdio> 165 #include <vector> 166 using namespace std; 167 168 const int MAX = 1E5 + 5; 169 170 struct SNode 171 { 172 int mi; 173 SNode *bit[2]; 174 175 SNode() 176 { 177 mi = MAX; 178 bit[0] = bit[1] = nullptr; 179 } 180 } *rt[MAX]; 181 vector<int> di[MAX]; 182 int q, t, u, k, x, s; 183 bool chk[MAX]; 184 185 void init() 186 { 187 for (int i = 1; i < MAX; i++) 188 { 189 for (int j = i; j < MAX; j += i) 190 di[j].push_back(i); 191 rt[i] = new SNode(); 192 } 193 } 194 195 void add(int k, int u) 196 { 197 SNode *cur = rt[k]; 198 cur->mi = min(cur->mi, u); 199 for (int i = 18; i >= 0; i--) 200 { 201 if (cur->bit[u >> i & 1] == nullptr) 202 cur->bit[u >> i & 1] = new SNode(); 203 cur = cur->bit[u >> i & 1]; 204 cur->mi = min(cur->mi, u); 205 } 206 } 207 208 int que(int x, int k, int s) 209 { 210 SNode *cur = rt[k]; 211 if (x % k != 0 || cur->mi + x > s) 212 return -1; 213 int ret = 0; 214 for (int i = 18; i >= 0; i--) 215 { 216 int bi = x >> i & 1; 217 if (cur->bit[bi ^ 1] != nullptr && cur->bit[bi ^ 1]->mi + x <= s) 218 { 219 ret += ((bi ^ 1) << i); 220 cur = cur->bit[bi ^ 1]; 221 } 222 else 223 { 224 ret += (bi << i); 225 cur = cur->bit[bi]; 226 } 227 } 228 return ret; 229 } 230 231 int main() 232 { 233 init(); 234 scanf("%d", &q); 235 while (q--) 236 { 237 scanf("%d", &t); 238 if (t == 1) 239 { 240 scanf("%d", &u); 241 if (!chk[u]) 242 { 243 chk[u] = true; 244 for (int k : di[u]) 245 add(k, u); 246 } 247 } 248 else 249 { 250 scanf("%d%d%d", &x, &k, &s); 251 printf("%d\n", que(x, k, s)); 252 } 253 } 254 return 0; 255 } 256 ``` 257 258 [979E - Kuro and Topological Parity](/contest/979/problem/E "Codeforces Round 482 (Div. 2)") 259 260 **Solution** 261 262 The problem asks us to find the number of different simple directed acyclic graphs with 1 → *n* forming its topological order to ensure the parity of the number of alternating paths to be equal to *p*. We will solve this problem using the dynamic programming approach. 263 264 Let's define **even-white** as the number of different nodes *u* colored in white that has an even number of alternating paths that end in *u*. In the same fashion, let's define **odd-white** as the number of different nodes *u* colored in white that has an odd number of alternating paths that end in *u*, **even-black** — the number of different nodes *u* colored in black that has an even number of alternating paths that end in *u*, and **odd-black** — the number of different nodes *u* colored in black that has an odd number of alternating paths that end in *u*. Let's also define *dp*[*i*][*ew*][*ow*][*eb*] as the number of different graphs following the requirements that can be built using the first *i* nodes, with *ew* even-white nodes, *ow* odd-white nodes and *eb* even-black nodes (the number of odd-black nodes *ob* = *i* - *ew* - *ow* - *eb*). We will figure out how to calculate such value. For the sake of simplicity, let's consider the current node — the {*i*}*th* node to be a white node. 265 266 We can notice a few things: 267 268 * If none of the previous *i* - 1 nodes connects to the current node, the current node becomes an odd-white node (the only alternating path that ends the current node is the node itself). 269 * How the previous white nodes connect to the current node does not matter. There are 2*ow* + *ew* - 1 ways to add edges between the previous white nodes and the current node. 270 * How the previous even-black nodes connect to the current node does not matter, as it does not change the state of the current white node (i.e. odd-white to even-white or even-white to odd-white). There are 2*eb* ways to add edges between the previous even-black nodes and the current node. 271 * If there are an odd number of previous odd-black nodes that have edges to the current node, the current node becomes an even-white node. There are  ways to do this. 272 * If there are an even number of previous odd-black nodes that have edges to the current node, the current node becomes an odd-white node. There are  ways to do this. 273 274 In conclusion, we can figure out that: 275 276  277 278 It is worth mentioning that we can use the same analogy to process when the current node is black. 279 280 In total, we process through *n*4 states, with an *O*(*n*) iteration for each stage, so the time complexity is *O*(*n*5). However, with precomputation of  and  for every value of *ob*, we can optimize the time complexity to *O*(*n*4). 281 282 Time complexity: *O*(*n*4). 283 284 **Code** 285 286 ``` 287 #include <iostream> 288 using namespace std; 289 290 const int N = 55, MOD = 1E9 + 7; 291 292 int n, p, c[N]; 293 long long ans = 0, pw[N], fct[N], inv[N], od[N], ev[N], f[N][N][N][N]; 294 295 long long power(int u, int p) 296 { 297 if (p == 0) 298 return 1; 299 long long ret = power(u, p >> 1); 300 (ret *= ret) %= MOD; 301 if (p & 1) 302 (ret *= u) %= MOD; 303 return ret; 304 } 305 306 long long C(int n, int k) 307 { 308 return fct[n] * inv[k] % MOD * inv[n - k] % MOD; 309 } 310 311 void init() 312 { 313 f[0][0][0][0] = 1; 314 pw[0] = 1; 315 fct[0] = 1; 316 for (int i = 1; i < N; i++) 317 { 318 pw[i] = pw[i - 1] * 2 % MOD; 319 fct[i] = fct[i - 1] * i % MOD; 320 } 321 inv[N - 1] = power(fct[N - 1], MOD - 2); 322 for (int i = N - 2; i >= 0; i--) 323 inv[i] = inv[i + 1] * (i + 1) % MOD; 324 for (int i = 0; i < N; i++) 325 { 326 for (int j = 0; j <= i; j += 2) 327 (ev[i] += C(i, j)) %= MOD; 328 for (int j = 1; j <= i; j += 2) 329 (od[i] += C(i, j)) %= MOD; 330 } 331 } 332 333 void find_ans(int ob, int eb, int ow, int ew, int col, long long &ret) 334 { 335 // current node is even-white 336 if (col != 0 && ew != 0) 337 (ret += f[ob][eb][ow][ew - 1] * pw[ow + ew - 1 + eb] % MOD * od[ob] % MOD) %= MOD; 338 339 // current node is odd-white 340 if (col != 0 && ow != 0) 341 (ret += f[ob][eb][ow - 1][ew] * pw[ow - 1 + ew + eb] % MOD * ev[ob] % MOD) %= MOD; 342 343 // current node is even-black 344 if (col != 1 && eb != 0) 345 (ret += f[ob][eb - 1][ow][ew] * pw[ob + eb - 1 + ew] % MOD * od[ow] % MOD) %= MOD; 346 347 // current node is odd-black 348 if (col != 1 && ob != 0) 349 (ret += f[ob - 1][eb][ow][ew] * pw[ob - 1 + eb + ew] % MOD * ev[ow] % MOD) %= MOD; 350 } 351 352 int main() 353 { 354 init(); 355 scanf("%d%d", &n, &p); 356 for (int i = 1; i <= n; i++) 357 scanf("%d", c + i); 358 for (int i = 1; i <= n; i++) 359 for (int ob = 0; ob <= i; ob++) 360 for (int eb = 0; ob + eb <= i; eb++) 361 for (int ow = 0; ob + eb + ow <= i; ow++) 362 { 363 int ew = i - ob - eb - ow; 364 find_ans(ob, eb, ow, ew, c[i], f[ob][eb][ow][ew]); 365 if (i == n && ((ob + ow) & 1) == p) 366 (ans += f[ob][eb][ow][ew]) %= MOD; 367 } 368 printf("%lld", ans); 369 return 0; 370 } 371 ```