codeforces-scrape

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

1975.md (43659B)


      1 Source: https://codeforces.com/blog/entry/129801
      2 
      3 [1975A - Bazoka and Mocha's Array](/contest/1975/problem/A)
      4 
      5 Idea: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") Solution: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") Prepared by: [Bazoka13](/profile/Bazoka13 "Master Bazoka13")
      6 
      7 **Hint 1**
      8 
      9 We can't do any insertions by the operation.
     10 
     11 **Hint 2**
     12 
     13 If the answer is yes, we can make $a$ become non-decreasing in no more than one operation.
     14 
     15 **Solution**
     16 
     17 Read the hints.
     18 
     19 If $a$ is non-decreasing initially, the answer is yes.
     20 
     21 If $a$ isn't non-decreasing initially, we can find the smallest $i$ such that $a_i \gt a_{i+1}$. Then we choose $x=[a_1,a_2,...,a_i]$ and $y=[a_{i+1},a_{i+2},...,a_n]$. If the array $y+x$ is non-decreasing, the answer is yes. Otherwise, the answer is no.
     22 
     23 **Code**
     24 
     25 ```
     26 #include<bits/stdc++.h>
     27 using namespace std;
     28 const int N = 1e5+10;
     29 int a[N];
     30 int main(){
     31     int t;
     32     cin>>t;
     33     while(t--){
     34         int n;
     35         cin>>n;
     36         for(int i=1;i<=n;i++){
     37             cin>>a[i];
     38         }
     39         int pos=0;
     40         for(int i=1;i<n;i++){
     41             if(a[i]>a[i+1]){
     42                 pos=i;
     43                 break;
     44             }
     45         }
     46         if(!pos)cout<<"Yes\n";
     47         else{
     48             int fl=0;
     49             for(int i=pos+1;i<=n;i++){
     50                 int j=(i%n)+1;
     51                 if(a[i]>a[j])fl=1;
     52             }
     53             if(!fl)cout<<"Yes\n";
     54             else cout<<"No\n";
     55         }
     56     }
     57 }
     58 ```
     59 
     60 [1975B - 378QAQ and Mocha's Array](/contest/1975/problem/B)
     61 
     62 Idea: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") Solution: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") Prepared by: [Bazoka13](/profile/Bazoka13 "Master Bazoka13")
     63 
     64 **Hint 1**
     65 
     66 How to solve the problem if we only need to find a number $i$($1\leq i\leq n$) such that $a_k$ is divisible by $a_i$ for all $k$($1\leq k\leq n$)?
     67 
     68 **Hint 2**
     69 
     70 We only need to check whether all elements are divisible by the minimum element of the array.
     71 
     72 **Solution**
     73 
     74 Read the hints.
     75 
     76 Suppose the minimum element of $a$ is $x$. Then we iterate over $a$, if an element is not divisible by $x$, then we add it to $b$ ($b$ is initially empty).
     77 
     78 If $b$ is still empty after iterating $a$, the answer is yes.
     79 
     80 If $b$ isn't empty, we check whether all elements of $b$ are divisible by the minimum element of $b$. If so, the answer is yes. Otherwise, the answer is no.
     81 
     82 **Code**
     83 
     84 ```
     85 #include<bits/stdc++.h>
     86 using namespace std;
     87 #define ll long long
     88 const int N = 1e5+10;
     89 int a[N];
     90 int main(){
     91     int t;
     92     cin>>t;
     93     while(t--){
     94         int n;
     95         cin>>n;
     96         int fl=0;
     97         for(int i=1;i<=n;i++){
     98             cin>>a[i];
     99             if(a[i]==1)fl=1;
    100         }
    101         if(fl)cout<<"Yes\n";
    102         else{
    103             sort(a+1,a+1+n);
    104             vector<int> b;
    105             for(int i=2;i<=n;i++){
    106                 if(a[i]%a[1])b.push_back(a[i]);
    107             }
    108             sort(b.begin(),b.end());
    109             n = b.size();
    110             for(int j=1;j<n;j++){
    111                 if(b[j]%b[0]){
    112                     fl=1;
    113                     break;
    114                 }
    115             }
    116             if(!fl)cout<<"Yes\n";
    117             else cout<<"No\n";
    118         }
    119 
    120     }
    121 }
    122 ```
    123 
    124 [1975C - Chamo and Mocha's Array](/contest/1975/problem/C)
    125 
    126 Idea: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") Solution: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") Prepared by: [Bazoka13](/profile/Bazoka13 "Master Bazoka13")
    127 
    128 **Hint 1**
    129 
    130 If a subarray of length at least $2$ contains only the same elements, we can change all elements of the array to that element by operations.
    131 
    132 **Hint 2**
    133 
    134 Suppose the answer is $x$, we can perform no more than one operation on the original array $a$ so that there is a subarray of length at least $2$ that contains only $x$.
    135 
    136 **Hint 3**
    137 
    138 If we can make all elements of a subarray become $x$ in one operation, then there must be a subarray of length $3$ with a median of $y$ ($y\geq x$).
    139 
    140 **Solution**
    141 
    142 Read the hints.
    143 
    144 If $n=2$, the answer is the minimum element.
    145 
    146 If $n\geq 3$, we iterate over all subarrays of length $3$, and the answer is the maximum value of the median of all subarrays of length $3$.
    147 
    148 **Code**
    149 
    150 ```
    151 #include<bits/stdc++.h>
    152 using namespace std;
    153 const int N = 1e5+10;
    154 int a[N];
    155 int main(){
    156     int n,t;
    157     cin>>t;
    158     while(t--){
    159         cin>>n;
    160         for(int i=1;i<=n;i++) 
    161             cin>>a[i];
    162         if(n==2)cout<<min(a[1],a[2])<<"\n";
    163         else{
    164             int ans = min(a[1],a[2]);
    165             for(int i=1;i<=n-2;i++){
    166                 vector<int> tmp;
    167                 for(int k=0;k<=2;k++)
    168                     tmp.push_back(a[i+k]);
    169                 sort(tmp.begin(),tmp.end());
    170                 ans = max(ans,tmp[1]);
    171             }
    172             cout<<ans<<"\n";
    173         }
    174     }
    175 }
    176 ```
    177 
    178 [1975D - Paint the Tree](/contest/1975/problem/D)
    179 
    180 Idea: [SanweiTreap](/profile/SanweiTreap "Grandmaster SanweiTreap") Solution: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") Prepared by: [Bazoka13](/profile/Bazoka13 "Master Bazoka13")
    181 
    182 **Hint 1**
    183 
    184 If two pieces overlap at the beginning, can you solve the problem?
    185 
    186 **Hint 2**
    187 
    188 Consider the first time a vertex is painted blue. After this event occurs, what happens next?
    189 
    190 **Solution**
    191 
    192 Read the hints.
    193 
    194 In subsequent movements after the first time a vertex is painted blue, we can ignore the process of painting vertices red and then painting them blue.
    195 
    196 We call the first vertex painted blue $r$. Then it is not difficult to find that $P_A$ arrived at this vertex earlier than $P_B$. Considering all subsequent movements of $P_B$, $P_A$ can restore these movements one by one after reaching $r$, then $P_B$ will pass through all vertices have been painted red.
    197 
    198 If we know which vertex is $r$, this will be a classic problem, assuming the distance between the farthest vertex on the tree from $r$ and $r$ is $d$, then the answer is $2(n-1)-d$. Then we consider the strategies of $P_A$ and $P_B$ at this time. The two must be close to each other, and then until the first vertex is painted blue. If another vertex is $r$, although the value of $d$ may increase, every time the value of $d$ increases by $1$, the time when $P_A$ and $P_B$ meet will also increase by at least $1$, so the answer will not decrease.
    199 
    200 **Code**
    201 
    202 ```
    203 #include<bits/stdc++.h>
    204 using namespace std;
    205 #define ll long long
    206 const int N = 2e5+10;
    207 vector<int> g[N];
    208 int dep[N],f[N],mx,n,a,b;
    209 void dfs(int x,int fa){
    210     dep[x]=dep[fa]+1;
    211     mx = max(mx,dep[x]);
    212     f[x]=fa;
    213     for(auto i:g[x]){
    214         if(i==fa)continue;
    215         dfs(i,x);
    216     }
    217 }
    218 vector<int> move(int x,int y){
    219     if (dep[x] > dep[y]) swap(x, y);
    220     vector<int> track,ano;
    221     int tmp = dep[y] - dep[x], ans = 0;
    222     track.push_back(y);
    223     while(tmp--){
    224         y = f[y];
    225         track.push_back(y);
    226     }
    227     if (y == x) return track;
    228     ano.push_back(x);
    229     while (f[x] != f[y]) {
    230         x = f[x];
    231         y = f[y];
    232         ano.push_back(x);
    233         track.push_back(y);
    234     }
    235     track.push_back(f[y]);
    236     reverse(ano.begin(),ano.end());
    237     for(auto i:ano)track.push_back(i);
    238     return track;
    239 }
    240 int main(){
    241     int t;
    242     cin>>t;
    243     dep[0]=-1;
    244     while(t--){
    245         mx = -1;
    246         cin>>n;
    247         for(int i=1;i<=n;i++)g[i].clear();
    248         cin>>a>>b;
    249         for(int i=1;i<n;i++){
    250             int u,v;
    251             cin>>u>>v;
    252             g[u].push_back(v);
    253             g[v].push_back(u);
    254         }
    255         if(a==b){
    256             dfs(a,0);
    257             cout<<2*(n-1)-mx<<"\n";
    258             continue;
    259         }
    260         dfs(1,0);
    261         auto tr = move(a,b);
    262         int m = tr.size();
    263         if(tr[0]!=a)reverse(tr.begin(),tr.end());
    264         int x = tr[(m-1)/2];
    265         mx = -1;
    266         dfs(x,0);
    267         cout<<2*(n-1)-mx+(m-1-(m-1)/2)<<"\n";
    268     }
    269 }
    270 ```
    271 
    272 [1975E - Chain Queries](/contest/1975/problem/E)
    273 
    274 Idea: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") Solution: [Serval](/profile/Serval "Grandmaster Serval") Prepared by: [Bazoka13](/profile/Bazoka13 "Master Bazoka13")
    275 
    276 **Hint 1**
    277 
    278 Suppose the tree is a rooted tree, we only need to care about the number of black child vertices of each vertex.
    279 
    280 **Hint 2**
    281 
    282 If the black vertices form a chain, there is no black vertex that has three or more black child vertices. And there is at most one black vertex that has two black child vertices.
    283 
    284 **Hint 3**
    285 
    286 If the black vertices form a chain, there is at most one black vertex whose parent vertex is white.
    287 
    288 **Solution**
    289 
    290 Read the hints.
    291 
    292 We can maintain the number of black vertices with $0/1/2/3+$ black child vertices in $O(1)$. When we flip the color of one vertex, only it and its parent node are affected.
    293 
    294 If the black vertices form a chain: - no black vertex that has three or more black child vertices and there is at most one black vertex that has two black child vertices. - there is at most one black vertex whose parent vertex is white. - if there is one black vertex that has two black child vertices, its parent vertex must be white.
    295 
    296 **Code**
    297 
    298 ```
    299 #include<bits/stdc++.h>
    300 using namespace std;
    301 const int N = 1e6+10;
    302 
    303 int f[N];
    304 vector<int> g[N];
    305 int col[N],num[N];
    306 int faw,sum_two,sum_more,tot_black,xor_two;
    307 int n;
    308 void init(){
    309     sum_two=0;
    310     tot_black=0;
    311     sum_more=0;
    312     faw=0;
    313     xor_two=0;
    314     for(int i=1;i<=n;i++){
    315         g[i].clear();
    316         num[i]=0;
    317     }
    318 }
    319 
    320 void dfs(int x,int fa){
    321     f[x]=fa;
    322     if(col[x]==1)tot_black++;
    323     int sum=0;
    324     for(auto i:g[x]){
    325         if(i==fa)continue;
    326         dfs(i,x);
    327         if(col[i]==1)sum++;
    328     }
    329     if(col[fa]==0&&col[x]==1)faw++;
    330     if(col[x]==1){
    331         if(sum==2)sum_two++,xor_two^=x;
    332         if(sum>2)sum_more++;
    333     }
    334     num[x]=sum;
    335 }
    336 
    337 void flip(int x){
    338     col[x]^=1;
    339     int d = col[x]==1?1:-1;
    340     tot_black+=d;
    341     if(col[f[x]]==0)faw+=d;
    342     if(num[x]==2)sum_two+=d,xor_two^=x;
    343     if(num[x]>2)sum_more+=d;
    344     faw-=d*num[x];
    345     if(col[x]==1){
    346         if(col[f[x]]==1&&num[f[x]]==2)sum_two--,sum_more++,xor_two^=f[x];
    347         num[f[x]]++;
    348         if(col[f[x]]==1&&num[f[x]]==2)sum_two++,xor_two^=f[x];
    349     }else{
    350         if(col[f[x]]==1&&num[f[x]]==2)sum_two--,xor_two^=f[x];
    351         num[f[x]]--;
    352         if(col[f[x]]==1&&num[f[x]]==2){
    353             sum_two++;
    354             sum_more--;
    355             xor_two^=f[x];
    356         }
    357     }
    358 }
    359 
    360 bool check(){
    361     if(!tot_black)return false;
    362     if(sum_more||sum_two>1)return false;
    363     if(faw>1)return false;
    364     if(sum_two&&col[f[xor_two]]==1)return false;
    365     return true;
    366 }
    367 
    368 int main(){
    369     int t;
    370     scanf("%d",&t);
    371     while(t--){
    372         init();
    373         int q;
    374         scanf("%d %d",&n,&q);
    375         for(int i=1;i<=n;i++) cin>>col[i];
    376         for(int i=1;i<n;i++){
    377             int u,v;
    378             scanf("%d %d",&u,&v);
    379             g[u].push_back(v);
    380             g[v].push_back(u);
    381         }
    382         dfs(1,0);
    383         while(q--){
    384             int x;
    385             scanf("%d",&x);
    386             flip(x);
    387             if(check()) printf("Yes\n");
    388             else printf("No\n");
    389         }
    390     }
    391 }
    392 ```
    393 
    394 [1975F - Set](/contest/1975/problem/F)
    395 
    396 Idea: [Toxel](/profile/Toxel "International Grandmaster Toxel") Solution: [errorgorn](/profile/errorgorn "International Grandmaster errorgorn"), [Toxel](/profile/Toxel "International Grandmaster Toxel") Prepared by: [Nerovix](/profile/Nerovix "International Master Nerovix")
    397 
    398 **Hint 1**
    399 
    400 Consider enumerating each number from $0$ to $n-1$ whether it is contained by $S$, when we have enumerated the first $x$ numbers, there are only $2^{n-x}$ constraints.
    401 
    402 **Solution**
    403 
    404 Read the hints.
    405 
    406 Consider enumerating each number from $0$ to $n-1$ whether it is contained by $S$. Suppose that the current enumeration reaches $i$, and in the remaining constraints, $T_1$ and $T_2$ are two sets, the only difference between them is whether they contain $i$ ($T_1$ contains $i$):
    407 
    408 * $S$ contains $i$. We can merge $T_1$ and $T_2$ into a new constraint $T'$ and $v_{T'}=(v_{T_1}»1)$&$v_{T_2}$.
    409 * $S$ doesn't contain $i$. We can merge $T_1$ and $T_2$ into a new constraint $T'$ and $v_{T'}=v_{T_1}$&$v_{T_2}$.
    410 
    411 We can merge constraints quickly when the enumeration reaches a new number. And the time complexity is $O(n\cdot 2^n)$
    412 
    413 **Code**
    414 
    415 ```
    416 #include<bits/stdc++.h>
    417 
    418 using namespace std;
    419 
    420 const int N = 24, S = (1 << 20) + 5;
    421 int n = 0, f[N][S] = {};
    422 vector<int> ans;
    423 
    424 inline void dfs(int s = 0, int i = 0){
    425 	if(i < n){
    426 		int m = 1 << (n - i - 1);
    427 		for(int t = 0 ; t < m ; t ++) f[i + 1][t] = f[i][t] & f[i][m | t];
    428 		dfs(s << 1, i + 1);
    429 		for(int t = 0 ; t < m ; t ++) f[i + 1][t] = f[i][t] & (f[i][m | t] >> 1);
    430 		dfs(s << 1 | 1, i + 1);
    431 	}
    432 	else if(f[n][0] & 1) ans.push_back(s);
    433 }
    434 
    435 int main(){
    436 	scanf("%d", &n);
    437 	f[0][0] = 1;
    438 	for(int s = 1 ; s < 1 << n ; s ++) scanf("%d", &f[0][s]);
    439 	dfs();
    440 	printf("%d\n", int(ans.size()));
    441 	for(int s : ans) printf("%d\n", s);
    442 	return 0;
    443 }
    444 ```
    445 
    446 [1975G - Zimpha Fan Club](/contest/1975/problem/G)
    447 
    448 Idea: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish"), [zimpha](/profile/zimpha "Grandmaster zimpha") Solution: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") Prepared by: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish"), [errorgorn](/profile/errorgorn "International Grandmaster errorgorn"), [MagicalFlower](/profile/MagicalFlower "International Grandmaster MagicalFlower")
    449 
    450 **Hint 1**
    451 
    452 If $s, t$ both have $*$, or both don't have $*$, then it will be a simple problem. Can you try to solve this problem?
    453 
    454 **Hint 2**
    455 
    456 According to the first hint, we have discussed two cases. In the remaining cases, without loss of generality, we think that only $t$ has $*$. Suppose we write $t$ as $t'_0*t'_1*t'_2* \dots*t'_k$. Where $t'_i$ does not take $*$, assuming that $|t'_i| \leq 50$ is satisfied for all $i$, can you solve this problem?
    457 
    458 **Hint 3**
    459 
    460 There is a strictly subproblem of this problem, namely, given two strings $s$ and $t$ consisting only of characters from $a$ to $z$ and $-$, you need to find all positions in $s$ where $t$ can be matched.
    461 
    462 This problem has a classic solution, where $-$ is set to $0$, and $a$ to $z$ are sequentially assigned values from $1$ to $26$, and then let $f_i = \sum_{j=1}^m [s_{i +j-1} \gt 0] \times [t_j \gt 0] (s_{i+j-1}-t_j)^2$, then all positions of $f_i = 0$ satisfy $s[i, i + m -1]$ can match $t$​.
    463 
    464 Decompose the calculation formula, $f_i = \sum_{j=1}^m s_{i+j-1}^2+s_j^2 - 2\sum_{j=1}^m s_{i+j -1}{t_j} - \sum_{j=1}^m [s_{i+j-1} = 0] t_j^2 - \sum_{j=1}^m s_{i+j-1}^ 2[t_j=0]$. For $\sum_{j=1}^m s_{i+j-1}^2+s_j^2$, you can prefix and process it, and for the remaining part, you can use FFT in $O(n \log n )$ to be resolved.
    465 
    466 What is the use of this solution in the original problem?
    467 
    468 **Solution**
    469 
    470 Read the hints.
    471 
    472 In the following, we consider $n, m$ to be of the same order.
    473 
    474 Consider the case where $s$ and $t$ do not contain $*$. We only need to be compared bit by bit.
    475 
    476 Consider the case where $s, t$ both contain $*$, if the beginning of $s$ is not $*$ or the beginning of $t$ is not $*$:
    477 
    478 * If one of the first characters of $s$ and $t$ is $*$ or the first characters can match, delete the first characters of the two strings that are not $*$.
    479 * Oherwise the answer is obviously `No`.
    480 
    481 Performing the same operation on the last characters, it is not difficult to find that it will be reduced to two strings $*s’$ and $t'*$, where $s'$ and $t'$ are arbitrary strings. Then it is not difficult to find that $t's'$ matches two strings at the same time. Therefore, as long as the head and tail can be successfully deleted, the answer must be `Yes`.
    482 
    483 Consider the hardest case. Without loss of generality, we assume that only $t$ contains $*$, otherwise $s, t$ can be exchanged. We still delete the beginning and the end first. It is not difficult to find that thereafter $t$ can be written as $*t'_1*t'_2*\dots*t'_k *$.
    484 
    485 Then we will have a greedy solution. We iterate $i$ from $1$ to $n$, find the first matching position of $t'_i$ in $s$ each time, and delete tthese matching characters and all preceding characters in $s$, that is, remove a prefix of $s$, and then until all matching is completed or no matching position is found in $s$.
    486 
    487 Assume that we use FFT to brute force solve this problem every time. See Hint.3 for the specific solution, then the complexity is $O(nk \log n)$.
    488 
    489 But it is not difficult to find that this is very wasteful. In fact, we can do this:
    490 
    491 * When matching $t'_i$, only take out the first $|2t'_i|$ characters of $s$ each time and try to match $t'_i$. Because if the match is successful, then since all positions matching $t'_i$ are deleted, it is not difficult to find that at least $|t'_i|$ characters are deleted. And if the match fails, it is not difficult to find that the first $|t'_i|$ characters of $s$ will no longer be useful and can also be deleted. Therefore we remove at least the first $|t'_i|$ characters in $s$ in complexity $O(|t'_i| \log |t'_i|)$.
    492 
    493 Since the total length of $s$ is $n$, the total time complexity does not exceed $O(n \log n)$.
    494 
    495 **Code**
    496 
    497 ```
    498 #include<bits/stdc++.h>
    499 
    500 using namespace std;
    501 typedef long long ll;
    502 
    503 const ll N = (1 << 22) + 5, Mod = 2013265921, G = 31;
    504 
    505 inline ll power(ll x, ll y){
    506 	ll ret = 1;
    507 	while(y){
    508 		if(y & 1) ret = ret * x % Mod;
    509 		x = x * x % Mod, y >>= 1;
    510 	}
    511 	return ret;
    512 }
    513 
    514 ll p[N] = {}, w[N] = {}, g[N] = {}, iv[N] = {};
    515 
    516 inline void dft(ll n, ll a[], bool idft){
    517 	for(ll i = 0 ; i < n ; i ++) if(i < p[i]) swap(a[i], a[p[i]]);
    518 	for(ll m = 1 ; m < n ; m <<= 1) for(ll j = 0, k = 0 ; j < n ; j += m << 1, k ++) for(ll i = j ; i < j + m ; i ++){
    519 		ll x = a[i], y = a[i + m];
    520 		a[i] = x + y, a[i] >= Mod && (a[i] -= Mod);
    521 		a[i + m] = (x - y + Mod) * w[k] % Mod;
    522 	}
    523 	if(!idft) return;
    524 	reverse(a + 1, a + n);
    525 	for(int i = 0 ; i < n ; i ++) a[i] = a[i] * iv[n] % Mod;
    526 }
    527 
    528 inline ll sqr(ll x){
    529 	return x * x;
    530 }
    531 
    532 ll n = 0, m = 0, a[3][N] = {}, b[3][N] = {}, c[N] = {}, d[N] = {};
    533 char s[N] = {}, t[N] = {};
    534 
    535 inline ll work(ll L, ll R, ll l, ll r){
    536 	ll M = 1; while(M < R - L + r - l) M <<= 1;
    537 	w[0] = 1;
    538 	for(ll k = 1 ; k < M ; k <<= 1){
    539 		ll bit = M / 2 / k;
    540         if(k == M / 2) for(ll i = 0; i < k ; i ++) p[i + k] = p[i] | bit;
    541         else for(ll i = 0 ; i < k ; i ++){
    542             w[i + k] = w[i] * g[k] % Mod;
    543             p[i + k] = p[i] | bit;
    544         }
    545     }
    546 	for(ll i = 0 ; i < M ; i ++){
    547 		p[i] = p[i >> 1] >> 1;
    548 		if(i & 1) p[i] |= M >> 1;
    549 	}
    550 	ll z = 0;
    551 	for(ll i = 0 ; i < M ; i ++){
    552 		c[i] = 0;
    553 		for(ll f = 0 ; f < 3 ; f ++)  a[f][i] = b[f][i] = 0;
    554 	}
    555 	for(ll i = L ; i < R ; i ++){
    556 		ll x = (s[i] == '-') ? 0 : (s[i] - 'a' + 1);
    557 		a[0][i - L] = x ? 0 : 1, a[1][i - L] = 2 * x, a[2][i - L] = sqr(x), d[i] = sqr(x);
    558 	}
    559 	d[R] = 0;
    560 	for(ll i = l ; i < r ; i ++){
    561 		ll x = (t[i] == '-') ? 0 : (t[i] - 'a' + 1);
    562 		b[0][r - i] = sqr(x), b[1][r - i] = x, b[2][r - i] = x ? 0 : 1, z += sqr(x);
    563 	}
    564 	for(ll f = 0 ; f < 3 ; f ++){
    565 		dft(M, a[f], 0), dft(M, b[f], 0);
    566 		for(ll i = 0 ; i < M ; i ++) c[i] = (c[i] + a[f][i] * b[f][i]) % Mod;
    567 	}
    568 	dft(M, c, 1);
    569 	for(ll i = 0 ; i < r - l ; i ++) z += d[i + L];
    570 	for(ll i = L ; i <= R - (r - l) ; z -= d[i], z += d[i + (r - l)], i ++) if(z % Mod == c[i - L + r - l]) return i;
    571 	return -1;
    572 }
    573 
    574 int main(){
    575 	for(ll i = 1 ; i < N ; i <<= 1) g[i] = power(G, Mod / 4 / i), iv[i] = power(i, Mod - 2);
    576 	scanf("%lld %lld", &n, &m);
    577 	scanf("%s %s", s, t);
    578 	while(n && m && s[n - 1] != '*' && t[m - 1] != '*'){
    579 		if(s[n - 1] != t[m - 1] && s[n - 1] != '-' && t[m - 1] != '-'){
    580 			printf("No");
    581 			return 0;
    582 		}
    583 		else n --, m --;
    584 	}
    585 	reverse(s, s + n), reverse(t, t + m);
    586 	while(n && m && s[n - 1] != '*' && t[m - 1] != '*'){
    587 		if(s[n - 1] != t[m - 1] && s[n - 1] != '-' && t[m - 1] != '-'){
    588 			printf("No");
    589 			return 0;
    590 		}
    591 		else n --, m --;
    592 	}
    593 	reverse(s, s + n), reverse(t, t + m);
    594 	if(min(n, m) == 0){
    595 		while(n && s[n - 1] == '*') n --;
    596 		while(m && t[m - 1] == '*') m --;
    597 		if(max(n, m) == 0) printf("Yes");
    598 		else printf("No");
    599 		return 0;
    600 	}
    601 	bool u = 0, v = 0;
    602 	for(ll i = 0 ; i < n ; i ++) if(s[i] == '*') u = 1;
    603 	for(ll i = 0 ; i < m ; i ++) if(t[i] == '*') v = 1;
    604 	if(u){
    605 		if(v){
    606 			printf("Yes");
    607 			return 0;
    608 		}
    609 		else swap(n, m), swap(s, t);
    610 	}
    611 	ll L = 0, R = 0;
    612 	for(ll l = 1, r = l ; l < m ; l = r + 1, r = l){
    613 		while(t[r] != '*') r ++;
    614 		if(r - l) while(1){
    615 			R = min(n, L + 2 * (r - l));
    616 			if(R - L < r - l){
    617 				printf("No");
    618 				return 0;
    619 			}
    620 			ll h = work(L, R, l, r);
    621 			if(h == -1) L = R - (r - l) + 1;
    622 			else{
    623 				L = h + r - l;
    624 				break;
    625 			}
    626 		}
    627 	}
    628 	printf("Yes");
    629 	return 0;
    630 }
    631 ```
    632 
    633 [1975H - 378QAQ and Core](/contest/1975/problem/H)
    634 
    635 Idea: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") Solution: [Toxel](/profile/Toxel "International Grandmaster Toxel") Prepared by: [Bazoka13](/profile/Bazoka13 "Master Bazoka13")
    636 
    637 **Solution**
    638 
    639 Consider the maximum character $m$ of the string $s$.
    640 
    641 If $m$ only appears once, then obviously the string starting with it is the largest in lexicographical order. To make it the smallest, $m$ should be arranged at the end. Other characters can be arranged arbitrarily.
    642 
    643 If $m$ appears more than twice, it can be proven that the beginning and end of the answer string must be $m$. If the beginning of the string is not $m$, moving the character at the beginning to somewhere before a non-first $m$ can make the suffix lexicographical order starting with this $m$ smaller, while the suffix lexicographical order starting with $m$ after this remains unchanged. For suffixes that do not start with $m$, they are definitely not the largest, so they do not need to be considered. If the end of the string is not $m$, first remove it, and all suffix lexicographical orders become smaller. Similarly, it can also be placed in front of a certain $m$ to reduce the lexicographical order.
    644 
    645 In this case, the answer is always in the form of $ms_{1}ms_{2}m\dots ms_{t}m$. Where $s_{1},s_{2},\dots,s_{t}$ contain characters that are less than $m$, it could also be an empty string. Now suppose that the set ${s_{1},s_{2},\dots,s_{t}}$ is determined, and consider how to arrange their order. Suppose we are currently comparing two suffixes $S_{i}=ms_{i}m\dots ms_{t}m$ and $S_{j}=ms_{j}m\dots ms_{t}m$, and suppose $s_{i+k}$ and $s_{j+k}$ are the first two substrings that appear differently. Then $ms_{i}m\dots ms_{i+k-1}$ and $ms_{j}m\dots ms_{j+k-1}$ must be equal, and the size relationship between $S_{i}$ and $S_{j}$ is the same as the size relationship between $ms_{i+k}$ and $ms_{j+k}$. In this way, all $ms_{i}$ can be sorted according to lexicographical order, and regarded as a new character, and Solving the original problem for $(ms1​)(ms_2)…(ms_t​)$ is sufficient.
    646 
    647 Now consider how to determine the set ${s_{1},s_{2},\dots,s_{t}}$. For a certain $s_{i}$, it should obviously be ordered, because this can make $ms_{i}$ smaller. There is also another property. Suppose there are $s_{i}=p_{i}c$ and $s_{j}$ such that $ms_{j}$ is the current lexicographically largest string, and $mp_{i} \lt ms_{j}$, where $c$ is a character less than $m$. Putting $c$ after $s_{j}$ can make the answer smaller.
    648 
    649 The proof of the property is as follows. Without loss of generality, let $f_{1}=p_{i}c$, $f_{2}=p_{i}$, $f_{3}=s_{j}c$, $f_{4}=s_{j}$, then we have $mf_{2} \lt mf_{1} \lt mf_{4}$ and $f_{3}m \lt f_{4}m$. Consider the subproblem after iteration, by definition, $f_{4}$ is the largest character in the problem. If $f_{1}$ and $f_{4}$ are used, and there is an $f_{4}$ to the left of some $f_{1}$ in the optimal solution string, then replacing this $f_{1}$ and its nearest $f_{4}$ on the left with $f_{2}$ and $f_{3}$ respectively, it is easy to prove that the largest suffix will definitely become smaller or unchanged. Otherwise, all $f_{1}$ are to the left of all $f_{4}$, at this time you can arbitrarily replace some $f_{1}$ and $f_{4}$ with $f_{2}$ and $f_{3}$ respectively, it is easy to prove that the largest suffix still becomes smaller or unchanged.
    650 
    651 Based on the above discussion, we can now give the final greedy algorithm for the problem. Suppose the largest character $m$ has $t+1$ occurrences. If $t=0$, then put the only $m$ at the end, and the other characters can be arranged arbitrarily. Otherwise, suppose there are $p$ characters less than $m$, if $p\le t$, it can be proved that there is at most one character between any two $m$. Consider $|s_{i}|\ge2$, $s_{j}=\varepsilon$ (empty string), then they meet the above properties, and it is more optimal to exchange the last character of $s_{i}$ to $s_{j}$. Therefore, $s_{1},\dots,s_{p}$ is a single character, $s_{p+1}=\dots=s_{t}=\varepsilon$, and recursively solve the subproblem. Note that to ensure time complexity, when $t\gg p$, multiple rounds of recursion need to be combined.
    652 
    653 If $p \gt t$, it can be similarly proved that there will not be an $s_{i}$ that is an empty string. In addition, consider the first character of all $s_{i}$, for those among these $t$ characters that are not the largest, using the same property, it can be proved that the length of the string they are in must be $1$, and no other characters will follow. Also, since $s_{i}$ is ordered, it can be proved that the first character of all $s_{i}$ must be the smallest $t$ characters less than $m$. Next, the remaining characters will only be filled after those largest characters among these $t$ characters, and it can be similarly proved that those filled in the second position of these strings are also the smallest among the remaining characters, and so on, until all characters are used up.
    654 
    655 Notice that the complexity of each recursion is linear, and each recursion at least halves the number of characters, so the total complexity is $O(n\log n)$.
    656 
    657 **Bonus**
    658 
    659 How to solve this problem in $O(n)$?
    660 
    661 **Code**
    662 
    663 ```
    664 #include<bits/stdc++.h>
    665 using namespace std;
    666 struct ch{
    667     string c;
    668     ch(){c = "";}
    669     ch(string cc){c=cc;}
    670     bool operator == (const ch& p)const{
    671         return c==p.c;
    672     }
    673     bool operator != (const ch& p)const{
    674         return c!=p.c;
    675     }
    676     void add(ch& p){
    677         c.append(p.c);
    678     }
    679 };
    680 vector<ch> solve(vector<ch> cs){
    681     int n = cs.size();
    682     int t = 0;
    683     if(cs.empty())return cs;
    684     for(int i=n-2;i>=0;i--){
    685         if(cs[i]!=cs[n-1])break;
    686         t++;
    687     }
    688     if(t==0){
    689         vector<ch> res;
    690         res.push_back(cs[n-1]);
    691         return res;
    692     }
    693     int p = n-(t+1);
    694     if(p<=t){
    695         vector<ch> res;
    696         vector<ch> nxt;
    697         int k = (t+1)/(p+1);
    698         int le = (t+1)%(p+1);
    699         ch m = cs[n-1];
    700         for(int j=1;j<k;j++){
    701             m.add(cs[n-1]);
    702         }
    703         for(int i=0;i<p;i++){
    704             ch tmp = m;
    705             tmp.add(cs[i]);
    706             nxt.push_back(tmp);
    707         }
    708         for(int i=0;i<le;i++){
    709             nxt.push_back(cs[n-1]);
    710         }
    711         auto nxt_solved = solve(nxt);
    712         for(auto i:nxt_solved)res.push_back(i);
    713         res.push_back(m);
    714         return res;
    715     }else{
    716         vector<ch> res;
    717         vector<ch> nxt;
    718         ch m = cs[n-1];
    719         for(int i=0;i<t;i++){
    720             nxt.push_back(m);
    721         }
    722         int now = 0,beg=0;
    723         for(int i=0;i<p;i++){
    724             nxt[now].add(cs[i]);
    725             if(now>=1){
    726                 if(cs[i]!=cs[i-1]){
    727                     beg=now;
    728                 }
    729             }
    730             now++;
    731             if(now>=t)now=beg;
    732         }
    733         auto nxt_solved = solve(nxt);
    734         for(auto i:nxt_solved)res.push_back(i);
    735         res.push_back(m);
    736         return res;
    737     }
    738 }
    739 vector<ch> trans(string s){
    740     vector<ch> tmp;
    741     for(auto i:s){
    742         string tmpp = "";
    743         tmpp+=i;
    744         tmp.push_back(tmpp);
    745     }
    746     return tmp;
    747 }
    748 int main(){
    749     int t;
    750     cin>>t;
    751     while(t--){
    752         int n;
    753         cin>>n;
    754         string s;
    755         cin>>s;
    756         sort(s.begin(),s.end());
    757         auto tmp = trans(s);
    758         auto ans= solve(tmp); 
    759         for(auto c:ans)cout<<c.c;
    760         cout<<"\n";
    761     }
    762 }
    763 ```
    764 
    765 [1975I - Mind Bloom](/contest/1975/problem/I)
    766 
    767 Idea: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") Solution: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") Prepared by: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish"), [errorgorn](/profile/errorgorn "International Grandmaster errorgorn")
    768 
    769 **Hint 0**
    770 
    771 Play "Slay the Spire". Unfortunately, it doesn't help much.
    772 
    773 **Hint 1**
    774 
    775 It may be helpful to calculate the probability that your hand becomes empty instead of the probability that the draw pile becomes empty.
    776 
    777 **Hint 2**
    778 
    779 The intended solution is a $O(n^5)$ DP. The constant factor is small enough to run.
    780 
    781 **Solution**
    782 
    783 If all the cards in your hand is $0$, you immediately lose. Therefore, we only need to consider whether we can empty our hand by playing cards with non-$0$ value.
    784 
    785 Consider a sequence of playing cards that will lead to use losing. The sum over the probabilities of all these losing sequences is the probability of us losing.
    786 
    787 To simplify the process, we will consider drawing $x$ random cards from the deck as drawing a random card from the deck $x$ times.
    788 
    789 Consider a sequence of played cards as $z_1, z_2, \ldots, z_k$ where $z_i$ is the index of the card played. Consider how $z_i$ was drawn into our hand. It is not hard to see that either:
    790 
    791 * $z_i$ was in our hand at the start
    792 * $z_i$ from drawn from card $a_j$ where $j$ is the maximum index such that $z_j \leq z_i$ and $j \lt i$.
    793 
    794 From our previous observation, we can motivate the following range DP. Let $f(i,0/1,u,p,x)$ denote the a sequence of played cards with the following:
    795 
    796 * the minimum index of a card we played is $i$
    797 * whether there are any cards with value greater than $i$ that is one of the cards that were in our hand in the start
    798 * before we played this sequence, we played a card of value $u$
    799 * before we played this sequence, the deck has $p$ cards
    800 * The **net** number of cards that we draw is $x$
    801 
    802 We will use $g(i,0/1,u,p,x)$ to help us transition quickly. It is defined as the suffix sum (on dimension $i$) of $f$.
    803 
    804 Consider transitioning based on the card of index $i$.
    805 
    806 We have the following transition for $f(*,0,*,*,*)$:
    807 
    808 * $f(i, 0, u, p, x) = \sum_{y=0}^{x-(c_i-1)} g(i+1, 0, u, p, y) \times g(i, 0, c_i, p - (c_i - 1) - y, x - (c_i - 1) - y) \times \frac {u+y} {(p-y+1)^{\underline c_i}}$
    809 * $g(i, 0, u, p, x) = g(i+1, 0, u, p, x) + f(i, 0, u, p, x)$
    810 
    811 For $f(*,1,*,*,*)$, To handle the fact that there are some cards that are initially in our hands, let $h$ denote the the number of $j \gt i$ such that $s_j=1$.
    812 
    813 If $s_i = 1$, we have the following transitions:
    814 
    815 * $f(i, 1, u, p, x) = \sum_{y=h}^{x-c_i} g(i+1, 1, u, p, y) \times g(i, 0, c_i, p - (c_i - 1) - y+h, x - c_i - y) \times \frac {1} {(p-y+1+h)^{\underline c_i}}$
    816 * $g(i, 1, u, p, x) = f(i, 1, u, p, x)$
    817 
    818 If $s_i = 0$, we have the following transitions:
    819 
    820 * $f(i, 1, u, p, x) = \sum_{y=h}^{x-(c_i-1)} g(i+1, 1, u, p, y) \times g(i, 0, c_i, p - (c_i - 1) - y+h, x - (c_i - 1) - y) \times \frac {u+y} {(p-y+1+h)^{\underline c_i}}$
    821 * $g(i, 1, u, p, x) = g(i+1, 1, u, p, x) + f(i, 1, u, p, x)$
    822 
    823 The time complexity is $O(n^5)$.
    824 
    825 Now consider adding the cards with value $1$. It is possible that our game never terminates when we keep on drawing cards with value $1$. We will instead force that when we play a card of value $1$, we are not allowed to draw a card of value $1$. It is not hard to observe that the answer will not change.
    826 
    827 Consider $dp(i,x)$ to be the probability that we have in our hand:
    828 
    829 * $i$ card of value $0$
    830 * $x$ card of value $1$
    831 
    832 It is not hard to observe that for the initial state, $dp(i, o+x)$ is $g(1, 1, i+x, 0, m) \times \binom {i+x} i \times (m-o)^{\underline x}$.
    833 
    834 Next, consider the transitions. There are only two cases, we draw a card with value $0$, or a card with value greater than $0$:
    835 
    836 * $dp(i, x) \times \frac 1 {w+k-i}\rightarrow dp(i + 1, x - 1)$
    837 * $\forall j+y \gt 1, dp(i, x) \times g(1, 0, 1, n-d-i-x,j+y-1) \times \frac 1 {w+k-i} \times \binom {j+y} j \times (m-x+1)^{\underline y}\rightarrow dp(i+j, x+y-1)$
    838 
    839 Finally, the answer is $\sum_{i=0}^k dp(i, 0) \times k^{\underline i}$.
    840 
    841 The time complexity is $O(n^4)$.
    842 
    843 Therefore, the total complexity is $O(n^5)$. If we use FFT, it can be $O(n^4 \log n)$, but it was not required in our solution and would probably make the code slower.
    844 
    845 Furthermore, we can record $v$ instead of $u$, which means there are $v$ cards with $i$ or greater index drawn from $u$ draws. So it's not difficult to find $v \leq u $. And when $c_i \leq \sqrt n $, we have $v \leq u \leq c_i \leq \sqrt n $. And when $c_i \gt \sqrt n $, we have $v \leq \frac n {c_i - 1} \leq \sqrt n $, the complexity can become $O (n ^ {4.5}) $. If we use FFT, it can be $O (n ^ {3.5} \log n) $.
    846 
    847 Let $k$ be the number of cards with value $0$. It is not hard to see that:
    848 
    849 * the size of $i$ is $n-k$
    850 * the size of $x$ is $k$
    851 * the size of $u$ is $n-k$
    852 * the size of $p$ is $n$
    853 
    854 The number of states is $(n-k)^2k^2n$, which has a constant of $\frac{1}{16}$. We also have that $y \leq x$ and $u \leq c_i$, which both gives us another constant of $\frac{1}{2}$. Since we have a flag in our dp state, it has a factor of $2$. This gives us a constant factor of rougly $\frac{1}{32}$, which is extremely small. So it is reasonable to expect $O(n^5)$ to run about $1$ second.
    855 
    856 **Code**
    857 
    858 ```
    859 #include<bits/stdc++.h>
    860 
    861 using namespace std;
    862 typedef long long ll;
    863 
    864 const ll N = 120 + 5, Mod = 1e9 + 7;
    865 
    866 inline ll power(ll x, ll y){
    867 	ll ret = 1;
    868 	while(y){
    869 		if(y & 1) ret = ret * x % Mod;
    870 		x = x * x % Mod, y >>= 1;
    871 	}
    872 	return ret;
    873 }
    874 
    875 inline ll inv(ll x){
    876 	return power(x, Mod - 2);
    877 }
    878 
    879 ll n = 0, m = 0, w = 0, o = 0, d = 0, r = 0, k = 0, c[N] = {}, v[N] = {};
    880 ll iv[N] = {}, a[N][N] = {}, b[N][N] = {}, binom[N][N] = {};
    881 ll f[2][2][N][N][N] = {}, g[2][2][N][N][N] = {}, dp[N][N] = {};
    882 char s[N] = {};
    883 
    884 inline void init(){
    885 	n = m = w = o = d = r = k = 0;
    886 	memset(c, 0, sizeof(c)), memset(v, 0, sizeof(v)), memset(s, 0, sizeof(s));
    887 	memset(f, 0, sizeof(f)), memset(g, 0, sizeof(g)), memset(dp, 0, sizeof(dp));
    888 }
    889 
    890 inline void solve(){
    891 	scanf("%lld", &n);
    892 	v[0] = v[1] = 1;
    893 	for(ll i = 1 ; i <= n ; i ++){
    894 		scanf("%lld", &c[i]);
    895 		v[c[i]] = 1;
    896 	}
    897 	scanf("%s", s + 1);
    898 	for(ll i = 1 ; i <= n ; i ++){
    899 		if(s[i] == '0') r ++;
    900 		if(c[i] > 1) w ++;
    901 		else if(c[i] == 1){
    902 			if(s[i] == '1') o ++;
    903 			m ++;
    904 		}
    905 		else{
    906 			if(s[i] == '1') d ++;
    907 			else k ++;
    908 		}
    909 	}
    910 	if(c[n] <= 1){
    911 		for(ll i = 1 ; i <= n ; i ++) if(s[i] == '0'){
    912 			printf("0\n");
    913 			return;
    914 		}
    915 		printf("1\n");
    916 		return;
    917 	}
    918 	for(ll p = 0 ; p <= n ; p ++) for(ll u = 0 ; u <= c[n] ; u ++) if(v[u]){
    919 		f[1][0][u][p][0] = f[1][1][u][p][0] = 1;
    920 		g[1][0][u][p][0] = g[1][1][u][p][0] = 1;
    921 	}
    922 	for(ll i = n, h = 0 ; c[i] > 1 ; i --){
    923 		for(ll p = 0 ; p <= n ; p ++) for(ll u = 0 ; u <= c[i] ; u ++) if(v[u]){
    924 			g[0][0][u][p][0] = 1;
    925 			if(s[i] == '0') g[0][1][u][p][0] = g[1][1][u][p][0];
    926 		}
    927 		for(ll p = 0 ; p <= n ; p ++) for(ll u = 0 ; u <= c[i] ; u ++) if(v[u]) for(ll x = 1 ; x <= k ; x ++){
    928 			for(ll y = 0 ; y <= x - (c[i] - 1) ; y ++) f[0][0][u][p][x] = (f[0][0][u][p][x] + (g[1][0][u][p][y] * g[0][0][c[i]][p - (c[i] - 1) - y][x - (c[i] - 1) - y] % Mod) * ((u + y) * b[p - y + 1][c[i]] % Mod)) % Mod;
    929 			g[0][0][u][p][x] = (g[1][0][u][p][x] + f[0][0][u][p][x]) % Mod;
    930 		}
    931 		for(ll p = 0 ; p <= n ; p ++) for(ll u = 0 ; u <= c[i] ; u ++) if(v[u]) for(ll x = 1 ; x <= k ; x ++){
    932 			if(s[i] == '1'){
    933 				for(ll y = h ; y <= x - c[i] ; y ++) f[0][1][u][p][x] = (f[0][1][u][p][x] + (g[1][1][u][p][y] * g[0][0][c[i]][p - (c[i] - 1) - y + h][x - c[i] - y] % Mod) * b[p - y + 1 + h][c[i]]) % Mod;
    934 				g[0][1][u][p][x] = f[0][1][u][p][x];
    935 			}
    936 			else{
    937 				for(ll y = h ; y <= x - (c[i] - 1) ; y ++) f[0][1][u][p][x] = (f[0][1][u][p][x] + (g[1][1][u][p][y] * g[0][0][c[i]][p - (c[i] - 1) - y + h][x - (c[i] - 1) - y] % Mod) * ((u + y) * b[p - y + 1 + h][c[i]] % Mod)) % Mod;
    938 				g[0][1][u][p][x] = (g[1][1][u][p][x] + f[0][1][u][p][x]) % Mod;
    939 			}
    940 		}
    941 		for(ll p = 0 ; p <= n ; p ++) for(ll u = 0 ; u <= c[i] ; u ++) if(v[u]) for(ll x = 0 ; x <= k ; x ++){
    942 			f[1][0][u][p][x] = f[0][0][u][p][x], f[1][1][u][p][x] = f[0][1][u][p][x];
    943 			g[1][0][u][p][x] = g[0][0][u][p][x], g[1][1][u][p][x] = g[0][1][u][p][x];
    944 			f[0][0][u][p][x] = f[0][1][u][p][x] = g[0][0][u][p][x] = g[0][1][u][p][x] = 0;
    945 		}
    946 		if(s[i] == '1') h ++;
    947 	}
    948 	for(ll i = 0 ; i <= k ; i ++) for(ll x = 0 ; x <= m - o ; x ++) dp[i][o + x] = g[1][1][0][r][i + x] * (binom[i + x][i] * a[m - o][x] % Mod) % Mod;
    949 	for(ll i = 0 ; i <= k ; i ++) for(ll x = 1 ; x <= m ; x ++) if(dp[i][x]){
    950 		if(i < k) dp[i + 1][x - 1] = (dp[i + 1][x - 1] + dp[i][x] * iv[w + k - i]) % Mod;
    951 		for(ll j = 0 ; i + j <= k ; j ++) for(ll y = 0 ; x + y - 1 <= m ; y ++) if(j + y > 1) dp[i + j][x + y - 1] = (dp[i + j][x + y - 1] + (dp[i][x] * g[1][0][1][n - d - i - x][j + y - 1] % Mod) * (iv[w + k - i] * (binom[j + y][j] * a[m - x + 1][y] % Mod) % Mod)) % Mod;
    952 	}
    953 	ll ans = 1;
    954 	for(ll i = 0 ; i <= k ; i ++) ans = (ans + (Mod - dp[i][0]) * a[k][i]) % Mod;
    955 	printf("%lld\n", ans);
    956 }
    957 
    958 ll T = 0;
    959 
    960 int main(){
    961 	for(ll x = 0 ; x < N ; x ++){
    962 		a[x][0] = b[x][0] = 1, iv[x] = inv(x), binom[x][0] = 1;
    963 		for(ll y = 1 ; y <= x ; y ++){
    964 			a[x][y] = a[x][y - 1] * (x - y + 1) % Mod, b[x][y] = inv(a[x][y]);
    965 			binom[x][y] = (binom[x - 1][y - 1] + binom[x - 1][y]) % Mod;
    966 		}
    967 	}
    968 	scanf("%lld", &T);
    969 	for(ll i = 1 ; i <= T ; i ++) init(), solve();
    970 	return 0;
    971 }
    972 ```
    973 
    974 Solution by [Melania](/profile/Melania "Grandmaster Melania")
    975 
    976 **Solution**
    977 
    978 Let $ S $ denote the set of cards currently in Jellyfish's hand.
    979 
    980 We assume that $ a_1 = 0 $ and $ a_n \geq 2 $. Initially, $ |S| \in [1, n-1] $. Cases where these conditions do not hold are trivial.
    981 
    982 We observe that Jellyfish cannot empty the draw pile if and only if she runs out of non-zero cards to play. In the following section, we compute the probability that she eventually runs out of non-zero cards.
    983 
    984 It is clear that in any scenario where she runs out of non-zero cards, $ \max(S) $ must gradually decrease to zero. We can break down the entire process into sub-procedures, where in each sub-procedure, $ \max(S) $ decreases from $ i $ to $ \leq i-1 $, ultimately reaching zero.
    985 
    986 Assume she is currently in a state where $ \max(S) = i $ and $ |S \setminus {i}| = x $. We denote $ F_{i,x,y} $ as the probability that she will eventually transition to a state where $ \max(S) \leq i-1 $, and in the very first state where $ \max(S) \leq i-1 $, the size of $ S $ is $ y $.
    987 
    988 ---
    989 
    990 For a fixed and given pair $(i,x)$, we aim to compute all values of $F_{i,x,y}$ simultaneously.
    991 
    992 To determine the values of $F_{i,x,y}$, consider the situation after Jellyfish plays card $a_i$. For the remaining $n-x$ cards, each card is equally likely to be one of the $a_i$ cards drawn. Therefore, for any individual card outside of the initial $x$ cards, the probability of possessing that card is $p = \dfrac{a_i}{n-x}$.
    993 
    994 We define the initial event where Jellyfish plays card $a_i$ as the starting point of our timeline. Following this event, we consider $n-i+2$ key moments when $\max(S)$ becomes $\leq n$ for the first time, $\leq n-1$ for the first time, and so on, down to $\leq i+1$, $\leq i$, and finally $\leq i-1$ for the first time.
    995 
    996 We denote $G_{j,y}$ as the probability that Jellyfish will eventually reach a state where $\max(S) \leq j$, and in the very first state where $\max(S) \leq j$, the size of $S$ is $y$. Initially, $G_{n,x + a_i} = 1$.
    997 
    998 To understand the transitions of $G_{j,y}$, note that since all cards $\leq j$ (excluding the initial $x$ cards) are symmetrical, the probability of owning card $j$ is exactly $p=\dfrac{y-x}{j-x}$.
    999 
   1000 * If Jellyfish does not own card $j$, then the first state where $\max(S) \leq j-1$ is simply the first state where $\max(S) \leq j$. This describes a transition of $G_{j-1,y} \leftarrow (1-p)G_{j,y}$.
   1001 * If Jellyfish owns card $j$, we enumerate the number of cards $|S| = z$ in her hand when she first reaches $\max(S) \leq j-1$. The probability of this happening is $F_{j,y-1,z}$. Thus, we have $G_{j-1,z} \leftarrow pG_{j,y}F_{j,y-1,z}$.
   1002 
   1003 Here’s a further explanation of why "all cards $\leq j$ (excluding the initial $x$ cards) are symmetrical": Because this state is the very first time $\max(S) \leq j$, it means that all cards played before this state and after Jellyfish initially plays $a_i$ are $\geq j+1$. From the perspective of those cards $\geq j+1$, all cards $\leq j$ (excluding the initial $x$ cards) are symmetrical.
   1004 
   1005 ---
   1006 
   1007 In the end, the actual algorithm we derived for computing $F_{i,x,y}$ is quite straightforward:
   1008 
   1009 * Iterate through $j$ backwards from $n$ to $i$.
   1010 * For each $G_{j,y}$, make two types of transitions:
   1011 
   1012 1. $G_{j-1,z} \leftarrow pG_{j,y}F_{j,y-1,z}$, where $p = \dfrac{y-x}{j-x}$;
   1013 2. $G_{j-1,y} \leftarrow (1-p)G_{j,y}$.
   1014 
   1015 Finally, $F_{i,x,y} = G_{i-1,y}$.
   1016 
   1017 A small catch is that we could have self-loops. If $a_i = 1$, then in the final step where $j = i$, there will be some transitions where $F_{i,x,y} \leftarrow cF_{i,x,y}$. For a given $F_{i,x,y}$, if all the other known values that contribute to it sum to $A$ and all the $c$ coefficients sum to $C$, then we have $F_{i,x,y} = A + CF_{i,x,y}$. This results in $F_{i,x,y} = \dfrac{A}{1-C}$. We can address this by calculating the inverse.
   1018 
   1019 It can be shown that if we also iterate through $x$ from larger to smaller values, no $F_{i,x,y}$ will use other values of $F_{i',x',y'}$ that are neither known nor equal to $F_{i,x,y}$ itself. In other words, the value of $F_{i,x,y}$ does not invoke other unknown values of $F_{i',x',y'}$.
   1020 
   1021 ---
   1022 
   1023 After computing all values of $F_{i,x,y}$, we proceed to determine the final answer.
   1024 
   1025 We define $\text{ans}_{i,x}$ as the average probability that Jellyfish will eventually run out of non-zero cards (thus losing the game) if she starts with all $s_i$ cards in $[1, i]$ (which she owns initially) plus an additional $x$ cards drawn randomly from the remaining $i - s_i$ cards in $[1, i]$ (which she does not own initially).
   1026 
   1027 * If $c_i = 1$, the transition is given by: $\text{ans}_{i,x}=\displaystyle\sum F_{i,x-1,y}\text{ans}_{i-1,y}$;
   1028 * If $c_i = 0$, the transition is given by: $\text{ans}_{i,x}=(1-p)\text{ans}_{i-1,x}+p\displaystyle\sum F_{i,x-1,y}\text{ans}_{i-1,y}$, where $p=\dfrac{x-s_i}{i-s_i}$.
   1029 
   1030 Finally, we compute $1 - \text{ans}_{n,s_n}$ to obtain the probability that Jellyfish will eventually win the game.
   1031 
   1032 The time complexity of this approach is $\mathcal{O}(n^5 + n^3 \log p)$, and the space complexity is $\mathcal{O}(n^3)$.
   1033 
   1034 ---
   1035 
   1036 It is also possible to optimize the $\mathcal{O}(n^5)$ time complexity to $\mathcal{O}(n^4 \sqrt{n})$ by using Lagrange interpolation.
   1037 
   1038 To achieve this speedup, we notice that the values of $i$ and $x$ do not play a crucial role in the transition of $G_{j,y}$. Specifically, the influence of the values $i$ and $x$ on the transition of $G_{j,y}$ can be described as follows:
   1039 
   1040 * The initial value is $G_{n,x+a_i} = 1$.
   1041 * During the transition, $p = \dfrac{y-x}{j-x}$ and $1-p = \dfrac{j-y}{j-x}$.
   1042 
   1043 We can fix the value of $k = x + a_i$ and treat $x$ as a variable, maintaining a polynomial in $x$ as the value of $G_{j,y}$.
   1044 
   1045 We observe that it is only necessary to keep the point values between $[k-1, k-\sqrt{n}]$ to track the polynomial accurately.
   1046 
   1047 * For $a_i \gt \sqrt{n}$, since each transition involving multiplication by $p$ will increase the value of $y$ by at least $a_i$, it is clear that the degree of the polynomial $G_{j,y}$ is at most $\sqrt{n}$. Thus, keeping track of $\sqrt{n}$ values is sufficient to restore the polynomial, and we can use linear Lagrange interpolation to obtain the point values outside these $\sqrt{n}$ points.
   1048 * For $a_i \leq \sqrt{n}$, since $x = k - a_i$, we only care about the point values in the range $[k-1, k-\sqrt{n}]$. Although the polynomial restored may be inaccurate beyond this range, these point values are the ones that matter for our calculations anyway.
   1049 
   1050 By applying this optimization, we effectively reduce the time complexity to $\mathcal{O}(n^4 \sqrt{n} + n^3 \log p)$.