2082.md (49746B)
1 Source: https://codeforces.com/blog/entry/140702 2 3 Sorry for the late editorial. Our problem setters were so exhausted with the offline competition yesterday that they really need some good rest. 4 5 Despite the unexpected and unpleasant incidents that occurred, we are truly surprised and grateful that so many of you still participated in this competition! We sincerely hope you enjoyed it! 6 7 (Gratitude for all you guys from [Ecrade_](/profile/Ecrade_ "Grandmaster Ecrade_"): I felt so heartbroken when I heard about the unexpected issues, but seeing so many people in the comments comforting us, sharing thoughtful and positive messages that showed genuine empathy, and continuing to fully support our competition even after the wasted time, I was deeply moved. Thank you all! Codeforces truly embodies such a positive and uplifting community spirit!) 8 9 [2082A - Binary Matrix](/contest/2082/problem/A "Codeforces Round 1010 (Div. 2, Unrated)") 10 Idea: [Ecrade_](/profile/Ecrade_ "Grandmaster Ecrade_") 11 12 **Hint** 13 14 Do we really have to consider the problem on the whole matrix? 15 16 **Solution** 17 18 Let $r$ be the number of rows where the bitwise XOR of all the numbers in it is $1$, and $c$ be the number of columns where the bitwise XOR of all the numbers in it is $1$. Our goal is to make both $r$ and $c$ zero. 19 20 When we change an element in the matrix, both $r$ and $c$ change by exactly one. Thus, it's not hard to see that the answer is $\max (r,c)$. 21 22 The time complexity is $O(\sum nm)$. 23 24 **Code** 25 26 ``` 27 #include<bits/stdc++.h> 28 using namespace std; 29 typedef long long ll; 30 ll t,n,m,r,c; 31 char s[1009]; 32 bool a[1009][1009]; 33 inline ll read(){ 34 ll s = 0,w = 1; 35 char ch = getchar(); 36 while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();} 37 while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar(); 38 return s * w; 39 } 40 int main(){ 41 t = read(); 42 while (t --){ 43 n = read(),m = read(),r = c = 0; 44 for (ll i = 1;i <= n;i += 1){ 45 scanf("%s",s + 1); 46 for (ll j = 1;j <= m;j += 1) a[i][j] = s[j] - '0'; 47 } 48 for (ll i = 1;i <= n;i += 1){ 49 bool sum = 0; 50 for (ll j = 1;j <= m;j += 1) sum ^= a[i][j]; 51 if (sum) r += 1; 52 } 53 for (ll j = 1;j <= m;j += 1){ 54 bool sum = 0; 55 for (ll i = 1;i <= n;i += 1) sum ^= a[i][j]; 56 if (sum) c += 1; 57 } 58 printf("%lld\n",max(r,c)); 59 } 60 return 0; 61 } 62 ``` 63 64 [2082B - Floor or Ceil](/contest/2082/problem/B "Codeforces Round 1010 (Div. 2, Unrated)") 65 Idea: [Ecrade_](/profile/Ecrade_ "Grandmaster Ecrade_"), [FairyWinx](/profile/FairyWinx "Grandmaster FairyWinx") 66 67 **Hint 1** 68 69 Consider $x$ in binary form. 70 71 **Hint 2** 72 73 What are all possible values of $x$ after $n+m$ operations? 74 75 **Solution** 76 77 Let's consider how to find the maximum value first. 78 79 Consider $x$ in binary form. Let the number formed by the last $n+m$ bits of $x$ be denoted as $r$, and the remaining higher bits form the number $l$ (for instance, if $x=12=(1100)_2$, $n=1$, $m=2$, then $l=1=(1)_2$, $r=4=(100)_2$), then the final value of $x$ after $n+m$ operations will be either $l$ or $l+1$, depending on whether a carry-over occurs in $r$ during the last operation. 80 81 If there are no $1$s in the higher $m$ bits of $r$, then the carry-over in $r$ during the last operation can never occur (operating on some small tests may give you a better understanding). Otherwise, we can choose to perform $n$ floor operations first followed by $m$ ceil operations, which can guarantee a carry-over in $r$ during the last operation. 82 83 This demonstrates that performing $n$ floor operations first followed by $m$ ceil operations will always yield the maximum value. Similarly, performing $m$ ceil operations first followed by $n$ floor operations will always produce the minimum value. We can simply simulate these operations because after $O(\log x)$ same operations, $x$ will remain unchanged. 84 85 The time complexity is $O(T\log x)$. 86 87 **Code** 88 89 ``` 90 #include<bits/stdc++.h> 91 using namespace std; 92 typedef long long ll; 93 ll t,x,n,m; 94 inline ll read(){ 95 ll s = 0,w = 1; 96 char ch = getchar(); 97 while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();} 98 while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar(); 99 return s * w; 100 } 101 ll F(ll x,ll n){ 102 while (n --){ 103 if (!x) return x; 104 x = (x >> 1); 105 } 106 return x; 107 } 108 ll C(ll x,ll n){ 109 while (n --){ 110 if (x <= 1) return x; 111 x = ((x + 1) >> 1); 112 } 113 return x; 114 } 115 int main(){ 116 t = read(); 117 while (t --){ 118 x = read(),n = read(),m = read(); 119 printf("%lld %lld\n",F(C(x,m),n),C(F(x,n),m)); 120 } 121 return 0; 122 } 123 ``` 124 125 [2081A - Math Division](/contest/2081/problem/A "Codeforces Round 1010 (Div. 1, Unrated)") 126 Idea: [Ecrade_](/profile/Ecrade_ "Grandmaster Ecrade_") 127 128 **Hint 1** 129 130 Consider $x$ in binary form. 131 132 **Hint 2** 133 134 What are all possible numbers of operations to make $x$ equal to $1$? 135 136 **Hint 3** 137 138 Consider using dynamic programming to calculate the answer. 139 140 **Solution** 141 142 Similar to the previous problem, the possible number of operations can only be $n-1$ or $n$, depending on whether a carry-over occurs in $x$ during the $(n-1)$ -th operation. 143 144 We can use dynamic programming to compute the probability of a carry-over occurring during the $(n-1)$ -th operation. 145 146 Let $f_i$ denote the probability of a carry-over occurring at the $i$ -th least significant bit. The recurrence relation is: 147 148 $ f_i = \begin{cases} \dfrac{1}{2} \times f_{i-1} & x_i = 0 \\ \dfrac{1}{2} \times (1 - f_{i-1}) + f_{i-1} & x_i = 1 \end{cases} $ 149 150 The final answer is given by $n-1+f_{n-1}$. 151 152 The time complexity is $O(\sum n)$. 153 154 **Code** 155 156 ``` 157 #include<bits/stdc++.h> 158 using namespace std; 159 typedef long long ll; 160 const ll inv2 = 5e8 + 4,mod = 1e9 + 7; 161 ll t,n; 162 char s[1000009]; 163 inline ll read(){ 164 ll s = 0,w = 1; 165 char ch = getchar(); 166 while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();} 167 while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar(); 168 return s * w; 169 } 170 int main(){ 171 t = read(); 172 while (t --){ 173 n = read(),scanf("%s",s + 1); 174 ll ans = 0; 175 for (ll i = n;i > 1;i -= 1) ans = (ans + (s[i] == '1')) * inv2 % mod; 176 printf("%lld\n",(n - 1 + ans) % mod); 177 } 178 return 0; 179 } 180 ``` 181 182 [2081B - Balancing](/contest/2081/problem/B "Codeforces Round 1010 (Div. 1, Unrated)") 183 Idea: [Ecrade_](/profile/Ecrade_ "Grandmaster Ecrade_") 184 185 **Hint 1** 186 187 Let's only consider the comparison between adjacent pairs first. Call a pair $(a_i,a_{i+1})$ an inversion pair if $a_i \gt a_{i+1}$. 188 189 In each operation, how can the number of inversion pairs change? 190 191 **Hint 2** 192 193 Under what circumstances can we decrease the maximum number of inversion pairs in every operation? 194 195 **Solution** 196 197 Let's only consider the comparison between adjacent pairs first. Call a pair $(a_i,a_{i+1})$ an inversion pair if $a_i \gt a_{i+1}$. Our goal is to decrease the number of inversion pairs to zero. 198 199 If we choose to replace $a_l,a_{l+1},\ldots,a_r$, only the comparison between $(a_{l-1},a_l)$ and $(a_{r},a_{r+1})$ can change, which means we can eliminate at most two inversion pairs in one operation. Let $s$ be the number of inversion pairs in $a_1,a_2,\ldots,a_n$, then a lower bound of the answer is $l=\left\lceil\dfrac{s}{2}\right\rceil$. 200 201 #### **Case 1: $s \gt 0$ and $2\mid s$** 202 203 In order to obtain the lower bound $l$, each operation must eliminate exactly two inversion pairs. This necessitates that we cannot alter any numbers before the first element $a_{p_1}$ of the first inversion pair or after the second element $a_{p_2}$ of the last inversion pair. (Why?) 204 205 An intuitive idea is that the difference between $a_{p_1}$ and $a_{p_2}$ should be as large as possible (more precisely, $a_{p_2} - a_{p_1} \geq p_2 - p_1$), so that a strictly increasing sequence can be "accommodated" between them. It is not difficult to constructively prove by recursion that this condition is both necessary and sufficient. 206 207 In other words, when $a_{p_2} - a_{p_1} \geq p_2 - p_1$, the answer is $l$; otherwise, an additional operation is required, making the answer $l+1$. 208 209 #### **Case 2: $s=0$ or $2\not\mid s$** 210 211 It's not difficult to prove that the answer in this case is $l$. (Why?) 212 213 The time complexity is $O(\sum n)$. 214 215 **Code** 216 217 ``` 218 #include<bits/stdc++.h> 219 using namespace std; 220 typedef long long ll; 221 ll t,n,a[200009]; 222 inline ll read(){ 223 ll s = 0,w = 1; 224 char ch = getchar(); 225 while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();} 226 while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar(); 227 return s * w; 228 } 229 int main(){ 230 t = read(); 231 while (t --){ 232 n = read(); 233 for (ll i = 1;i <= n;i += 1) a[i] = read(); 234 ll ans = 0,pos1 = 0,pos2 = 0; 235 for (ll i = 1;i < n;i += 1) if (a[i] > a[i + 1]){ 236 ans += 1,pos2 = i + 1; 237 if (!pos1) pos1 = i; 238 } 239 if ((ans & 1) || (pos1 && a[pos2] - a[pos1] < pos2 - pos1)) printf("%lld\n",(ans >> 1) + 1); 240 else printf("%lld\n",ans >> 1); 241 } 242 return 0; 243 } 244 ``` 245 246 [2081C - Quaternary Matrix](/contest/2081/problem/C "Codeforces Round 1010 (Div. 1, Unrated)") 247 Idea: [Ecrade_](/profile/Ecrade_ "Grandmaster Ecrade_") 248 249 **Hint 1** 250 251 Do we really have to consider the problem on the whole matrix? 252 253 **Hint 2** 254 255 Use greedy algorithm and guess some possible conclusions. Can you prove them (or construct some counterexamples) ? 256 257 **Solution** 258 259 The problem can be rephrased as follows: Let the XOR sum of each row be $ r_1, r_2, \ldots, r_n $, and the XOR sum of each column be $ c_1, c_2, \ldots, c_m $. In each operation, we can choose any $ 1 \le i \le n $, $ 1 \le j \le m $, and $ 0 \le x \le 3 $, then let $ r_i \leftarrow r_i \oplus x $ and $ c_j \leftarrow c_j \oplus x $. The goal is to determine the minimum number of operations required to make all $ r_1, r_2, \ldots, r_n $ and $ c_1, c_2, \ldots, c_m $ zero. 260 261 Let $ R_x\ ( 0 \le x \le 3 )$ denote the count of $ x $ in $ r_1, r_2, \ldots, r_n $, and $ C_x $ denote the count of $ x $ in $ c_1, c_2, \ldots, c_m $. A trivial upper bound for the answer is $ s = R_1 + R_2 + R_3 + C_1 + C_2 + C_3 $, which corresponds to the scenario where each operation only zeros out one of $ r_i $ and $ c_j $. 262 263 To reduce the number of operations, we can consider grouping the non-zero elements in $ r_1, \ldots, r_n, c_1, \ldots, c_m $ into disjoint groups where: 264 265 1. The XOR sum of each group is zero. 266 2. Each group contains at least one element from $ r $ and one from $ c $. 267 268 For such a group, we can reduce the number of operations by one, as there always exists an operation which can zero out both $ r_i $ and $ c_j $. Thus, the goal is to maximize the number of such groups, and the minimum number of operations will be $s - \text{(number of groups formed)}$. 269 270 Define the following group types: 271 272 * $ P_2 $: Groups of the form $(R_1,C_1)$, $(R_2,C_2)$ or $(R_3,C_3)$. 273 * $ P_3 $: Groups of the form $(R_1,R_2,C_3)$, $(R_1,C_2,C_3)$, $(R_1,C_2,R_3)$, $(C_1,C_2,R_3)$, $(C_1,R_2,R_3)$ or $(C_1,R_2,C_3)$. 274 * $ P_4 $: Groups of the form $(R_1,R_1,C_2,C_2)$, $(R_1,R_1,C_3,C_3)$, $(R_2,R_2,C_1,C_1)$, $(R_2,R_2,C_3,C_3)$, $(R_3,R_3,C_1,C_1)$ or $(R_3,R_3,C_2,C_2)$. 275 276 **Conclusion 1:** There exists an optimal solution where all groups are of the form $ P_2 $, $ P_3 $, or $ P_4 $. 277 278 **Brief Proof** 279 280 * Each group must have size at least 2. Groups of size 2 or 3 can only be $ P_2 $ or $ P_3 $. 281 * Groups of size 4 not conforming to $ P_4 $ (e.g., $ (R_1, R_1, R_1, C_1) $) can be decomposed into at least one $ P_2 $. 282 * Larger groups can be decomposed into combinations of $ P_2 $, $ P_3 $, and $ P_4 $. 283 284 **Conclusion 2:** There exists an optimal solution where all $ P_3 $ groups share the same structure, and so do all $ P_4 $ groups. 285 286 **Brief Proof** 287 288 * Two different $ P_3 $ groups can be decomposed into at least two $ P_2 $ or at least one $ P_2 $ and one $ P_4 $. 289 * Two different $ P_4 $ groups can be decomposed into at least two $ P_2 $ or at least two $ P_3 $. 290 291 **Conclusion 3:** There exists an optimal solution where the elements in $ P_4 $ groups are a subset of those in $ P_3 $ groups (e.g., if $ P_3 $ is $ (R_1, R_2, C_3) $, then $ P_4 $ can only be $ (R_1, R_1, C_3, C_3) $ or $ (R_2, R_2, C_3, C_3) $). The proof is analogous to Conclusion 2 and is left as an exercise. 292 293 Based on these conclusions, the optimal strategy is: first form as many $P_2$ groups as possible; then form as many $P_3$ groups as possible from the remaining elements; then form as many $P_4$ groups as possible from the remaining elements. 294 295 After grouping, each group can be zeroed out with one less operation. Note that the remaining ungrouped elements require individual operations. 296 297 The time complexity is $O(\sum nm)$. 298 299 **Code** 300 301 ``` 302 #include<bits/stdc++.h> 303 using namespace std; 304 typedef long long ll; 305 ll t,n,m,a[1009][1009]; 306 char s[1009]; 307 vector <ll> row[4],col[4]; 308 inline ll read(){ 309 ll s = 0,w = 1; 310 char ch = getchar(); 311 while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();} 312 while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar(); 313 return s * w; 314 } 315 int main(){ 316 t = read(); 317 while (t --){ 318 n = read(),m = read(); 319 for (ll i = 1;i <= 3;i += 1) row[i].clear(),col[i].clear(); 320 for (ll i = 1;i <= n;i += 1){ 321 scanf("%s",s + 1); 322 for (ll j = 1;j <= m;j += 1) a[i][j] = s[j] - '0'; 323 } 324 for (ll i = 1;i <= n;i += 1){ 325 ll sum = 0; 326 for (ll j = 1;j <= m;j += 1) sum ^= a[i][j]; 327 if (sum) row[sum].emplace_back(i); 328 } 329 for (ll j = 1;j <= m;j += 1){ 330 ll sum = 0; 331 for (ll i = 1;i <= n;i += 1) sum ^= a[i][j]; 332 if (sum) col[sum].emplace_back(j); 333 } 334 ll ans = 0; 335 for (ll i = 1;i <= 3;i += 1){ 336 while (row[i].size() && col[i].size()){ 337 ans += 1; 338 a[row[i].back()][col[i].back()] ^= i; 339 row[i].pop_back(),col[i].pop_back(); 340 } 341 } 342 for (ll i = 1;i <= 3;i += 1){ 343 ll j = i % 3 + 1,k = j % 3 + 1; 344 while (row[i].size() && col[j].size() && col[k].size()){ 345 ans += 2; 346 a[row[i].back()][col[j].back()] ^= j; 347 a[row[i].back()][col[k].back()] ^= k; 348 row[i].pop_back(),col[j].pop_back(),col[k].pop_back(); 349 } 350 while (col[i].size() && row[j].size() && row[k].size()){ 351 ans += 2; 352 a[row[j].back()][col[i].back()] ^= j; 353 a[row[k].back()][col[i].back()] ^= k; 354 col[i].pop_back(),row[j].pop_back(),row[k].pop_back(); 355 } 356 } 357 for (ll i = 1;i <= 3;i += 1) for (ll j = 1;j <= 3;j += 1) if (i != j){ 358 while (row[i].size() >= 2 && col[j].size() >= 2){ 359 ll r1 = row[i].back(); row[i].pop_back(); 360 ll r2 = row[i].back(); row[i].pop_back(); 361 ll c1 = col[j].back(); col[j].pop_back(); 362 ll c2 = col[j].back(); col[j].pop_back(); 363 ans += 3; 364 a[r1][c1] ^= i; 365 a[r2][c1] ^= (i ^ j); 366 a[r2][c2] ^= j; 367 } 368 } 369 for (ll i = 1;i <= 3;i += 1){ 370 while (row[i].size()) ans += 1,a[row[i].back()][1] ^= i,row[i].pop_back(); 371 while (col[i].size()) ans += 1,a[1][col[i].back()] ^= i,col[i].pop_back(); 372 } 373 printf("%lld\n",ans); 374 for (ll i = 1;i <= n;i += 1,puts("")) for (ll j = 1;j <= m;j += 1) printf("%lld",a[i][j]); 375 } 376 return 0; 377 } 378 ``` 379 380 [2081D - MST in Modulo Graph](/contest/2081/problem/D "Codeforces Round 1010 (Div. 1, Unrated)") 381 Idea: [newbiewzs](/profile/newbiewzs "International Master newbiewzs") 382 383 **Hint** 384 385 There are only $O(n\log n)$ edges that are truly useful in the whole graph. 386 387 **Solution** 388 389 First, for vertices with the same weight, they can naturally be treated as a single vertex. 390 391 We observe that in the interval of weights $(kx,(k+1)x)\ (k\ge 1)$, only the smallest $y$ is useful. It is because, if $x \lt y \lt z \lt 2x$, connecting edges $(x,y)$ and $(y,z)$ will always be better than connecting $(x,y)$ and $(x,z)$. 392 393 Therefore, for a vertex with weight $x$, we enumerate $k = x , 2 x , \ldots , \lfloor \frac{n}{x}\rfloor\cdot x$. For each $k$, we connect $x$ to the smallest $y$ that is greater than or equal to $k$. 394 395 It can be proven that this approach guarantees a connected graph (since connecting only the first edge larger than $x$ already forms a connected structure). 396 397 This method generates $O(n\log n)$ edges (due to the harmonic series property). Directly applying Kruskal's algorithm would result in a time complexity of $O(n\log^2 n)$. With radix sort, this can be optimized to $O(n\log n)$. 398 399 **Code** 400 401 ``` 402 #include<iostream> 403 #include<cstdio> 404 #include<algorithm> 405 #include<string.h> 406 #include<vector> 407 #include<queue> 408 #include<map> 409 #include<ctime> 410 #include<bitset> 411 #include<set> 412 #include<math.h> 413 //#include<unordered_map> 414 #define fi first 415 #define se second 416 #define mp make_pair 417 #define pii pair<int,int> 418 #define pb push_back 419 #define pil pair<int,long long> 420 #define pll pair<long long,long long> 421 #define vi vector<int> 422 #define vl vector<long long> 423 #define ci ios::sync_with_stdio(false) 424 //#define int long long 425 using namespace std; 426 typedef long long ll; 427 typedef unsigned long long ull; 428 int read(){ 429 char c=getchar(); 430 ll x=1,s=0; 431 while(c<'0'||c>'9'){ 432 if(c=='-')x=-1;c=getchar(); 433 } 434 while(c>='0'&&c<='9'){ 435 s=s*10+c-'0';c=getchar(); 436 } 437 return s*x; 438 } 439 const int N=5e5+55; 440 int MAXN=0; 441 int n,tot,ans,maxx,f[N],siz[N],p[N],bj[N],pre[N],suf[N],pos[N]; 442 struct node{ 443 int from,to,dis; 444 }a[N*20]; 445 int cmp(node x,node y){ 446 return x.dis<y.dis; 447 } 448 int find(int x){ 449 if(f[x]!=x)return f[x]=find(f[x]); 450 else return x; 451 } 452 void merge(int x,int y){ 453 x=find(x);y=find(y); 454 if(siz[x]<siz[y])swap(x,y); 455 siz[x]+=siz[y]; 456 f[y]=x; 457 } 458 int T; 459 int main(){ 460 T=read(); 461 while(T--) 462 { 463 tot=ans=maxx=0; 464 for(int i=1;i<=MAXN;++i) 465 { 466 f[i]=siz[i]=p[i]=bj[i]=pre[i]=suf[i]=pos[i]=0; 467 } 468 for(int i=0;i<=MAXN*19;++i) 469 a[i].from=a[i].to=a[i].dis=0; 470 471 472 473 n=read(); 474 MAXN=n; 475 for(int i=1;i<=n;i++)p[i]=read(),bj[p[i]]=1,maxx=max(maxx,p[i]),MAXN=max(MAXN,p[i]); 476 sort(p+1,p+n+1); 477 for(int i=1;i<=maxx;i++){ 478 if(bj[i])pre[i]=i; 479 else pre[i]=pre[i-1]; 480 } 481 for(int i=maxx;i>=1;i--){ 482 if(bj[i])suf[i]=i; 483 else suf[i]=suf[i+1]; 484 } 485 for(int i=1;i<=n;i++)pos[p[i]]=i; 486 for(int i=1;i<=n;i++){ 487 if(p[i]==p[i-1]){ 488 a[++tot]={i,i-1,0}; 489 continue; 490 } 491 for(int k=1;k*p[i]<=maxx;k++){ 492 int tmy=0; 493 if(bj[k*p[i]] and k!=1){ 494 a[++tot]={pos[k*p[i]],i,0}; 495 continue; 496 } 497 if(suf[k*p[i]+1]<=(k+1)*p[i])tmy=suf[k*p[i]+1]; 498 if(!tmy)continue; 499 int cost=abs(k*p[i]-tmy); 500 a[++tot]={pos[tmy],i,cost}; 501 } 502 } 503 sort(a+1,a+tot+1,cmp); 504 for(int i=1;i<=n;i++)f[i]=i,siz[i]=1; 505 for(int i=1;i<=tot;i++){ 506 if(find(a[i].from)!=find(a[i].to)){ 507 merge(a[i].from,a[i].to); 508 ans+=a[i].dis; 509 } 510 } 511 cout<<ans<<endl; 512 } 513 return 0; 514 } 515 ``` 516 517 [2081E - Quantifier](/contest/2081/problem/E "Codeforces Round 1010 (Div. 1, Unrated)") 518 Idea: [chen_03](/profile/chen_03 "Master chen_03") 519 520 **Hint 1** 521 522 Move each chip as deep as possible in descending order of labels. Can we simplify the operations after that? 523 524 **Hint 2** 525 526 Now we only need to move the chips upward and swap adjacent chips with the same color. What can we do after that? 527 528 **Hint 3** 529 530 We can perform dynamic programming (DP) to calculate the numbers. What information do we need to record? 531 532 **Hint 4** 533 534 We need to record the color and the length of the top monochromatic segment. How can we perform the DP in $\mathcal{O}(m^2)$ time complexity? 535 536 **Solution** 537 538 First, in descending order of labels, move each chip to the deepest possible position successively. It can be shown that this allows each chip to reach the theoretically deepest position it can attain. Consequently, every final state can be obtained from this configuration by performing only upward moves of chips and swaps of adjacent chips with the same color. 539 540 Next comes the process of moving chips upward while performing dynamic programming (DP). Let $e_u$ denote the edge from node $u$ to its parent. Assume we have decided the order of all the chips in subtree $u$ (except the ones on $e_u$), and we need to merge them with the original chips on $e_u$. If the bottom chip on $e_u$ shares color with the subtree's top chip, we need to know the length of the subtree's topmost maximal monochromatic contiguous segment to calculate the number of ways to merge the two parts, i.e., if the length of the bottommost segment on $e_u$ is $x$ and the length of the topmost segment of the subtree is $y$, we have $\dbinom{x+y}{x}$ ways to combine them. So we need to record the color and the length of the top segment. 541 542  543 544 Let $f_{u,0/1,i}$ denote the number of permutation schemes on $e_u$ after moving all the chips in subtree $u$ to $e_u$, where: 545 546 * The topmost chip on $e_u$ is black/white (0/1). 547 * The length of the topmost maximal monochromatic contiguous segment on $e_u$ is $i$. 548 549 When calculating $f_{u,0/1,i}$ for all $i$, we first merge the DP states of all the subtrees of node $u$, and then merge the original chips on $e_u$ into the resulting DP states. 550 551 **Subtree merging**: Assume we merge two subtrees $v$ and $w$. Let $S$ and $T$ denote the number of chips on $e_v$ and $e_w$ respectively, and let $g_{0/1,i}$ be a temporary DP array initialized to all zeros. 552 553 Let's consider two cases. 554 555 #### **Case 1: Different colors at tops of $e_v$ and $e_w$** 556 557 Suppose the top chip comes from $e_v$ after merging. Then the maximal monochromatic segment length from $e_w$ becomes irrelevant, and therefore let $h_c=\sum_{i=1}^T f_{w,c,i}$. If the top chip of $e_w$ would split the top segment of $e_v$, enumerate split positions. The split position should be strictly inside the top segment of $e_v$. 558 559 $g_{c,i}\leftarrow g_{c,i} + \dbinom{S-i+T-1}{T-1} h_{1-c} \sum_{k=i+1}^S f_{v,c,k}\ (1\le i\le S)$ 560 561 Otherwise, the position of the top chip of $e_w$ becomes irrelevant. 562 563 $g_{c,i}\leftarrow g_{c,i} + \dbinom{S-i+T}{T} h_{1-c} f_{v,c,i}$ 564 565  566 567 With suffix sum optimization, this achieves $\mathcal{O}(m^2)$ time complexity. 568 569 #### **Case 2: Same color at tops** 570 571 If there are only chips of this color on both edges: 572 573 $g_{c,S+T}\leftarrow g_{c,S+T} + \dbinom{S+T}{T} f_{v,c,S} f_{w,c,T}$ 574 575 Otherwise, assume the topmost different-colored chip is from subtree $w$ after merging. Enumerate insertion positions where this chip splits the top segment of the other (not necessarily strictly inside the segment). 576 577 $g_{c,i+j}\leftarrow g_{c,i+j} + \dbinom{i+j}{j} \dbinom{S-i+T-j-1}{T-j-1} f_{w,c,j} \sum_{k=i}^S f_{v,c,k}\ (0\le i\le S,\ 1\le j \lt T)$ 578 579 (Similar transition equation for $v$.) 580 581  582 583 With suffix sum optimization, this forms a tree knapsack DP with $\mathcal{O}(m^2)$ time complexity. 584 585 --- 586 587 After computing $g_{0/1,i}$, we can treat $g$ as the DP states of a subtree, and continue to perform the process above. 588 589 **Merging original chips on $e_u$ into the results**: We first account for internal permutations of original monochromatic segments. After that, if the bottom chip on $e_u$ shares color with merged subtrees' top chip (with segment lengths $x$ and $y$), multiply the DP state by $\dbinom{x+y}{x}$. 590 591 Assuming $n$ and $m$ are of the same order, the overall time complexity is $\mathcal{O}(m^2)$. 592 593 **Code** 594 595 ``` 596 #include <bits/stdc++.h> 597 #define eb emplace_back 598 using namespace std; 599 typedef long long ll; 600 const int p=998244353; 601 int T,n,m,fa[5005],col[5005],d[5005],stk[5005],top,ct[5005][2]; 602 int C[5005][5005],fac[5005],siz[5005],f[5005][2][5005],g[2][5005],ans; 603 vector<int> to[5005],vec[5005]; 604 inline void diff(int u,int v){ 605 int S=siz[u],T=siz[v]; 606 for(int x=0,A,B;x<2;++x){ 607 A=B=0; 608 for(int j=1;j<=T;++j)B=(B+f[v][x^1][j])%p; 609 for(int i=S;i>=1;--i){ 610 g[x][i]=(g[x][i]+((ll)A*C[S+T-i-1][T-1]+(ll)f[u][x][i]*C[S+T-i][T])%p*B)%p; 611 A=(A+f[u][x][i])%p; 612 } 613 } 614 } 615 inline void same1(int u,int v){ 616 int S=siz[u],T=siz[v]; 617 for(int x=0,A,B;x<2;++x){ 618 for(int i=1;i<S;++i){ 619 if(!(A=f[u][x][i]))continue; 620 B=0; 621 for(int j=T;j>=0;--j){ 622 B=(B+f[v][x][j])%p; 623 g[x][i+j]=(g[x][i+j]+(ll)A*B%p*C[i+j][j]%p*C[S-i-1+T-j][T-j])%p; 624 } 625 } 626 } 627 } 628 inline void same(int u,int v){ 629 same1(u,v),same1(v,u); 630 int S=siz[u],T=siz[v]; 631 for(int x=0;x<2;++x) 632 g[x][S+T]=(g[x][S+T]+(ll)f[u][x][S]*f[v][x][T]%p*C[S+T][T])%p; 633 } 634 inline void merge(int u,int v){ 635 for(int i=1;i<=siz[u]+siz[v];++i)g[0][i]=g[1][i]=0; 636 diff(u,v),diff(v,u),same(u,v); 637 siz[u]+=siz[v]; 638 for(int i=1;i<=siz[u];++i) 639 f[u][0][i]=g[0][i],f[u][1][i]=g[1][i]; 640 } 641 void dfs(int u){ 642 siz[u]=0; 643 for(auto v:to[u]){ 644 dfs(v); 645 if(!siz[v])continue; 646 if(siz[u])merge(u,v); 647 else{ 648 for(int i=1;i<=siz[v];++i) 649 f[u][0][i]=f[v][0][i],f[u][1][i]=f[v][1][i]; 650 siz[u]=siz[v]; 651 } 652 } 653 if(vec[u].empty())return; 654 int prd=1,L=vec[u].size(),c=vec[u][0],fir=0,lst=0,res=0; 655 for(int i=0,j=0;i<L;i=j){ 656 while(j<L && vec[u][i]==vec[u][j])++j; 657 if(i==0)fir=j-i; 658 if(j==L)lst=j-i; 659 prd=(ll)prd*fac[j-i]%p; 660 } 661 for(int i=siz[u]+1;i<=siz[u]+L;++i)f[u][0][i]=f[u][1][i]=0; 662 if(!siz[u])f[u][vec[u][L-1]][lst]=prd; 663 else if(fir==L){ 664 for(int i=siz[u];i>=1;--i){ 665 f[u][c][i+L]=(ll)f[u][c][i]*C[i+L][i]%p*fac[L]%p; 666 res=(res+f[u][c^1][i])%p; 667 f[u][c^1][i]=0; 668 } 669 for(int i=1;i<L;++i)f[u][c][i]=0; 670 f[u][c][L]=(ll)res*fac[L]%p; 671 } 672 else{ 673 for(int i=1;i<=siz[u];++i){ 674 res=(res+(ll)f[u][c][i]*C[i+fir][i]+f[u][c^1][i])%p; 675 f[u][0][i]=f[u][1][i]=0; 676 } 677 f[u][vec[u][L-1]][lst]=(ll)res*prd%p; 678 } 679 siz[u]+=L; 680 } 681 int main(){ 682 scanf("%d",&T); 683 while(T--){ 684 scanf("%d%d",&n,&m); 685 for(int i=0;i<=n;++i){ 686 to[i].clear(),vec[i].clear(); 687 ct[i][0]=ct[i][1]=0; 688 } 689 for(int i=1;i<=n;++i) 690 scanf("%d",fa+i),to[fa[i]].eb(i); 691 for(int i=1;i<=m;++i)scanf("%d",col+i); 692 for(int i=1;i<=m;++i)scanf("%d",d+i); 693 for(int i=m,u;i>=1;--i){ 694 top=0,u=d[i]; 695 while(u)stk[++top]=u,u=fa[u]; 696 for(int j=top;j>=1;--j){ 697 if(j>1 && !ct[stk[j]][col[i]^1])continue; 698 vec[stk[j]].eb(col[i]),++ct[stk[j]][col[i]]; 699 break; 700 } 701 } 702 C[0][0]=fac[0]=1; 703 for(int i=1;i<=m;++i){ 704 for(int j=1;j<=i;++j) 705 C[i][j]=(C[i-1][j-1]+C[i-1][j])%p; 706 C[i][0]=1; 707 fac[i]=(ll)fac[i-1]*i%p; 708 } 709 dfs(1),ans=0; 710 for(int i=1;i<=m;++i) 711 ans=((ll)ans+f[1][0][i]+f[1][1][i])%p; 712 printf("%d\n",ans); 713 } 714 return 0; 715 } 716 ``` 717 718 [2081F - Hot Matrix](/contest/2081/problem/F "Codeforces Round 1010 (Div. 1, Unrated)") 719 Idea: [18Michael](/profile/18Michael "Grandmaster 18Michael") 720 721 **Solution** 722 723 First, it is not difficult to observe that when $ n $ is odd, a solution exists if and only if $ n = 1 $. 724 725 When $ n $ is even, a solution always exists. 726 727 Consider the following construction: 728 729 Let $ n = 2m $. Use $(x, y)$ to denote the cell in the $ x $-th row and $ y $-th column of the matrix, and assume the top-left corner of the matrix is $(1, 1)$, while the bottom-right corner is $(n, n)$. 730 731 For $(a, b)$ and $(c, d)$, let $ k_1 = c - a $ and $ k_2 = d - b $. When $ |k_1| = |k_2| $, denote $(a, b) \sim (c, d)$ as: 732 733 * $(a, b), (a+1, b+1), \dots, (a+k_1, b+k_2)$ if $ k_1, k_2 \geq 0 $. 734 * $(a, b), (a+1, b-1), \dots, (a+k_1, b+k_2)$ if $ k_1 \geq 0, k_2 \leq 0 $. 735 * $(a, b), (a-1, b+1), \dots, (a+k_1, b+k_2)$ if $ k_1 \leq 0, k_2 \geq 0 $. 736 * $(a, b), (a-1, b-1), \dots, (a+k_1, b+k_2)$ if $ k_1, k_2 \leq 0 $. 737 738 For any $ 1 \leq i \leq m $, we alternately fill the numbers $ 2i-1 $ and $ 2i-2 $ in the cells along the paths $(1, 2i) \sim (n-2i+1, n)$, $(n-2i+2, n) \sim (n, n-2i+2)$, $(n, n-2i+1) \sim (2i, 1)$, and $(2i-1, 1) \sim (1, 2i-1)$. 739 740 An illustration for $ n = 10 $: 741 742  743 744 Next, we prove that this construction satisfies all the requirements of the problem: 745 746 * Each row and column of $ A $ is a permutation of $ 0 \sim n-1 $. 747 748 **Proof** 749 750 For each $ 1 \leq i \leq m $, color the cells containing the numbers $ 2i-1 $ and $ 2i-2 $ black and white alternately along the paths described above. It can be shown that each row and column contains exactly one black and one white cell, ensuring that $ 2i-1 $ and $ 2i-2 $ appear exactly once in each row and column. Thus, each row and column is a permutation of $ 0 \sim n-1 $. 751 752 * $ a_{i,j} + a_{i,n-j+1} = n-1 $ and $ a_{i,j} + a_{n-i+1,j} = n-1 $. 753 754 **Proof** 755 756 From the filling process, the cells containing $2i-1$ and $2i-2$ and the cells containing $n-2i+1$ and $n-2i$ are symmetric with respect to the midline between the $m$-th and $(m+1)$-th rows, as well as the midline between the $m$-th and $(m+1)$-th columns. This symmetry further ensures that $ 2i-1 $ and $ n-2i $ are symmetric, as are $ 2i-2 $ and $ n-2i+1 $. Therefore, both $ a_{i,j} + a_{i,n-j+1} = n-1 $ and $ a_{i,j} + a_{n-i+1,j} = n-1 $ are satisfied. 757 758 * All ordered pairs $ \langle a_{i,j}, a_{i,j+1} \rangle $ (for $ 1 \leq i \leq n, 1 \leq j \lt n $) are distinct, and all ordered pairs $ \langle a_{i,j}, a_{i+1,j} \rangle $ (for $ 1 \leq i \lt n, 1 \leq j \leq n $) are distinct. 759 760 **Proof** 761 762 For each $ 1 \leq i \leq m $, divide the cells containing $ 2i-1 $ and $ 2i-2 $ into four categories: 763 764 * First category: $(1, 2i) \sim (n-2i+1, n)$ 765 * Second category: $(n-2i+2, n) \sim (n, n-2i+2)$ 766 * Third category: $(n, n-2i+1) \sim (2i, 1)$ 767 * Fourth category: $(2i-1, 1) \sim (1, 2i-1)$ 768 769 For any $ 1 \leq i \lt j \leq m $: 770 771 * The first and third category cells of $ 2i-1, 2i-2 $ do not neighbor the first and third category cells of $ 2j-1, 2j-2 $ (since the sum of their coordinates is odd). 772 * The second and fourth category cells of $ 2i-1, 2i-2 $ do not neighbor the second and fourth category cells of $ 2j-1, 2j-2 $ (since the sum of their coordinates is even). 773 * The second and fourth category cells of $ 2i-1, 2i-2 $ do not have row-wise neighbors with the first and third category cells of $ 2j-1, 2j-2 $, and the first and third category cells of $ 2i-1, 2i-2 $ have exactly $2$ pairs of row-wise neighbors with the second and fourth category cells of $ 2j-1, 2j-2 $ (this can be visualized and proven through diagrams). 774 775 Specifically: 776 777 * The first category cells of $ 2i-1, 2i-2 $ and the second category cells of $ 2j-1, 2j-2 $ have exactly 2 pairs of row-wise neighbors: 778 779 + $ a_{n-i-j+1,n+i-j} = 2i-2 + ((i+j+1) \bmod 2), a_{n-i-j+1,n+i-j+1} = 2j-2 + ((i+j+1) \bmod 2) $ 780 + $ a_{n-i-j+2,n+i-j+1} = 2i-2 + ((i+j) \bmod 2), a_{n-i-j+2,n+i-j} = 2j-2 + ((i+j) \bmod 2) $ 781 * The first category cells of $ 2i-1, 2i-2 $ and the fourth category cells of $ 2j-1, 2j-2 $ have exactly 2 pairs of row-wise neighbors: 782 783 + $ a_{j-i,i+j-1} = 2i-2 + ((i+j) \bmod 2), a_{j-i,i+j} = 2j-2 + ((i+j+1) \bmod 2) $ 784 + $ a_{j-i+1,i+j} = 2i-2 + ((i+j+1) \bmod 2), a_{j-i+1,i+j-1} = 2j-2 + ((i+j) \bmod 2) $ 785 * The third category cells of $ 2i-1, 2i-2 $ and the second category cells of $ 2j-1, 2j-2 $ have exactly 2 pairs of row-wise neighbors: 786 787 + $ a_{n+i-j+1,n-i-j+2} = 2i-2 + ((i+j) \bmod 2), a_{n+i-j+1,n-i-j+1} = 2j-2 + ((i+j+1) \bmod 2) $ 788 + $ a_{n+i-j,n-i-j+1} = 2i-2 + ((i+j+1) \bmod 2), a_{n+i-j,n-i-j+2} = 2j-2 + ((i+j) \bmod 2) $ 789 * The third category cells of $ 2i-1, 2i-2 $ and the fourth category cells of $ 2j-1, 2j-2 $ have exactly 2 pairs of row-wise neighbors: 790 791 + $ a_{i+j,j-i+1} = 2i-2 + ((i+j+1) \bmod 2), a_{i+j,j-i} = 2j-2 + ((i+j+1) \bmod 2) $ 792 + $ a_{i+j-1,j-i} = 2i-2 + ((i+j) \bmod 2), a_{i+j-1,j-i+1} = 2j-2 + ((i+j) \bmod 2) $ 793 794 From the above analysis and by enumerating the parity of $i+j$, it is clear that all ordered pairs $ \langle a_{i,j}, a_{i,j+1} \rangle $ (for $ 1 \leq i \leq n, 1 \leq j \lt n $) are distinct, and all ordered pairs $ \langle a_{i,j}, a_{i+1,j} \rangle $ (for $ 1 \leq i \lt n, 1 \leq j \leq n $) are distinct. 795 796 In conclusion, we have provided a construction for even $ n $ and proven that it satisfies all the problem's requirements. 797 798 The time complexity is $O(\sum n^2)$. 799 800 **Code** 801 802 ``` 803 #include<bits/stdc++.h> 804 using namespace std; 805 int Test_num,n; 806 int a[3002][3002]; 807 void solve() 808 { 809 scanf("%d",&n); 810 if(n>=3 && (n&1))return (void)(puts("NO")); 811 puts("YES"); 812 if(n==1)return (void)(puts("0")); 813 for(int i=0;i<n;i+=2) 814 { 815 for(int j=1;j<=i+1;++j)a[j][i+2-j]=i+((j&1)^1); 816 for(int j=i+2;j<=n;++j)a[j][j-i-1]=i+((j&1)^1); 817 for(int j=1;j<=n-i-1;++j)a[j][i+1+j]=i+(j&1); 818 for(int j=n-i;j<=n;++j)a[j][2*n-i-j]=i+(j&1); 819 } 820 for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)printf("%d%c",a[i][j],j==n? '\n':' '); 821 } 822 int main() 823 { 824 for(scanf("%d",&Test_num);Test_num--;)solve(); 825 return 0; 826 } 827 ``` 828 829 [2081G1 - Hard Formula](/contest/2081/problem/G1 "Codeforces Round 1010 (Div. 1, Unrated)") 830 Idea: [Prean](/profile/Prean "Expert Prean") 831 832 **Hint 1** 833 834 If $g'(np)\neq g'(n)$ , then $p\le n$ unless $n=2,p=3$ or $n=1,p=2$ . 835 836 **Hint 2** 837 838 Think about the method of $\min 25$ sieve. 839 840 **Solution** 841 842 We define $\displaystyle g(n)=\frac n{\varphi(n)}=\prod_{p|n}\frac p{p-1},g'(n)=\lfloor g(n)\rfloor$. 843 844 It's easy to see that $res=\frac{N(N+1)}2-\sum_{i=1}^Ng'(i)\varphi(i)$. 845 846 Let's consider how to calculate $\sum_{i=1}^Ng'(i)\varphi(i)$. 847 848 $\texttt{Key observation 1}$:if $g'(np)\neq g'(n)$, then $p\le n$ unless $n=2,p=3$ or $n=1,p=2$. 849 850 **Proof** 851 852 $ \begin{aligned} &\because g(n)\cdot\frac p{p-1}\ge g'(np)\ge g'(n)+1\\ &\therefore p\le\frac{g'(n)+1}{g'(n)+1-g(n)}\\ &\therefore p\le\dfrac{\left\lfloor\dfrac n{\varphi(n)}\right\rfloor\varphi(n)+\varphi(n)}{\left\lfloor\dfrac n{\varphi(n)}\right\rfloor\varphi(n)+\varphi(n)-n}\\ &\texttt{let}\ x=\left\lfloor\dfrac n{\varphi(n)}\right\rfloor\varphi(n)+\varphi(n)-n\ge 1\\ &\therefore p\le\dfrac{x+n}x\le n+1\\ \end{aligned} $ 853 854 if $p=n+1$, then $\dfrac{x+n}x=n+1\implies x=1\implies \left(1+\left\lfloor \dfrac n{\phi(n)}\right\rfloor\right)\varphi(n) = n+1 \implies \varphi(n)\mid n+1$. 855 856 if $n\gt 2$ then $\varphi(n)\ge 2$, but $\varphi(n)\mid n+1=p$, which is contradict the fact that $p$ is a prime number. 857 858 The case of $n\le 2$ is easy to check. 859 860 Therefore, all the prime factors $p$ that $\gt \sqrt N$ wouldn't change the number of $g'(n)$. 861 862 Use a linear sieve to find all the prime numbers $\le \sqrt N$, following the approach for handling composite numbers in the min25 sieve: 863 864 Let's define: 865 866 $s(n,k)=\varphi(n)\sum_{k\leq p\leq\lfloor\frac{N}{n}\rfloor}g'(np)\times\varphi(p)$ $S(n,k)=s(n,k)+\sum_{k\leq p\leq\sqrt N\And p^e\leq\lfloor\frac{N}{n}\rfloor}S(np^e,p)+[e\neq 1]g'(np^e)\times\varphi(np^e)$ 867 868 When $p\leq\frac{n+(\varphi(n)-n\mod\varphi(n))}{\varphi(n)-n\mod\varphi(n)}$, there is $g'(np)=g'(n)+1$, otherwise $g'(np)=g'(n)$. 869 870 Pre-calculate the prefix of $\varphi(p)$ among prime numbers, we can calculate $s(n,k)$ like this: 871 872 $s(n,k)=\varphi(n)\times\left(g'(n)\sum_{k\leq p\leq\lfloor\frac{N}{n}\rfloor}\varphi(p)+\sum_{k\leq p\leq\min\left(\frac{n+(\varphi(n)-n\mod\varphi(n))}{\varphi(n)-n\mod\varphi(n)},\lfloor\frac{N}{n}\rfloor\right)}\varphi(p)\right)$ 873 874 The answer is $\frac{N(N+1)}{2}-1-S(1,1)$. 875 876 With time complexity $\mathcal O\left(\frac{n^{0.75}}{\log n}\right)$, it could pass the test cases of $N\le 10^{11}$. 877 878 **Code** 879 880 ``` 881 #include<cstdio> 882 #include<cmath> 883 typedef unsigned long long ull; 884 typedef unsigned uint; 885 const uint M=1e6+5; 886 ull N;const uint ANS[11]={0,0,0,1,1,2,2,3,3,6,8}; 887 uint B,n4,top,pri[M],F0[M],F1[M],G0[M],G1[M],SF[M],SG[M]; 888 inline ull Div(const ull&n,const ull&m){ 889 return double(n)/m; 890 } 891 inline ull min(const ull&a,const ull&b){ 892 return a>b?b:a; 893 } 894 inline uint DFS(const ull&n,uint k,const ull&phi){ 895 const ull&T=Div(N,n); 896 const uint&g=int(n*1./phi),&R=min(Div((g+1)*phi,(g+1)*phi-n),min(ull(B),T)); 897 uint ans=0; 898 if(k>top)ans=T<=B?0:g*phi*(SF[n]-SG[B]); 899 else if(pri[k]>T)ans=0; 900 else if(pri[k]<=R)ans=g*phi*((n<=B?SF[n]:SG[T])-SG[R])+(g+1)*phi*(SG[R]-SG[pri[k-1]]); 901 else ans=g*phi*((n<=B?SF[n]:SG[T])-SG[pri[k-1]]); 902 for(;k<=top;++k){ 903 const uint&p=pri[k],&w=p<=R?g+1:g;if(1ull*p*p>T)break; 904 for(ull x=n,tp=phi*(p-1);x*p<=N;tp*=p)ans+=DFS(x*=p,k+1,tp)+w*tp; 905 ans-=w*phi*(p-1); 906 } 907 return ans; 908 } 909 signed main(){ 910 scanf("%llu",&N); 911 if(N<=10)return!printf("%d",ANS[N]);B=sqrt(N);n4=sqrt(B); 912 for(uint i=1;i<=B;++i){ 913 const ull&w=Div(N,i); 914 F0[i]=w-1;F1[i]=w*(w+1)/2-1; 915 G0[i]=i-1;G1[i]=i*(i+1ull)/2-1; 916 } 917 for(uint p=2;p<=n4;++p)if(G0[p]!=G0[p-1]){ 918 const uint&lim=Div(B,p),&S0=G0[p-1],&S1=G1[p-1];pri[++top]=p; 919 for(uint k=1;k<=lim;++k){ 920 F0[k]-=F0[k*p]-S0;F1[k]-=p*(F1[k*p]-S1); 921 } 922 for(uint k=lim+1;k<=B;++k){ 923 const uint&x=Div(N,k*p);F0[k]-=G0[x]-S0;F1[k]-=p*(G1[x]-S1); 924 } 925 for(uint k=B,e=lim;e>=p;--e)for(uint x=e*p,V0=G0[e]-S0,V1=p*(G1[e]-S1);k>=x;--k){ 926 G0[k]-=V0;G1[k]-=V1; 927 } 928 } 929 for(uint p=n4+1;p<=B;++p)if(G0[p]!=G0[p-1]){ 930 const uint&lim=Div(B,p),&T=Div(N,1ll*p*p),&S0=G0[p-1],&S1=G1[p-1];pri[++top]=p; 931 for(uint k=1;k<=lim;++k){ 932 F0[k]-=F0[k*p]-S0;F1[k]-=p*(F1[k*p]-S1); 933 } 934 for(uint k=lim+1;k<=T;++k){ 935 const uint&x=Div(N,k*p);F0[k]-=G0[x]-S0;F1[k]-=p*(G1[x]-S1); 936 } 937 } 938 for(uint i=1;i<=B;++i)SF[i]=F1[i]-F0[i],SG[i]=G1[i]-G0[i]; 939 printf("%u",N*(N+1)/2-1-DFS(1,1,1)); 940 } 941 ``` 942 943 [2081G2 - Hard Formula (Hard Version)](/contest/2081/problem/G2 "Codeforces Round 1010 (Div. 1, Unrated)") 944 Idea: [Prean](/profile/Prean "Expert Prean") 945 946 **Hint 1** 947 948 Consider the DFS structure of $\min 25$ sieve. 949 950 What kind of nodes are important? 951 952 How many of nodes are important? 953 954 **Hint 2** 955 956 Consider using Du Sieve to get some important functions. 957 958 **Solution** 959 960 For further optimization, let's consider the DFS tree of $\min25$ sieve: $N$ vertices, rooted on $1$, the father of a node $d$ is $\frac{d}{\text{maxp}(d)}$ where $\text{maxp}(d)$ denotes the maximum prime factor of $d$. 961 962 Consider all the positions $d$ that $g'(d)\neq g'(fa_d)$. Let's divide them into two cases: 963 964 1. $d$ is a leaf, which means $d\le N\lt d\times \operatorname{maxp}(d)$. 965 2. $d$ is not a leaf, which means $d\times \operatorname{maxp}(d)\le N$. 966 967 The answer could be calculated like this: 968 969 $\sum_{g'(d)\neq g'(fa_d)\text{ or }d=1}G(\frac{d}{\mathrm{maxp}(d)},\mathrm{maxp}(d))$ 970 971 where $G(d,p)$ denotes the sum of $\varphi$ in the subtree of node $d$, and $G(d,p)$ could be calculated like this: 972 973 $G(d,p)=\varphi(d)\sum_{i=1}^{\lfloor\frac{N}{d}\rfloor}[\mathrm{minp}(i)=p]\varphi(i)$ 974 975 We could use DFS to search all the nodes $d$ which satisfy case 2, and we can calculate its contribution to the answer during our DFS. 976 977 For a non-leaf node $u$, let's consider its child nodes $up$ which satisfy case 1. 978 979 It's easy to see that $p$ is in an interval, which allows $O(1)$ calculation of the contributions of these nodes. 980 981 As a result, we get the number of nodes $d$. 982 983 **DFS Code** 984 985 ``` 986 //pi[n] means the number of prime number <=n 987 //Sp[k] The prefix sum of phi(p) among the first k prime numbers 988 //g[k]=(pri[k]-1.0)/pri[k] 989 inline ull div(ull n,ull m){ 990 return n*1./m; 991 } 992 inline bool check(double P,ull n,uint k){ 993 ull x(1);while(P>1&&k<=m&&x*pri[k]<=n)P*=g[k],x*=pri[k++];return P>1; 994 } 995 bool DFS1(ull n,uint k,ull phi){ 996 const ull T=div(N,n);const uint w=int(1.*n/phi)+1; 997 if(check(w*phi*1./n,T,k))return true; 998 //if the g' would not change in the subtree, return directly 999 const uint R=pi[min(div(w*phi,w*phi-n),min(ull(B),T))]; 1000 //g(n)*p/(p-1)>=int(g(n))+1 1001 for(;k<=m;++k){ 1002 const uint&p=pri[k];if(p*p>T)break; 1003 if(k<=R)d[k].push_back(nb(n,phi)),n*p<=K&&(lim=max(lim,k)); 1004 for(ull x=n,tp=phi*(p-1);x*p<=N;tp*=p)if(DFS1(x*=p,k+1,tp))break; 1005 //The subtree of np^e is isomorphic to the subtree of np^(e+1) , so if we didn't find in the previous one, we do not need to dfs into the latter one 1006 //This will not effect the efficiency significantly since dfs is not the efficiency bottleneck 1007 } 1008 if(k<=R)sum+=phi*(Sp[R]-Sp[k-1]); 1009 //The contribution of its child nodes which is leaf 1010 return false; 1011 } 1012 ``` 1013 1014 | $N$ | The number of non-leaf nodes satisfy $g'(d)\neq g'(fa_d)$ | Time to DFS (tested in i9-14900HX) | 1015 | --- | --- | --- | 1016 | $10^{10}$ | 78370 | 0.007s | 1017 | $10^{11}$ | 285027 | 0.021s | 1018 | $10^{12}$ | 1074403 | 0.085s | 1019 | $10^{13}$ | 4010656 | 0.505s | 1020 1021 Let's consider how to calculate $G(d,p)$. Define: 1022 1023 $f_k(x)=\sum_{i=1}^n [\text{minp}(i)\ge k]\varphi(i)$ 1024 1025 where $\text{minp}(i)$ denote the minimum prime number of $i$. 1026 1027 Then we can see that: 1028 1029 $G(d,p)=f_p(\lfloor\frac{N}{d}\rfloor)-f_{p+1}(\lfloor\frac{N}{d}\rfloor)$ 1030 1031 It's easy to see that $F_0(x)=\frac{\zeta(x-1)}{\zeta(x)}$, we can use Du Sieve to get all the $f_0(\lfloor \frac Nd\rfloor)$ in $O(N^{\frac 23})$. 1032 1033 According to $\texttt{Key observation 1}$, $\forall d\notin{2,6},\mathrm{maxp}(d)\leq\sqrt d$. 1034 1035 Let $k=\max_{g'(d)\neq g'(fa_d)\And d\leq B}(\mathrm{maxp}(d))$, categorize these nodes $d$ again: 1036 1037 * (i) $\mathrm{maxp}(d)\leq k$, Then $\mathrm{maxp}(d)\leq \sqrt B$. 1038 * (ii) $\mathrm{maxp}(d) \gt k$, then $B\leq\mathrm{maxp^2(d)}\leq d$, $\lfloor\frac{N}{d}\rfloor \lt \frac NB$. 1039 1040 For those $d$ satisfy condition (i), let's begin with $f_0$, delete the prime numbers from small to large, until $f_k$ and calculate the contributions of these $d$. 1041 1042 We could use Dirichlet convolution to calculate $f_{p+1}$ from $f_p$. 1043 1044 Step 1: 1045 1046 $h_p(N)=f_p(N)-p\times f_p(\lfloor\frac{N}{p}\rfloor)$ 1047 1048 Step 2: 1049 1050 $f_{p+1}(N)=\sum_{i=0}h_p(\lfloor\frac{N}{p^i}\rfloor)=h_p(N)+f_{p+1}(\lfloor\frac{N}{p}\rfloor)$ 1051 1052 These could solve in $O\left(\frac{\sqrt N \times \sqrt B}{\log n}\right)$. 1053 1054 For those $d$ satisfy condition (ii), we calculate $G(d,p)$ in this method: 1055 1056 $G(d,p)=\sum_{k=1}\varphi(dp^k)f_{p+1}(\lfloor\frac{N}{dp^k}\rfloor)$ 1057 1058 Because $p\geq \sqrt B$ and $d\geq B$, we only need to consider $k\le \frac{\log N}{\log B}$, which is similar to $O(1)$. 1059 1060 In this part, we only need $f(x)$ for $x\le B$, so to calculate these $f$ is actually a two-dimensional partial order problem which can be solved using a BIT, time complexity $O(\frac NB\log N)$. 1061 1062 Since for each $d$, we get $G(d,p)$ in $O(1)$ in case (i), and $O(\log N)$ in case (ii). 1063 1064 The total time complexity is $O\left(N^{\frac 23} + \frac{\sqrt N\times \sqrt B}{\log N}+ \frac NB\log N+D\log N\right)$. 1065 1066 Let $B=N^{\frac 13}\log^{\frac 43}N$, the total time complexity is $O\left(N^{\frac 23}+ \frac{N^{\frac 23}}{\log^{\frac 13}N}+D\log N\right)$. 1067 1068 ### Further optimization to $n=10^{13}$ 1069 1070 This part is included in the offline contest. 1071 1072 $\texttt{Key observation 2}$ : The number of $i$ in range $[1,n]$ that satisfy $\mathrm{minp}\geq n^{\frac{1}{4}}$ is of the order of $\frac{n}{\ln n}$. 1073 1074 **Proof** 1075 1076 $O\left(\sum_{x=\pi(n^{\frac{1}{4}})}^{\pi(n)}\sum_{y=\pi(n^{\frac{1}{4}})}^{\pi(\frac{n}{p_x})}\max\left(\pi(\frac{n}{p_xp_y})-\pi(n^{\frac{1}{4}}),0\right)\right)=O\left(\sum_{x=\pi(n^{\frac{1}{4}})}^{\pi(n)}\pi(\frac{n}{p_x})\sum_{y=\pi(n^{\frac{1}{4}})}^{\pi(\frac{n}{p_x})}\frac{1}{p_y}\right)$ $O\left(\sum_{n^{\frac{1}{3}}\leq p\leq n}\frac{1}{p}\right)=O(\log\log n-\log\log n^{\frac{1}{3}})=O(\log 3)$ $O\left(\sum_{x=\pi(n^{\frac{1}{4}})}^{\pi(n)}\pi(\frac{n}{p_x})\sum_{y=\pi(n^{\frac{1}{4}})}^{\pi(\frac{n}{p_x})}\frac{1}{p_y}\right)=O\left(\sum_{x=\pi(n^{\frac{1}{4}})}^{\pi(n)}\pi(\frac{n}{p_x})\right)=O(\pi(n))=O(\frac{n}{\log n})$ 1077 1078 Since we only need to calculate $G(\frac{d}{\mathrm{maxp}(d)},\mathrm{maxp}(d))$ where $\text{maxp}(d)\gt \sqrt B$ in case (ii). 1079 1080 We actually only need to consider those $\text{minp}(i)\gt \sqrt B$, and $i\le \frac{d}{\text{maxp}(d)}\le\frac N{\sqrt B}$. 1081 1082 Then if $B\gt N^{\frac 13}$, the actual size to append into the BIT is only $O(\frac{N}{B\log N})$, so the time complexity of case ii is $O(\frac NB)$. 1083 1084 Then we could adjust $B$ to $N^{\frac 13}\log^{\frac 23}N$, the time complexity could reduce to $O\left(\frac {N^{\frac 23}}{\log^{\frac 23}N}+D\log N+N^{\frac 23}\right)$. 1085 1086 To further optimize, let's introduce a method that could significantly reduce the time consumption of Du Sieve. 1087 1088 The formula of Du Sieve is $\sum_{xy\leq N}f(x)g(y)=S_{f*g}(N)$. We can see that $\min(x,y)\leq\sqrt{N}$, Let $B=\lfloor\sqrt{N}\rfloor$, the formula could be rewritten like this: 1089 1090 $\sum_{i=1}^Bf(i)S_g(\lfloor\frac{N}{i}\rfloor)+g(i)S_f(\lfloor\frac{N}{i}\rfloor)-S_f(B)S_g(B)=S_{f*g}(N)$ $S_f(N)=S_{f*g}(N)+S_f(B)S_g(B)-\sum_{i=2}^Bf(i)S_g(\lfloor\frac{N}{i}\rfloor)+g(i)S_f(\lfloor\frac{N}{i}\rfloor)-S_g(N)$ 1091 1092 Traditionally, we need $[6B,8B]$ times of division, but using this method need a maximum of $2B$ times of division. 1093 1094 As for what we need to calculate in this problem, we can get the formula: 1095 1096 $S_{\varphi}(N)=\frac{N(N-1)}{2}+S_{\varphi(B)}\times B-\sum_{i=2}^B\varphi(i)\lfloor\frac{N}{i}\rfloor+iS_{\varphi}(\lfloor\frac{N}{i}\rfloor)$ 1097 1098 Without using things like $\text{std::map}$, and use dynamic programming instead of DFS, we can further reduce the time consumption. 1099 1100 Then consider how to optimize Du Sieve to $O\left(\frac{N^{\frac{2}{3}}}{\log N}\right)$. 1101 1102 Definition: if $f$ is a multiplicative function, then we define a multiplicative function $f_x(p^k)=[p\geq x]f(p^k)$. 1103 1104 We can calculate $\varphi_{N^{\frac{1}{6}}}(\lfloor\frac {N}{i} \rfloor)$ for each $i$ and then recurrence $\varphi$ from $\varphi_{N^{\frac 16}}$. Let $n6=N^{\frac{1}{6}}$, we can change the formula into: 1105 1106 $S_{\varphi_{n6}}(N)=S_{id_{n6}}(N)-S_{1_{n6}}(N)+S_{\varphi_{n6}}(B)S_{1_{n6}}(B)-\sum_{i=2}^B[\mathrm{minp}(i)\geq n6]\varphi(i)S_{1_{n6}}(\lfloor\frac{N}{i}\rfloor)+S_{\varphi_{n6}}(\lfloor\frac{N}{i})$ 1107 1108 Where $\text{id}(x)=x$ and $1(x)=1$, which can be calculated through $\text{min25}$ Seive, but we only need to solve $p\leq n6$ instead of $p\leq\sqrt N$. 1109 1110 According to $\texttt{Key observation 2}$, we know that the number of $i\le \sqrt N$ that satisfy $\mathrm{minp}(i)\geq n6$ is about $\frac{\sqrt N}{\log N}$, find them and iterate these numbers in the Du Sieve. The time complexity of this part is $O\left(\frac{N^{\frac{2}{3}}}{\log N}\right)$. 1111 1112 At last we get a solution of $O\left(\frac{N^{\frac{2}{3}}}{\log N}+\frac{\sqrt{NK}}{\log N}+\frac{N}{K}\right)$. 1113 1114 **Code** 1115 1116 ``` 1117 #include<bitset> 1118 #include<cstdio> 1119 #include<vector> 1120 #include<cmath> 1121 #include<ctime> 1122 using std::min; 1123 using std::max; 1124 typedef unsigned uint; 1125 typedef unsigned long long ull; 1126 namespace Sol{ 1127 const uint M=4162277+5,Pi=1001258+5,M2=500000000+5; 1128 uint sum;ull N; 1129 uint F[M],G[M]; 1130 uint top,Sp[Pi],pri[Pi],pi[M],phi[M2];double g[Pi]; 1131 uint n4,K,B,m,lim,BIT[M]; 1132 double st,ed; 1133 struct nb{ 1134 ull n;uint phi; 1135 nb(const ull&n=1,const uint&phi=1):n(n),phi(phi){} 1136 };std::vector<nb>d[Pi]; 1137 inline ull div(const ull&n,const ull&m){ 1138 return n*1./m; 1139 } 1140 inline void Add(uint n,const uint&V){ 1141 while(n<=B)BIT[n]+=V,n+=n&-n; 1142 } 1143 inline uint Qry(uint n){ 1144 uint ans(0);while(n)ans+=BIT[n],n-=n&-n;return ans; 1145 } 1146 inline bool check(double P,ull n,uint k){ 1147 ull x(1);while(P>1&&k<=m&&x*pri[k]<=n)P*=g[k],x*=pri[k++];return P>1; 1148 } 1149 inline bool DFS1(const ull&n,uint k,const ull&phi){ 1150 const ull&T=div(N,n);const uint&w=int(n/phi)+1; 1151 if(check(w*phi*1./n,T,k))return true; 1152 //g(n)*p/(p-1)>=int(g(n))+1 1153 const uint&R=pi[min(div(w*phi,w*phi-n),min(ull(B),T))]; 1154 for(;k<=m;++k){ 1155 const uint&p=pri[k];if(p*p>T)break; 1156 if(k<=R)d[k].push_back(nb(n,phi)),n*p<=B&&(lim=max(lim,k)); 1157 for(ull x=n,tp=phi*(p-1);x*p<=N;tp*=p)if(DFS1(x*=p,k+1,tp))break; 1158 } 1159 if(k<=R)sum+=phi*(Sp[R]-Sp[k-1]); 1160 return false; 1161 } 1162 inline void DFS2(const uint&n,uint k,const uint&phi){ 1163 const uint&T=div(B,n);Add(n,phi); 1164 for(;k<=m;++k){ 1165 const uint&p=pri[k],&T2=div(B,p);if(p>T)return; 1166 for(uint x=n,tp=phi*(p-1);x<=T2;tp*=p)DFS2(x*=p,k+1,tp); 1167 } 1168 } 1169 void sieve(const uint&n){ 1170 phi[1]=1; 1171 for(uint i=2;i<=n;++i){ 1172 if(!phi[i]){ 1173 phi[i]=i-1;if(i<=B)pri[++top]=i,g[top]=1.*(i-1)/i,Sp[top]=Sp[top-1]+phi[i],pi[i]=1; 1174 } 1175 for(uint x,j=1;j<=top&&(x=i*pri[j])<=n;++j){ 1176 phi[x]=phi[i]*(pri[j]-1);if(div(i,pri[j])*pri[j]==i){phi[x]+=phi[i];break;} 1177 } 1178 if(i<=B)pi[i]+=pi[i-1]; 1179 } 1180 } 1181 void Getphi(const ull&n){ 1182 const uint&B2=div(N,K); 1183 for(uint i=1;i<=B;++i)G[i]=G[i-1]+phi[i];for(uint i=div(N,B);i>=1;--i)F[B]+=phi[i]; 1184 for(uint i=B-1;i>B2;--i){ 1185 const uint&L=div(N,i+1)+1,&R=div(N,i);F[i]=F[i+1];for(uint k=L;k<=R;++k)F[i]+=phi[k]; 1186 } 1187 for(uint i=B2;i>=1;--i){ 1188 const ull&T=div(N,i);const uint&lim=sqrt(T);F[i]=lim*G[lim]+T*(T-1)/2; 1189 for(uint k=2;k<=lim;++k){ 1190 const uint&x=div(T,k);F[i]-=(i*k<=B?F[i*k]:G[x])+phi[k]*x; 1191 } 1192 } 1193 } 1194 uint Solve(const ull&n){ 1195 st=clock(); 1196 N=n;B=sqrt(N);n4=sqrt(B); 1197 sieve(K=uint(pow(N,2./3)));m=pi[B]; 1198 fprintf(stderr,"sieve(%d) done %lf\n",K,((ed=clock())-st)/1000);st=ed; 1199 DFS1(1,1,1); 1200 fprintf(stderr,"DFS done %lf\n",((ed=clock())-st)/1000);st=ed; 1201 Getphi(N);sum+=F[1]; 1202 fprintf(stderr,"Getphi done %lf\n",((ed=clock())-st)/1000);st=ed; 1203 for(uint i=1;i<=lim;++i){ 1204 const uint&p=pri[i],&T=B/p;const ull&k=div(N,p); 1205 for(nb&x:d[i])sum+=x.phi*(x.n<=B?F[x.n]:G[div(N,x.n)]); 1206 for(uint i=1;i<=T;++i)F[i]-=p*F[i*p]; 1207 for(uint i=T+1;i<=B;++i)F[i]-=p*G[div(k,i)]; 1208 for(uint i=B,j=div(i,p);j;--j)for(uint e=j*p,V=p*G[j];i>=e;--i)G[i]-=V; 1209 for(uint i=p,j=1;i<=B;++j)for(uint e=min(i+p,B+1),V=G[j];i<e;++i)G[i]+=V; 1210 for(uint i=B;i>T;--i)F[i]+=G[div(k,i)]; 1211 for(uint i=T;i>=1;--i)F[i]+=F[i*p]; 1212 for(nb&x:d[i])sum-=x.phi*(x.n<=B?F[x.n]:G[div(N,x.n)]); 1213 } 1214 fprintf(stderr,"case1 done %lf\n",((ed=clock())-st)/1000);st=ed; 1215 Add(1,1); 1216 for(uint i=m;i>lim;--i){ 1217 const uint&p=pri[i]; 1218 for(nb&x:d[i]){ 1219 ull n=N/x.n/p,phi=x.phi*(p-1); 1220 while(n)sum+=phi*Qry(n),n/=p,phi*=p; 1221 } 1222 for(ull x=p,phi=p-1;x<=B;x*=p,phi*=p)DFS2(x,i+1,phi); 1223 } 1224 fprintf(stderr,"case2 done %lf\n",((ed=clock())-st)/1000);st=ed; 1225 return n*(n+1)/2-sum; 1226 } 1227 } 1228 namespace sol{ 1229 uint top,pri[10005],pos[10005],phi[10005]; 1230 inline uint solve(const uint&N){ 1231 uint sum(0);phi[1]=1; 1232 for(uint i=2;i<=N;++i){ 1233 if(!pos[i])pri[pos[i]=++top]=i,phi[i]=i-1; 1234 for(uint x,j=1;j<=pos[i]&&(x=i*pri[j])<=N;++j)phi[x]=(pos[x]=j)==pos[i]?phi[i]*pri[j]:phi[i]*(pri[j]-1); 1235 sum+=i%phi[i]; 1236 } 1237 return sum; 1238 } 1239 } 1240 signed main(){ 1241 ull n;scanf("%llu",&n);if(n<=10000)return printf("%u\n",sol::solve(n)),0;printf("%u\n",Sol::Solve(n)); 1242 } 1243 ```