2089.md (34230B)
1 Source: https://codeforces.com/blog/entry/141053 2 3 We apologize for the late editorial. 4 5 [2090A - Treasure Hunt](/contest/2090/problem/A "Codeforces Round 1012 (Div. 2)") 6 Idea: [_Lucien](/profile/_Lucien "Master _Lucien") 7 8 **Solution** 9 10 Let's calculate how many operations we need. The number of pairs of operations is $\left\lfloor\frac{a}{x + y}\right\rfloor$. Additionally, we add $+1$ if $(a \bmod (x + y)) \ge x$, because in this case, the first player will be able to make one more move. Note that the first part is always even, which means the answer depends only on whether $(a \bmod (x + y)) \ge x$, and in this case, the answer is YES. 11 12 **Code** 13 14 ``` 15 #include <bits/stdc++.h> 16 17 using namespace std; 18 19 void solve() { 20 int x, y, a; 21 cin >> x >> y >> a; 22 if (a % (x + y) < x) { 23 cout << "NO\n"; 24 } else { 25 cout << "YES\n"; 26 } 27 } 28 29 int main() { 30 ios_base::sync_with_stdio(0); 31 cin.tie(0); 32 33 int t; 34 cin >> t; 35 while (t--) 36 solve(); 37 } 38 ``` 39 40 [2090B - Pushing Balls](/contest/2090/problem/B "Codeforces Round 1012 (Div. 2)") 41 Idea: [Ecrade_](/profile/Ecrade_ "Grandmaster Ecrade_") 42 43 **Solution** 44 45 We can transform the problem into: select a row / column and replace the leftmost / topmost $0$ with $1$. Then the solution is clear: if, for each $1$ in the grid, there does not exist any $0$ on its top, or does not exist any $0$ on its left, then the answer is YES; otherwise NO. 46 47 But how to prove that if the condition is satisfied, we can always construct a valid series of ball-pushing operations? We can consider the problem in reverse order: given the final state, if, for an $1$ in the grid, there does not exist any $0$ on its top, or does not exist any $0$ on its left, then we can turn it into $0$, and our goal is to turn all $1$ s into $0$ s. We can always reach the goal if we choose $1$ s in descending order of $i+j$, where $(i,j)$ is their coordinates in the grid. 48 49 **Code** 50 51 ``` 52 #include<bits/stdc++.h> 53 using namespace std; 54 typedef long long ll; 55 ll t,n,m,a[59][59],vis[59][59]; 56 char s[59]; 57 inline ll read(){ 58 ll s = 0,w = 1; 59 char ch = getchar(); 60 while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();} 61 while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar(); 62 return s * w; 63 } 64 int main(){ 65 t = read(); 66 while (t --){ 67 n = read(),m = read(); 68 for (ll i = 1;i <= n;i += 1){ 69 scanf("%s",s + 1); 70 for (ll j = 1;j <= m;j += 1){ 71 a[i][j] = s[j] - '0'; 72 vis[i][j] = 0; 73 } 74 } 75 for (ll i = 1;i <= n;i += 1){ 76 for (ll j = 1;j <= m;j += 1){ 77 if (!a[i][j]) break; 78 vis[i][j] = 1; 79 } 80 } 81 for (ll j = 1;j <= m;j += 1){ 82 for (ll i = 1;i <= n;i += 1){ 83 if (!a[i][j]) break; 84 vis[i][j] = 1; 85 } 86 } 87 bool fl = 1; 88 for (ll i = 1;i <= n && fl;i += 1){ 89 for (ll j = 1;j <= m;j += 1){ 90 if (a[i][j] && !vis[i][j]){ 91 fl = 0; 92 break; 93 } 94 } 95 } 96 puts(fl ? "YES" : "NO"); 97 } 98 return 0; 99 } 100 ``` 101 102 [2090C - Dining Hall](/contest/2090/problem/C "Codeforces Round 1012 (Div. 2)") 103 Idea: [myee](/profile/myee "International Master myee") 104 105 **Solution** 106 107 > Original idea from [myee](/profile/myee "International Master myee") has $4$ cases, which is a medium difficulty problem using deletable heap. You may find the original statement in zh-cn on GitHub later. 108 > 109 > The Codeforces version by [FairyWinx](/profile/FairyWinx "Grandmaster FairyWinx") has only $2$ cases, in order to meet the difficulty as Div2C. 110 > 111 > The En/Ru statement changes for times after checking. Sorry for the inconvenience. 112 113 Firstly we can get the distance of each cell by BFS or Math Way: $d(x,y)=x+y+2[x\bmod3=y\bmod3=2]$. 114 115  116 117 The proof is trivial. 118 119 Then we can sort out the first $4n$ table cell with the lowest distance in $O(n)$ time: by BFS or enumerating possible $d(x,y)=k$. 120 121 Suppose we record whether a table cell is occupied or not by a bool array. Then we can check whether a cell can be allowed to go by someone $o=0/1$ in $O(1)$ time. 122 123 Suppose the shortest table cell we can choose is $x_0$ -th and $x_1$ -th ones, then $x_1\le x_0\le4n$. We can keep trying the smallest $x_o$ until it's okay. 124 125 The time complexity is $O(n)$. 126 127 **Code** 128 129 ``` 130 #include <bits/stdc++.h> 131 132 using uint = unsigned; 133 using bol = bool; 134 135 const uint T=2000; 136 const uint R=200000; 137 138 uint Ord[R+5]; 139 uint Nxt(uint p,uint o) 140 { 141 uint x=p/T,y=p%T; 142 if(o&1)y=y/3*3+3-y%3; 143 if(o&2)x=x/3*3+3-x%3; 144 return x*T+y; 145 } 146 147 bol G[2][T*T];uint Ans[2]; 148 149 int main() 150 { 151 #ifdef MYEE 152 freopen("QAQ.in","r",stdin); 153 freopen("QAQ.out","w",stdout); 154 #endif 155 for(uint i=2,tp=0;i<T&&tp<R;i++)if(i%3==2) 156 { 157 for(uint x=1;x<i&&tp<R;x+=3)Ord[tp++]=x*T+i-x; 158 } 159 else if(!(i%3)) 160 { 161 for(uint x=1;x<=i-2&&tp<R;x++) 162 if(x%3==1)Ord[tp++]=x*T+i-x; 163 else if(x%3==2)Ord[tp++]=x*T+i-x-2,Ord[tp++]=x*T+i-x; 164 Ord[tp++]=(i-1)*T+1; 165 } 166 uint t;scanf("%u",&t); 167 while(t--) 168 { 169 uint q;scanf("%u",&q); 170 for(uint i=0;i<q*4;i++)G[0][Ord[i]]=G[1][Ord[i]]=0; 171 Ans[0]=Ans[1]=0; 172 while(q--) 173 { 174 uint t;scanf("%u",&t);while(G[t][Ord[Ans[t]]])Ans[t]++; 175 t=Ord[Ans[t]];printf("%u %u\n",t/T,t%T); 176 G[1][t]=1;for(uint o=0;o<4;o++)G[0][Nxt(t,o)]=1; 177 } 178 } 179 return 0; 180 } 181 ``` 182 183 [2089A - Simple Permutation](/contest/2089/problem/A "Codeforces Round 1012 (Div. 1)") 184 Idea: [QuietBeautifulThoughts](/profile/QuietBeautifulThoughts "Legendary Grandmaster QuietBeautifulThoughts") 185 186 **Solution** 187 188 **Lemma (Bertrand's postulate):** For each positive integer $x$, there is a prime $p$ inside the interval $[x,2x]$. 189 190 Find a prime number $p$ between $\lfloor \frac{n}{3} \rfloor$ and $\lceil \frac{2n}{3} \rceil$, and construct the permutation in an alternating way: $p, p-1, p+1, p-2, p+2, \dots$. Place the remaining numbers arbitrarily. 191 192 In this construction, we have $c_1 = c_3 = c_5 = \dots = c_{2 \lfloor \frac{n}{3} \rfloor - 1} = p$, which meets the requirement with at least $\lfloor \frac{n}{3} \rfloor$ numbers being prime. 193 194 **Code** 195 196 ``` 197 #include<bits/stdc++.h> 198 using namespace std; 199 200 bool isPrime(int x){ 201 if(x <= 1) 202 return 0; 203 for(int i = 2 ; i * i <= x ; ++i) 204 if(x % i == 0) 205 return 0; 206 return 1; 207 } 208 209 vector<int> generateSol(int n, int p){ 210 vector<int> ans; 211 ans.push_back(p); 212 for(int i = 1 ; i <= n ; ++i){ 213 if(p - i > 0) 214 ans.push_back(p - i); 215 if(p + i <= n) 216 ans.push_back(p + i); 217 } 218 return ans; 219 } 220 221 int main(){ 222 int t; 223 cin >> t; 224 for(int i = 1 ; i <= t ; ++i){ 225 int n; 226 cin >> n; 227 vector < int > ans; 228 for(int x = 0 ; ; ++x){ 229 if(isPrime(n / 2 - x)){ 230 ans = generateSol(n , n / 2 - x); 231 break; 232 } 233 if(isPrime(n / 2 + x)){ 234 ans = generateSol(n , n / 2 + x); 235 break; 236 } 237 } 238 for(int i = 0 ; i < n ; ++i) 239 cout << ans[i] << " \n"[i == n - 1]; 240 } 241 return 0; 242 } 243 ``` 244 245 [2089B1 - Canteen (Easy Version)](/contest/2089/problem/B1 "Codeforces Round 1012 (Div. 1)") 246 Idea: [Ecrade_](/profile/Ecrade_ "Grandmaster Ecrade_") 247 248 **Solution** 249 250 For each $ a_i $, calculate the minimum number of cyclic right shifts required to reduce it to zero, denoted as $ d_i $. The answer is the maximum $ d_i $ across all $ i $. 251 252 For cyclic problems, we can consider breaking the cycle into a chain (i.e., let $ a_{i+n} = a_i $, $ b_{i+n} = b_i $). 253 254 Consider constructing a parenthesis sequence $ s $ by concatenating $ a_0 $ left parentheses, $ b_0 $ right parentheses, $ a_1 $ left parentheses, $ b_1 $ right parentheses, ... ,$ a_{2n-1} $ left parentheses and $ b_{2n-1} $ right parentheses. The operation in the original problem corresponds to the process of matching parentheses in $ s $: 255 256 * "Set the smaller of $(a_i, b_i)$ to zero and the larger to their difference" $\Rightarrow$ "Match the parentheses corresponding to $(a_i, b_i)$". 257 * "Cyclically right-shift $ a $" $\Rightarrow$ "Unmatched left parentheses continue to find matching right parentheses". 258 259 The first time $ a_i $ is reduced to zero depends on which $ b_j $ ’s right parenthesis matches the leftmost parenthesis corresponding to $ a_i $. 260 261 We can use prefix sums to find matchings of the parenthesis: Let $ c_i = \sum\limits_{j=0}^i (a_j - b_j) $. Define $ p_i $ as the smallest index satisfying $ p_i \gt i $ and $ c_{p_i} \leq c_i $, then $ d_i = p_i - i $. We can compute all $ p_i $ with a monotonic stack. 262 263 It should be pointed out that matching parentheses is just an intuitive way of understanding the solution. You can, of course, also draw the above conclusion by direct observation. 264 265 The time complexity is $ O(\sum n) $. 266 267 **Code** 268 269 ``` 270 #include<bits/stdc++.h> 271 using namespace std; 272 typedef long long ll; 273 ll t,n,k,a[400009],stk[400009]; 274 inline ll read(){ 275 ll s = 0,w = 1; 276 char ch = getchar(); 277 while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();} 278 while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar(); 279 return s * w; 280 } 281 int main(){ 282 t = read(); 283 while (t --){ 284 n = read(),k = read(); 285 for (ll i = 1;i <= n;i += 1) a[i] = read(); 286 for (ll i = 1;i <= n;i += 1) a[i] = a[i + n] = a[i] - read(); 287 for (ll i = 1;i <= 2 * n;i += 1) a[i] += a[i - 1]; 288 ll tp = 0,ans = 0; 289 for (ll i = 2 * n;i >= 1;i -= 1){ 290 while (tp && a[stk[tp]] > a[i]) tp -= 1; 291 if (i <= n) ans = max(ans,stk[tp] - i); 292 stk[++ tp] = i; 293 } 294 printf("%lld\n",ans); 295 } 296 return 0; 297 } 298 ``` 299 300 [2089B2 - Canteen (Hard Version)](/contest/2089/problem/B2 "Codeforces Round 1012 (Div. 1)") 301 Idea: [Ecrade_](/profile/Ecrade_ "Grandmaster Ecrade_") 302 303 **Solution** 304 305 We can use binary search on the answer $ x $, and calculate the minimum number of changes needed to make $a$ zero within $ x $ rounds. 306 307 However, direct computation on the cyclic chain of $ 2n $ elements is troublesome (due to overlapping contributions). Instead, we can cyclically shift $ a $ and $ b $ such that $ c_{n-1} = \min\limits_{i=0}^{n-1} c_i$, which ensures that no $ a_{n-1} \gt 0 $ will be cyclically shifted to $a_0$, enabling us to only consider the first $n$ elements of the chain. 308 309 For the adjusted $ a $ and $ b $, we can greedily process $ i $ from $ n - x - 1 $ to $ -1 $: If $ \min\limits_{j=i+1}^{i+x}c_j \gt c_i $, then we should apply $ \min\limits_{j=i+1}^{i+x}c_j - c_i $ changes to $ a_{i+1} $ (assume that $c_{-1}=0$). We can also use a monotonic stack to maintain the whole process. 310 311 Note that if $\sum\limits_{i=0}^{n-1} a_i=k$, we should output $0$. 312 313 The time complexity is $ O(\sum n\log k) $. 314 315 **Bonus:** Find an $O(\sum n)$ solution. 316 317 **Code** 318 319 ``` 320 #include<bits/stdc++.h> 321 using namespace std; 322 typedef long long ll; 323 ll t,n,k,pos,a[400009],stk[400009]; 324 inline ll read(){ 325 ll s = 0,w = 1; 326 char ch = getchar(); 327 while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();} 328 while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar(); 329 return s * w; 330 } 331 bool judge(ll x){ 332 ll l = 1,r = 0,res = 0; 333 for (ll i = pos;i >= pos - n;i -= 1){ 334 if (l <= r && stk[l] - i > x) l += 1; 335 if (pos - i >= x) res += max(0ll,a[stk[l]] - a[i]); 336 if (res > k) return 0; 337 while (l <= r && a[stk[r]] > a[i]) r -= 1; 338 stk[++ r] = i; 339 } 340 return 1; 341 } 342 int main(){ 343 t = read(); 344 while (t --){ 345 n = read(),k = read(); 346 ll suma = 0; 347 for (ll i = 1;i <= n;i += 1) a[i] = read(),suma += a[i]; 348 for (ll i = 1;i <= n;i += 1) a[i] -= read(),a[i + n] = a[i]; 349 if (suma == k){puts("0"); continue;} 350 for (ll i = 1;i <= 2 * n;i += 1) a[i] += a[i - 1]; 351 pos = n; 352 for (ll i = n + 1;i <= 2 * n;i += 1) if (a[i] < a[pos]) pos = i; 353 ll l = 1,r = n,ans = n; 354 while (l <= r){ 355 ll mid = (l + r) >> 1; 356 if (judge(mid)) ans = mid,r = mid - 1; 357 else l = mid + 1; 358 } 359 printf("%lld\n",ans); 360 } 361 return 0; 362 } 363 ``` 364 365 [2089C2 - Key of Like (Hard Version)](/contest/2089/problem/C2 "Codeforces Round 1012 (Div. 1)") 366 Idea: [SpiritualKhorosho](/profile/SpiritualKhorosho "Candidate Master SpiritualKhorosho") 367 368 **Solution** 369 370 ### Background 371 372 This problem is inspired by a minigame from a recently released party video game, but the story was modified to comply with *the title*. We tried to isolate the artistic part and the theoretical part, and I apologize if you still feel like working on reading comprehension exercises. 373 374 ### Solution 375 376 Noticing that each member's strategy is not maximizing the total outcome (which is the expected number of successful matches between keys and locks), but only maximizing the outcome in her current turn, and equally likely to adopt each of optimal (pure) strategies, it will be ideal if there is some simple form of the strategy that only depends on $L$ and $K$. 377 378 #### Analyzing the Strategy 379 380 At the very beginning, when there is no information about the relationship between keys and locks, the first member in her first turn must randomly choose a key and a lock. 381 382 What about the second member, if the first one is not lucky enough? Since she will not choose the same pair of keys and locks, there are three different types of (pure) strategies: 383 384 * Choose a different key to open the same lock; 385 * Choose the same key to open a different lock; 386 * Choose a different key and a different lock. 387 388 For the first type of strategy, since there are $(L+K-1)$ keys remaining (after the very first attempt), and among them is only one correct key, the probability of opening the same lock is $1/(L+K-1)$. 389 390 For the second type, it can be proven that the probability is also $1/(L+K-1)$. Another way to think of this is, add $K$ imaginary locks and match each of them with a counterfeit key. Then, it is apparent that a new lock matches the selected key with the given probability. 391 392 **The Straightforward Computation of the Probability** 393 394 The key selected by the first member can either be a real key or a counterfeit one. Denote the event of the key being authentic as $A$, and that of it failing to open the lock at the first turn as $B$. Then, according to the Bayes' theorem along with the law of total probability, 395 396 \begin{equation} \begin{split} P(A|B) &= \frac{P(B|A)P(A)}{P(B)} = \frac{P(B|A)P(A)}{P(B|A)P(A) + P\left(B\left|\bar{A}\right.\right)P\left(\bar{A}\right)} \\ &= \frac{((L-1)/L)\cdot (L/(L+K))}{((L-1)/L)\cdot (L/(L+K)) + 1\cdot(K/(L+K))}\\ &= \frac{L-1}{L+K-1},\\ P\left(\left.\bar{A}\right|B\right) &= 1 — P(A|B) = \frac{K}{L+K-1}. \end{split} \end{equation} 397 398 Thus, the probability that the same key selected by the first member can open another lock randomly chosen by the second member (denoted as $C$) is 399 400 \begin{equation} \begin{split} P(C|B) &= P(A|B)\cdot P(C|AB) + P\left(\left.\bar{A}\right|B\right)\cdot P\left(C\left|\bar{A}B\right.\right)\\ &=\frac{L-1}{L+K-1}\cdot\frac{1}{L-1} + \frac{K}{L+K-1}\cdot 0\\ &= \frac{1}{L+K-1}. \end{split} \end{equation} 401 402 For the third type of strategy, its probability can be computed from either the first type or the second type, as $(L+K-1)$ different outcomes are equally likely to happen: 403 404 \begin{equation} \frac{1-1/(L+K-1)}{L+K-1}=\frac{L+K-2}{(L+K-1)^2}<\frac{1}{L+K-1}. \end{equation} 405 406 In conclusion, the second member will either choose the same key or the same lock. Because there are $(L - 1)$ pairs of the same key and other locks, and $(L + K - 1)$ pairs of other keys and the same lock, the second member will use the same key with probability $(L - 1)/(2L + K - 2)$, or check the same lock with probability $(L + K - 1)/(2L + K - 2)$. 407 408 As for all the following attempts, a similar *Proof* shows that, everyone will imitate the strategy adopted by the second member. That is to say, if the second member decides to continue with the same key, everyone will keep using this same key, until a lock is opened or all the locks are checked; if the second member picks a different key for the same lock, everyone will challenge this same lock, until it is eventually settled (and obviously it will). 409 410 Furthermore, whenever a key is identified as counterfeit, or a lock is opened, the information 'collapses', which turns the original problem into a subproblem with either one less counterfeit key (corresponding to $K' = K - 1$), or both one less valid key and one less lock ($L' = L - 1$), respectively. 411 412 To sum up, the process of the game is: 413 414 * Whenever a lock is opened, the original problem is reduced to a subproblem with $L' = L - 1$; 415 * Whenever a key is proven counterfeit, the original problem is reduced to a subproblem where $K' = K - 1$; -The first member randomly chooses a key and a lock to check if they match; 416 * If the first member fails, the second member adopts the same key with probability $(L - 1)/(2L + K - 2)$, or investigates the same lock with probability $(L + K - 1)/(2L + K - 2)$; 417 * If the second member fails as well, all the following attempts will replicate the choice of whether to employ the same key or the same lock. 418 419 #### Design the Algorithm with Strategies Solved 420 421 Knowing the concrete strategies, the task now becomes how to compute the expected values efficiently. As you might have imagined, it can be achieved using dynamic programming due to the existence of overlapping subproblems. But let's examine another approach which might be easier to understand: compute $p_i (l, k)$, the total probability that the $i$-th member begins a subproblem with $l$ locks and $k$ counterfeit keys, and accumulate $e_i$'s during the computation. 422 423 Transitions for $p$ itself include (and those from $p$ to $e$ will be similar to): 424 425 1. The first member manages to open the lock without any prior information; 426 2. The second member makes a successful guess; 427 3. Any of the succeeding attempts succeeds; 428 4. Everyone uses the same key but it fails on all the locks. 429 430 For each $p_i(l, k)$, all the transition can be easily processed in $\Theta(1)$ time, except the third one. A verbatim implementation requires $O(L + K)$ time per state, which is apparently not efficient enough. Since $N \ll L$, a possible work-around is to compute the transition coefficient for each member, instead of each attempt. Intuitively, all attempts should share the same probability of success, regardless of the order. A simplified model is to draw all balls sequentially without replacement from a box of $1$ red ball and $(x-1)$ white balls, in which the red ball appears at the $i$-th attempt with an equal probability of $1/x$. Of course, the observation for our problem can also be proven mathematically, but let's omit it for simplicity. 431 432 This important observation reduces the time complexity of the third type of transition to $O(N)$, as we can first compute the maximum number of attempts for each member, and then multiply it with the common probability of a single attempt. However, this is still not enough for passing the problem (and we adjusted the constraints to prevent so). 433 434 The final trick to pass all testcases requires revisiting the transition coefficients we just computed. Notice that, if all the members have $a$ attempts in total (but for the third type of transition only, which excludes the first two), then: 435 436 * If $a$ is a multiple of $N$, then every member can have at most $a/N$ attempts; 437 * Otherwise, the first $a \bmod N$ members (right after the second member, who decides to advance with the same key or the same lock) can have at most $\lceil a/N\rceil$ attempts, while all the others can have at most $\lfloor a/N\rfloor$ attempts. 438 439 This implies that the transition coefficients consists of at most $3$ maximal contiguous subsequences of the same coefficients (in fact, if the coefficients are treated as a circular sequence, then there will be exactly $1$ or $2$ for the two cases respectively). Using techniques such as prefix sums helps further decrease the complexity of the computation to $\Theta(1)$ per state. 440 441 The total time complexity is $O(NLK)$. 442 443 **Code** 444 445 ``` 446 #include <cstdio> 447 #include <cstring> 448 using namespace std; 449 #define MOD 1000000007 450 #define MAXN 108 451 #define MAXL 5004 452 #define MAXK 27 453 int e[MAXN], p[2][MAXK][MAXN], inv[2 * MAXL + MAXK]; 454 inline void _update(int * const a, const int lbd, const int rbd, const int base, const int diff) { 455 (a[0] += base) %= MOD; 456 (a[lbd] += diff) %= MOD; 457 (a[rbd] += MOD - diff) %= MOD; 458 return ; 459 } 460 #define Hill(_a, _lbd, _rbd, _base, _diff) _update(_a, _lbd, _rbd, _base, _diff) 461 #define Valley(_a, _lbd, _rbd, _base, _diff) _update(_a, _rbd, _lbd, ((_base) + (_diff)) % MOD, MOD - (_diff)) 462 #define Update(_a, _lbd, _rbd, _base, _diff) { if (_lbd < _rbd) Hill(_a, _lbd, _rbd, _base, _diff); else Valley(_a, _lbd, _rbd, _base, _diff); } 463 int like() { 464 int n, l, k, i, j, a, b, dh, now, nxt, totk, ntry, prob, pd, pb, lbd, rbd; 465 scanf("%d %d %d", &n, &l, &k); 466 if (n == 1) { 467 printf("%d\n", l); 468 return 0; 469 } 470 inv[1] = 1; 471 j = 2 * l + k; 472 for (i = 2; i <= j; ++i) inv[i] = 1ll * (MOD - MOD / i) * inv[MOD % i] % MOD; 473 474 memset(p, 0, sizeof(p)); 475 memset(e, 0, sizeof(e)); 476 p[0][0][0] = 1; 477 p[0][0][1] = -1; 478 now = 0; nxt = 1; 479 for (i = 0; i < l; ++i) { 480 for (j = 0; j <= k; ++j) { 481 totk = l + k - i - j; 482 for (a = 1; a < n; ++a) (p[now][j][a] += p[now][j][a - 1]) %= MOD; 483 for (a = 0; a < n; ++a) { 484 // Match at the first try 485 prob = 1ll * p[now][j][a] * inv[totk] % MOD; 486 (e[a] += prob) %= MOD; 487 if (a != n - 1) (e[a + 1] += MOD - prob) %= MOD; 488 (p[nxt][j][(a + 1) % n] += prob) %= MOD; 489 if (a != n - 2) (p[nxt][j][(a + 2) % n] += MOD - prob) %= MOD; 490 491 prob = 1ll * prob * inv[totk + l - i - 2] % MOD; 492 // Same lock 493 pd = 1ll * prob * (ntry = totk - 1) % MOD; 494 pb = 1ll * (ntry / n) * pd % MOD; 495 if (dh = ntry % n) { 496 lbd = (a + 1) % n; 497 rbd = (a + dh) % n + 1; 498 Update(e, lbd, rbd, pb, pd); 499 (++lbd) %= n; 500 ++(rbd %= n); 501 Update(p[nxt][j], lbd, rbd, pb, pd); 502 } 503 else { 504 (e[0] += pb) %= MOD; 505 (p[nxt][j][0] += pb) %= MOD; 506 } 507 508 // Same key 509 pd = 1ll * prob * (ntry = l - i - 1) % MOD; 510 if (j < k) { 511 pb = 1ll * pd * (k - j) % MOD; 512 b = (a + l - i) % n; 513 (p[now][j + 1][b] += pb) %= MOD; 514 if (b != n - 1) (p[now][j + 1][b + 1] += MOD - pb) %= MOD; 515 } 516 pb = 1ll * (ntry / n) * pd % MOD; 517 if (dh = ntry % n) { 518 lbd = (a + 1) % n; 519 rbd = (a + dh) % n + 1; 520 Update(e, lbd, rbd, pb, pd); 521 (++lbd) %= n; 522 ++(rbd %= n); 523 Update(p[nxt][j], lbd, rbd, pb, pd); 524 } 525 else { 526 (e[0] += pb) %= MOD; 527 (p[nxt][j][0] += pb) %= MOD; 528 } 529 } 530 } 531 532 now ^= 1; 533 nxt ^= 1; 534 memset(p[nxt], 0, sizeof(int) * MAXK * MAXN); 535 } 536 for (i = 1; i < n; ++i) (e[i] += e[i - 1]) %= MOD; 537 538 for (i = 0; i < n; ++i) printf("%d%c", e[i], " \n"[i == n - 1]); 539 return 0; 540 } 541 int main() { 542 int t; 543 scanf("%d", &t); 544 while (t--) { 545 like(); 546 } 547 return 0; 548 } 549 ``` 550 551 [2089D - Conditional Operators](/contest/2089/problem/D "Codeforces Round 1012 (Div. 1)") 552 Idea: [E.Space](/profile/E.Space "International Master E.Space") 553 554 **Solution** 555 556 Each operation transform three adjacent characters into one. If the string starts with `11`, the answer should be yes since we can first transform the remaining part into a single `0` or `1` and then the value of `11?` is always $1$. 557 558 If the string ends with `1`, only `101` has no solution, otherwise it starts with `11` or `0`, or we can transform `10?` in the front of the string into a 0. Then transform the rest part of the string into a single character to make the last operation `0?(anything):1` makes 1. 559 560 If an operation transformed a string ending with `0` into one ending with `1`, it must be `1?1:0` makes 1. 561 562 Consider the case where the strings contains `11` as a substring. After transforming the remaining part, `?11??` or `??11?` will be derived. The cases are `01100`, `00110`, `01110`, `10110`. All other cases start with `11` or end with `1`. 563 564 All cases of `??11?` have a solution: 565 566 `(0?0:1)?1:0` makes 1. 567 568 `(0?1:1)?1:0` makes 1. 569 570 `1?(0?1:1):0` makes 1. 571 572 However, `01100` has no solution. 573 574 Since `0?0:1` equals 1, before the last `1`, any two adjacent 0's with no `1` in between can be eliminated. Thus, if there are two 1's with an even number of 0's in between, and there are an even number of characters in front the former `1`, i.e., `(..)*1(00)*1(..)*0` in regular expression, the answer should be yes, since after eliminating the 0's in between, the 1's become adjacent. The parity of the characters before the former `1` guarantees that it will not become `01100`. 575 576 Another case is that the string ends with `0` and every pair of adjacent 1's has an odd number of 0's in between. Since `0(1?0:1)0` makes `000`, `1(0?1:0)1` makes `101`, `10(1?0:0)01` makes `10001`, there is no way to change the parity of the consecutive 0's to make `11` to change the ending `0` into `1`. 577 578 In the remaining case, there are even 0's between some pair of adjacent 1's, but the number of characters before the first 1 is odd, there must be only one pair. Suppose the string is 1-indexed. It is because the indices of such pair of 1's must be [odd, even]; while the indices in the previous case must be [even, odd]. Thus, if there are two such pairs of this case [odd, even], in the parity sequence [odd, even, ..., odd, even] there must be an [even, odd] as a substring. 579 580 Therefore, any other pair of adjacent 1's must have odd 0's in between, i.e., $0(00)^*\color{blue}{(10(00)^*)^*}\color{red}1\color{black}(00)^*\color{red}1\color{blue}{((00)^*01)^*}\color{black}(00)^+$ in regular expression. Any operation remains the string in this case, except that the string is $0(00)^*\color{blue}{(10(00)^*)^*}\color{red}1\color{red}1\color{black}(00)^+$ and the operation is $\color{red}1\color{black}?\color{red}1\color{black}:0$ makes 1. Since it must ends with `00`, it becomes a string ending with `0` and every pair of adjacent 1's has odd 0's in between, which is a case mentioned before that has no solution. 581 582 In conclusion, it has a solution if and only of at least one of the two following conditions is met: 583 584 * It ends with `1` but it is not `101`. 585 * It has two adjacent 1's such that there are even 0's in between and the number of characters before the former `1` is even. 586 587 **Code** 588 589 ``` 590 #include<bits/stdc++.h> 591 char s[333333]; 592 char val(char x,char y,char z){ 593 return x=='1'?y:z; 594 } 595 std::pair<std::string, char> fold(int l,int r){ 596 std::string str; 597 char v=s[r]; 598 for(int i=l;i<r;i+=2){ 599 str+=s[i]; 600 str+='?'; 601 str+=s[i+1]; 602 str+=':'; 603 } 604 str+=s[r]; 605 for(int i=r-2;i>=l;i-=2){ 606 v=val(s[i],s[i+1],v); 607 } 608 return std::make_pair(str,v); 609 } 610 void solve(){ 611 int n; 612 scanf("%d",&n); 613 n=2*n+1; 614 scanf("%s",s+1); 615 int last=0; 616 for(int i=1;i<=n;++i){ 617 if(s[i]=='1'&&last>0){ 618 if(i%2==0&&last&1){ 619 puts("Yes"); 620 std::string s4=fold(last+1,i).first; 621 auto tmp=fold(i+1,n); 622 std::string s5=tmp.first; 623 char v5=tmp.second; 624 if(last==1){ 625 printf("1?(%s):(%s)\n",s4.c_str(),s5.c_str()); 626 return; 627 } 628 tmp=fold(1,last-2); 629 std::string s1=tmp.first; 630 char v1=tmp.second; 631 if(v1=='1'){ 632 printf("(%s)?(%c?1:(%s)):(%s)\n",s1.c_str(),s[last-1],s4.c_str(),s5.c_str()); 633 } 634 else{ 635 printf("((%s)?%c:1)?(%s):(%s)\n",s1.c_str(),s[last-1],s4.c_str(),s5.c_str()); 636 } 637 return; 638 } 639 } 640 if(s[i]=='1'){ 641 last=i; 642 } 643 } 644 if(s[n]=='1'&&std::string(s+1)!="101"){ 645 puts("Yes"); 646 auto left=s[1]=='0'?fold(1,1):fold(1,3); 647 auto mid=s[1]=='0'?fold(2,n-1):fold(4,n-1); 648 printf("(%s)?(%s):1\n",left.first.c_str(),mid.first.c_str()); 649 return; 650 } 651 puts("No"); 652 return; 653 } 654 int main(){ 655 int T; 656 scanf("%d",&T); 657 while(T--){ 658 solve(); 659 } 660 return 0; 661 } 662 ``` 663 664 [2089E - Black Cat Collapse](/contest/2089/problem/E "Codeforces Round 1012 (Div. 1)") 665 Idea: [abruce](/profile/abruce "International Master abruce") 666 667 **Solution** 668 669 Firstly, consider a classical dp to calculate $dp_{u,k}$ as the number of delete $k$ vertices in subtree $u$ without considering deleting vertex $n-i+1$ everyday. This is trivial. 670 671 Then, due to the existence of an “automatic deletion” process, we cannot view the selected points within the subtree of $u$ as operations with only relative order, because they may be illegal. However, we consider the final operation sequence, putting the vertex chosen on the $i$ th day in the position $n-i+1$. That is, if we firstly choose $4$, then $3$, then $1$, it will be $0431$. Then, one vertex $u$ must be put in position $u$ or later. 672 673 Then, we find that for the subtree of vertex $u$ with DFS order interval $[l,r]$, all vertices can't be put in position before $l$, and it is always legal to put in position after $r$ if parent-child relations are satisfied. 674 675 So we consider a dp $f_{u,i,j,k}$ which represents that the subtree of $u$ leaves position $i$ for ancestors (which means nothing can be placed at position $i$ or before, and if $i=0$, then nothing is left for ancestors), there are $j$ empty spaces (not including the one left for ancestors), and $k$ vertices need to be put into positions after the subtree of $u$. In the $i=0$ case, we merge subtrees, and the subtree with smaller DFS order can put some backward operations into the space of the subtree with bigger DFS order. 676 677 Specifically, consider the sons of $u$ enumerated in reverse order of DFS, and the son is $v$. Then enumerate $w$ as how many backward operations of $v$ will fill in space of $u$. The transition is $f_{u,0,j+j1-w,k+k1-w}\leftarrow f_{u,0,j+j1-w,k+k1-w}+f_{u,0,j,k}\times f_{v,0,j1,k1}\times \binom{j}{w}\times\binom{k+k1-w}{k}$. That is, after putting $w$ operations from backward operations of $v$ into spaces of $u$, we merge the spaces of $u$ and $v$, then the backward operations of $u$ and $v$. 678 679 For $f_{v,i,j,k}(i\neq 0)$, it won't interfere with the transition with its following siblings. And for $f_{u,i,j,k}$,any operations from $v$ can't put into the subtree of $u$ and $v$, so we only need to merge backward operations of $u$ and $v$. 680 681 After finishing the transition of subtrees, we consider where to put $u$. 682 683 * If we don't put $u$, there will be one more space, and we can consider whether to leave it for ancestors if $i=0$.That is $f_{u,i,j,k}\rightarrow f_{u,i,j+1,k},f_{u,0,j,k}\rightarrow f_{u,u,j,k}$. 684 * We put $u$ into the position left for ancestors, that is $f_{u,i,j,k}\rightarrow f_{u,0,j+1,k}$. And we can leave another position for ancestors of $u$, that is $f_{u,i,j,k}\rightarrow f_{u,i1,j+1,k}(i1 \lt i)$. 685 * We put $u$ into position $u$, in that case, we can't leave position for ancestors of $u$, that is $f_{u,0,j,k}\rightarrow f_{u,0,j,k}$. 686 * We put $u$ backward, then we can't put anything in the subtree of $u$, but we can leave position for ancestors of $u$, that is $f_{u,i,siz_u-2,k}\rightarrow f_{u,i,siz_u-1,k+1},f_{u,0,siz_u-1,k}\rightarrow f_{u,0,siz_u,k+1}$. 687 688 The answer for $i$ operations is just we leave position $n-i+1$ for $1$, and there are $n-i$ spaces (therefore the spaces are before $n-i+1$) and no backward operations. 689 690 The time complexity is $O(\sum n^5)$. 691 692 **Code** 693 694 ``` 695 #include<bits/stdc++.h> 696 using namespace std; 697 typedef long long ll; 698 int read() { 699 int x=0,f=1; 700 char c=getchar(); 701 while(c<'0'||c>'9') { 702 if(c=='-')f=-1; 703 c=getchar(); 704 } 705 while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); 706 return x*f; 707 } 708 namespace tokido_saya { 709 const int maxn=81,mod=998244353; 710 typedef vector<int>::iterator iter; 711 int n,lp[maxn],rp[maxn],siz[maxn],t; 712 vector<int> v[maxn]; 713 ll f[maxn][maxn][maxn][maxn],dp[maxn][maxn],fac[maxn],inv[maxn]; 714 int zc[maxn][maxn][maxn][maxn]; 715 ll qpow(ll x,int y) 716 { 717 ll w=1; 718 while(y) 719 { 720 if(y&1)w=w*x%mod; 721 x=x*x%mod,y>>=1; 722 } 723 return w; 724 } 725 ll C(int x,int y) 726 { 727 if(y<0||y>x)return 0; 728 return fac[x]*inv[x-y]%mod*inv[y]%mod; 729 } 730 void dfs1(int u) 731 { 732 lp[u]=rp[u]=u; 733 for(iter it=v[u].begin();it!=v[u].end();it++)dfs1(*it),rp[u]=max(rp[u],rp[*it]); 734 } 735 void dfs2(int u) 736 { 737 f[u][0][0][0]=1,dp[u][0]=1; 738 for(iter it=v[u].begin();it!=v[u].end();it++) 739 { 740 int v=*it; 741 dfs2(v); 742 for(int i=siz[u];i>=0;i--) 743 for(int j=siz[v];j;j--)dp[u][i+j]=(dp[u][i+j]+dp[u][i]*dp[v][j]%mod*C(i+j,j))%mod; 744 for(int j1=0;j1<=siz[v];j1++) 745 for(int k1=0;k1<=min(j1+1,siz[v]);k1++) 746 { 747 memset(zc[j1][k1],0,sizeof(zc[j1][k1])); 748 for(int j=0;j<=siz[u];j++) 749 for(int k=0;k<=j+1;k++) 750 for(int w=0;w<=min(k1,j);w++)zc[j1][k1][j+j1-w][k+k1-w]=(zc[j1][k1][j+j1-w][k+k1-w]+f[u][0][j][k]*C(j,w)%mod*C(k+k1-w,k))%mod; 751 } 752 memset(f[u][0],0,sizeof(f[u][0])); 753 for(int j=0;j<=siz[v];j++) 754 for(int k=0;k<=j+1;k++) 755 for(int j1=0;j1<=siz[u]+siz[v];j1++) 756 for(int k1=0;k1<=min(siz[u]+siz[v],j1+1);k1++) 757 if(zc[j][k][j1][k1]) 758 { 759 const int w=zc[j][k][j1][k1]; 760 f[u][0][j1][k1]=(f[u][0][j1][k1]+f[v][0][j][k]*w)%mod; 761 for(int i=lp[v];i<=rp[v];i++)f[u][i][j1][k1]=(f[u][i][j1][k1]+f[v][i][j][k]*w)%mod; 762 } 763 for(int i=rp[v]+1;i<=rp[u];i++) 764 for(int j=siz[u]-1;j>=i-rp[v]-1;j--) 765 for(int k=j+1;k>=0;k--) 766 { 767 const int val=f[u][i][j][k]; 768 f[u][i][j][k]=0; 769 for(int p=0;p<=siz[v];p++) 770 for(int w=0;w<=min(p,j-(i-rp[v]-1));w++)f[u][i][j+siz[v]-w][k+p-w]=(f[u][i][j+siz[v]-w][k+p-w]+dp[v][p]*val%mod*C(j-(i-rp[v]-1),w)%mod*C(k+p-w,k))%mod; 771 } 772 siz[u]+=siz[v]; 773 } 774 for(int i=siz[u];i>=0;i--)dp[u][i+1]=(dp[u][i+1]+dp[u][i])%mod; 775 if(u!=1)for(int j=siz[u];j>=0;j--) 776 for(int k=min(j+1,siz[u]);k>=0;k--) 777 { 778 ll sum=0; 779 for(int i=rp[u];i>=lp[u];i--) 780 { 781 const int w=f[u][i][j][k]; 782 f[u][i][j+1][k]=(f[u][i][j+1][k]+w)%mod; 783 if(j==siz[u]-1)f[u][i][j+1][k+1]=(f[u][i][j+1][k+1]+w)%mod; 784 f[u][i][j][k]=sum,sum=(sum+w)%mod; 785 } 786 const int w=f[u][0][j][k]; 787 f[u][lp[u]][j][k]=(f[u][lp[u]][j][k]+w)%mod,f[u][0][j+1][k]=(f[u][0][j+1][k]+w+sum)%mod; 788 if(j==siz[u])f[u][0][j+1][k+1]=(f[u][0][j+1][k+1]+w)%mod,f[u][lp[u]][j][k+1]=(f[u][lp[u]][j][k+1]+w)%mod; 789 } 790 siz[u]++; 791 } 792 int main() { 793 int x,y; 794 t=read(),fac[0]=1; 795 for(int i=1;i<=80;i++)fac[i]=fac[i-1]*i%mod; 796 inv[80]=qpow(fac[80],mod-2); 797 for(int i=80;i;i--)inv[i-1]=inv[i]*i%mod; 798 while(t--) 799 { 800 n=read(),memset(f,0,sizeof(f)),memset(dp,0,sizeof(dp)),memset(siz,0,sizeof(siz)); 801 for(int i=1;i<=n;i++)v[i].clear(); 802 for(int i=1;i<n;i++) 803 { 804 x=read(),y=read(); 805 if(x>y)swap(x,y); 806 v[x].push_back(y); 807 } 808 for(int i=1;i<n;i++)sort(v[i].begin(),v[i].end()),reverse(v[i].begin(),v[i].end()); 809 dfs1(1),dfs2(1); 810 for(int i=n;i>1;i--)printf("%lld ",f[1][i][i-2][0]); 811 puts("1"); 812 } 813 return 0; 814 } 815 } 816 int main() { 817 return tokido_saya::main(); 818 } 819 ```