codeforces-scrape

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

2090.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 ![ ](https://espresso.codeforces.com/db9590b32cd739d8aff4b52b22fba9065f198177.png)
    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 ```