716.md (65278B)
1 Source: https://codeforces.com/blog/entry/47169 2 3 We hope everyone enjoyed the problems. Here is the editorial for the problems. I tried to make it more detailed but there might be some parts that might not be explained clearly. 4 5 ## [Div. 2 A — Crazy Computer](//codeforces.com/contest/716/problem/A) 6 7 Prerequisites : None 8 9 This is a straightforward implementation problem. Iterate through the times in order, keeping track of when is the last time a word is typed, keeping a counter for the number of words appearing on the screen. Increment the counter by 1 whenever you process a new time. Whenever the difference between the time for two consecutive words is greater than *c*, reset the counter to 0. After that, increment it by 1. 10 11 Time Complexity : *O*(*n*), since the times are already sorted. 12 13 **Code (O(n))** 14 15 ``` 16 #include <bits/stdc++.h> 17 #include <ext/pb_ds/assoc_container.hpp> 18 #include <ext/pb_ds/tree_policy.hpp> 19 20 using namespace std; 21 using namespace __gnu_pbds; 22 23 #define fi first 24 #define se second 25 #define mp make_pair 26 #define pb push_back 27 #define fbo find_by_order 28 #define ook order_of_key 29 30 typedef long long ll; 31 typedef pair<int,int> ii; 32 typedef vector<int> vi; 33 typedef long double ld; 34 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 35 typedef set<int>::iterator sit; 36 typedef map<int,int>::iterator mit; 37 typedef vector<int>::iterator vit; 38 39 const int N = 1e5 + 3; 40 ll a[N]; 41 int main() 42 { 43 ios_base::sync_with_stdio(0); cin.tie(0); 44 int n, c; cin >> n >> c; 45 for(int i = 0; i < n; i++) 46 { 47 cin >> a[i]; 48 } 49 //sort(a, a + n); 50 int cnt = 0; 51 for(int i = 0; i < n; i++) 52 { 53 if(i == 0) cnt++; 54 else 55 { 56 if(a[i] - a[i - 1] <= c) cnt++; 57 else cnt = 1; 58 } 59 } 60 cout << cnt; 61 return 0; 62 } 63 ``` 64 65 ## [Div. 2 B — Complete The Word](//codeforces.com/contest/716/problem/B) 66 67 Prerequisites : None 68 69 Firstly, if the length of the string is less than 26, output - 1 immediately. 70 71 We want to make a substring of length 26 have all the letters of the alphabet. Thus, the simplest way is to iterate through all substrings of length 26 (there are *O*(*n*) such substrings), then for each substring count the number of occurrences of each alphabet, ignoring the question marks. After that, if there exist a letter that occurs twice or more, this substring cannot contain all letters of the alphabet, and we process the next substring. Otherwise, we can fill in the question marks with the letters that have not appeared in the substring and obtain a substring of length 26 which contains all letters of the alphabet. After iterating through all substrings, either there is no solution, or we already created a nice substring. If the former case appears, output - 1. Otherwise, fill in the remaining question marks with random letters and output the string. 72 73 Note that one can optimize the solution above by noting that we don't need to iterate through all 26 letters of each substring we consider, but we can iterate through the substrings from left to right and when we move to the next substring, remove the front letter of the current substring and add the last letter of the next substring. This optimization is not required to pass. 74 75 We can still optimize it further and make the complexity purely *O*(|*s*|). We use the same trick as above, when we move to the next substring, we remove the previous letter and add the new letter. We store a frequency array counting how many times each letter appear in the current substring. Additionally, store a counter which we will use to detect whether the current substring can contain all the letters of the alphabet in *O*(1). When a letter first appear in the frequency array, increment the counter by 1. If a letter disappears (is removed) in the frequency array, decrement the counter by 1. When we add a new question mark, increment the counter by 1. When we remove a question mark, decrement the counter by 1. To check whether a substring can work, we just have to check whether the counter is equal to 26. This solution works in *O*(|*s*|). 76 77 Time Complexity : *O*(|*s*|·262), *O*(|*s*|·26) or *O*(|*s*|) 78 79 **Code (O(26^2*|s|)** 80 81 ``` 82 #include <bits/stdc++.h> 83 #include <ext/pb_ds/assoc_container.hpp> 84 #include <ext/pb_ds/tree_policy.hpp> 85 86 using namespace std; 87 using namespace __gnu_pbds; 88 89 #define fi first 90 #define se second 91 #define mp make_pair 92 #define pb push_back 93 #define fbo find_by_order 94 #define ook order_of_key 95 96 typedef long long ll; 97 typedef pair<int,int> ii; 98 typedef vector<int> vi; 99 typedef long double ld; 100 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 101 typedef set<int>::iterator sit; 102 typedef map<int,int>::iterator mit; 103 typedef vector<int>::iterator vit; 104 105 const int N = 10000; 106 int cnt[27]; 107 string s; int n; 108 109 bool valid() 110 { 111 for(int i = 0; i < 26; i++) 112 { 113 if(cnt[i] >= 2) return false; 114 } 115 return true; 116 } 117 118 void fillall() 119 { 120 for(int i = 0; i < n; i++) 121 { 122 if(s[i] == '?') s[i] = 'A'; 123 } 124 } 125 126 int main() 127 { 128 ios_base::sync_with_stdio(0); cin.tie(0); 129 cin >> s; 130 n = s.length(); 131 if(n < 26) {cout << -1; return 0;} 132 for(int i = 25; i < n; i++) 133 { 134 memset(cnt, 0, sizeof(cnt)); 135 for(int j = i; j >= i - 25; j--) 136 { 137 cnt[s[j]-'A']++; 138 } 139 if(valid()) 140 { 141 //cout << "GG " << i << '\n'; 142 int cur = 0; 143 while(cnt[cur]>0) cur++; 144 for(int j = i - 25; j <= i; j++) 145 { 146 if(s[j] == '?') 147 { 148 s[j] = cur + 'A'; 149 cur++; 150 while(cnt[cur]>0) cur++; 151 } 152 } 153 fillall(); 154 cout << s; 155 return 0; 156 } 157 } 158 cout << -1; 159 return 0; 160 } 161 ``` 162 163 **Code (O(26*|s|)** 164 165 ``` 166 #include <bits/stdc++.h> 167 #include <ext/pb_ds/assoc_container.hpp> 168 #include <ext/pb_ds/tree_policy.hpp> 169 170 using namespace std; 171 using namespace __gnu_pbds; 172 173 #define fi first 174 #define se second 175 #define mp make_pair 176 #define pb push_back 177 #define fbo find_by_order 178 #define ook order_of_key 179 180 typedef long long ll; 181 typedef pair<int,int> ii; 182 typedef vector<int> vi; 183 typedef long double ld; 184 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 185 typedef set<int>::iterator sit; 186 typedef map<int,int>::iterator mit; 187 typedef vector<int>::iterator vit; 188 189 const int N = 10000; 190 int cnt[27]; 191 string s; int n; 192 193 bool valid() 194 { 195 for(int i = 0; i < 26; i++) 196 { 197 if(cnt[i] >= 2) return false; 198 } 199 return true; 200 } 201 202 void fillall() 203 { 204 for(int i = 0; i < n; i++) 205 { 206 if(s[i] == '?') s[i] = 'A'; 207 } 208 } 209 210 int main() 211 { 212 ios_base::sync_with_stdio(0); cin.tie(0); 213 cin >> s; 214 n = s.length(); 215 if(n < 26) {cout << -1; return 0;} 216 for(int i = 0; i < 26; i++) cnt[s[i]-'A']++; 217 if(valid()) 218 { 219 int cur = 0; 220 while(cnt[cur]>0) cur++; 221 for(int i = 0; i < 26; i++) 222 { 223 if(s[i] == '?') 224 { 225 s[i] = cur + 'A'; 226 cur++; 227 while(cnt[cur]>0) cur++; 228 } 229 } 230 fillall(); 231 cout << s; 232 return 0; 233 } 234 for(int i = 26; i < n; i++) 235 { 236 cnt[s[i]-'A']++; cnt[s[i-26]-'A']--; 237 if(valid()) 238 { 239 //cout << "GG " << i << '\n'; 240 int cur = 0; 241 while(cnt[cur]>0) cur++; 242 for(int j = i - 25; j <= i; j++) 243 { 244 if(s[j] == '?') 245 { 246 s[j] = cur + 'A'; 247 cur++; 248 while(cnt[cur]>0) cur++; 249 } 250 } 251 fillall(); 252 cout << s; 253 return 0; 254 } 255 } 256 cout << -1; 257 return 0; 258 } 259 ``` 260 261 **Code (O(|s|)** 262 263 ``` 264 #include <bits/stdc++.h> 265 #include <ext/pb_ds/assoc_container.hpp> 266 #include <ext/pb_ds/tree_policy.hpp> 267 268 using namespace std; 269 using namespace __gnu_pbds; 270 271 #define fi first 272 #define se second 273 #define mp make_pair 274 #define pb push_back 275 #define fbo find_by_order 276 #define ook order_of_key 277 278 typedef long long ll; 279 typedef pair<int,int> ii; 280 typedef vector<int> vi; 281 typedef long double ld; 282 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 283 typedef set<int>::iterator sit; 284 typedef map<int,int>::iterator mit; 285 typedef vector<int>::iterator vit; 286 287 const int N = 50000; 288 int cnt[27]; 289 string s; int n; 290 int counter; 291 292 bool valid() 293 { 294 //cout << counter << endl; 295 return (counter == 26); 296 } 297 298 void fillall() 299 { 300 for(int i = 0; i < n; i++) 301 { 302 if(s[i] == '?') s[i] = 'A'; 303 } 304 } 305 306 int main() 307 { 308 ios_base::sync_with_stdio(0); cin.tie(0); 309 cin >> s; 310 n = s.length(); 311 if(n < 26) {cout << -1; return 0;} 312 counter = 0; 313 for(int i = 0; i < 26; i++) 314 { 315 if(s[i] == '?') 316 { 317 counter++; continue; 318 } 319 cnt[s[i]-'A']++; 320 if(cnt[s[i]-'A'] == 1) counter++; 321 } 322 if(valid()) 323 { 324 int cur = 0; 325 while(cnt[cur]>0) cur++; 326 for(int i = 0; i < 26; i++) 327 { 328 if(s[i] == '?') 329 { 330 s[i] = cur + 'A'; 331 cur++; 332 while(cnt[cur]>0) cur++; 333 } 334 } 335 fillall(); 336 cout << s; 337 return 0; 338 } 339 for(int i = 26; i < n; i++) 340 { 341 if(s[i] != '?') {cnt[s[i]-'A']++; if(cnt[s[i]-'A']==1) counter++;} 342 if(s[i-26] != '?') {cnt[s[i-26]-'A']--; if(cnt[s[i-26]-'A']==0) counter--;} 343 if(s[i-26] == '?') counter--; 344 if(s[i] == '?') counter++; 345 if(valid()) 346 { 347 int cur = 0; 348 while(cnt[cur]>0) cur++; 349 for(int j = i - 25; j <= i; j++) 350 { 351 if(s[j] == '?') 352 { 353 s[j] = cur + 'A'; 354 cur++; 355 while(cnt[cur]>0) cur++; 356 } 357 } 358 fillall(); 359 cout << s; 360 return 0; 361 } 362 } 363 cout << -1; 364 return 0; 365 } 366 ``` 367 368 ## [Div. 2 C/Div. 1 A — Plus and Square Root](//codeforces.com/contest/715/problem/A) 369 370 Prerequisites : None 371 372 Firstly, let *a**i*(1 ≤ *i* ≤ *n*) be the number on the screen before we level up from level *i* to *i* + 1. Thus, we require all the *a**i*s to be perfect square and additionally to reach the next *a**i* via pressing the plus button, we require  and  for all 1 ≤ *i* < *n*. Additionally, we also require *a**i* to be a multiple of *i*. Thus, we just need to construct a sequence of such integers so that the output numbers does not exceed the limit 1018. 373 374 There are many ways to do this. The third sample actually gave a large hint on my approach. If you were to find the values of *a**i* from the second sample, you'll realize that it is equal to 4, 36, 144, 400. You can try to find the pattern from here. My approach is to use *a**i* = [*i*(*i* + 1)]2. Clearly, it is a perfect square for all 1 ≤ *i* ≤ *n* and when *n* = 100000, the output values can be checked to be less than 1018 375 376 Unable to parse markup [type=CF_TEX] 377 378 which is a multiple of *i* + 1, and  is also a multiple of *i* + 1. 379 380 The constraints *a**i* must be a multiple of *i* was added to make the problem easier for Div. 1 A. 381 382 Time Complexity : *O*(*n*) 383 384 **Code (O(n))** 385 386 ``` 387 #include <bits/stdc++.h> 388 #include <ext/pb_ds/assoc_container.hpp> 389 #include <ext/pb_ds/tree_policy.hpp> 390 391 using namespace std; 392 using namespace __gnu_pbds; 393 394 #define fi first 395 #define se second 396 #define mp make_pair 397 #define pb push_back 398 #define fbo find_by_order 399 #define ook order_of_key 400 401 typedef long long ll; 402 typedef pair<ll,ll> ii; 403 typedef vector<int> vi; 404 typedef long double ld; 405 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 406 typedef set<int>::iterator sit; 407 typedef map<int,int>::iterator mit; 408 typedef vector<int>::iterator vit; 409 410 int main() 411 { 412 ios_base::sync_with_stdio(0); cin.tie(0); 413 ll n; cin >> n; 414 for(ll i = 1; i <= n; i++) 415 { 416 if(i == 1) cout << 2 << '\n'; 417 else cout << i*(i+1)*(i+1)-(i-1) << '\n'; 418 } 419 return 0; 420 } 421 ``` 422 423 ## [Div. 2 D/Div. 1 B — Complete The Graph](//codeforces.com/contest/715/problem/B) 424 425 Prerequisites : Dijkstra's Algorithm 426 427 This problem is actually quite simple if you rule out the impossible conditions. Call the edges that does not have fixed weight variable edges. First, we'll determine when a solution exists. 428 429 Firstly, we ignore the variable edges. Now, find the length of the shortest path from *s* to *e*. If this length is < *L*, there is no solution, since even if we replace the 0 weights with any positive weight the shortest path will never exceed this shortest path. Thus, if the length of this shortest path is < *L*, there is no solution. (If no path exists we treat the length as ∞.) 430 431 Next, we replace the edges with 0 weight with weight 1. Clearly, among all the possible graphs you can generate by replacing the weights, this graph will give the minimum possible shortest path from *s* to *e*, since increasing any weight will not decrease the length of the shortest path. Thus, if the shortest path of this graph is > *L*, there is no solution, since the shortest path will always be > *L*. If no path exists we treat the length as ∞. 432 433 Other than these two conditions, there will always be a way to assign the weights so that the shortest path from *s* to *e* is exactly *L*! How do we prove this? First, consider all paths from *s* to *e* that has at least one 0 weight edge, as changing weights won't affect the other paths. Now, we repeat this algorithm. Initially, assign all the weights as 1. Then, sort the paths in increasing order of length. If the length of the shortest path is equal to *L*, we're done. Otherwise, increase the weight of one of the variable edges on the shortest path by 1. Note that this will increase the lengths of some of the paths by 1. It is not hard to see that by repeating these operations the shortest path will eventually have length *L*, so an assignment indeed exists. 434 435 Now, we still have to find a valid assignment of weights. We can use a similar algorithm as our proof above. Assign 1 to all variable edges first. Next, we first find and keep track of the shortest path from *s* to *e*. Note that if this path has no variable edges it must have length exactly *L* or strictly more than *L*, so either we're already done or the shortest path contains variable edges and the length is strictly less than *L*. (otherwise we're done) 436 437 From now on, whenever we assign weight to a variable edge (after assigning 1 to every variable edge), we call the edge assigned. 438 439 Now, mark all variable edges not on the shortest path we found as ∞ weight. (we can choose any number greater than *L* as ∞) Next, we will find the shortest path from *s* to *e*, and replace the weight of an unassigned variable edge such that the length of the path becomes equal to *L*. Now, we don't touch the assigned edges again. While the shortest path from *s* to *e* is still strictly less than *L*, we repeat the process and replace a variable edge that is not assigned such that the path length is equal to *L*. Note that this is always possible, since otherwise this would've been the shortest path in one of the previous steps. Eventually, the shortest path from *s* to *e* will have length exactly *L*. It is easy to see that we can repeat this process at most *n* times because we are only replacing the edges which are on the initial shortest path we found and there are less than *n* edges to replace (we only touch each edge at most once). Thus, we can find a solution after less than *n* iterations. So, the complexity becomes . This is sufficient to pass all tests. 440 441 What if the constraints were *n*, *m* ≤ 105? Can we do better? 442 443 Yes! Thanks to [HellKitsune](/profile/HellKitsune "Гроссмейстер HellKitsune") who found this solution during testing. First, we rule out the impossible conditions like we did above. Then, we assign all the variable edges with ∞ weight. We enumerate the variable edges arbitarily. Now, we binary search to find the minimal value *p* such that if we make all the variable edges numbered from 1 to *p* have weight 1 and the rest ∞, then the shortest path from *s* to *e* has length ≤ *L*. Now, note that if we change the weight of *p* to ∞ the length of shortest path will be more than *L*. (if *p* equals the number of variable edges, the length of the shortest path is still more than *L* or it will contradict the impossible conditions) If the weight is 1, the length of the shortest path is ≤ *L*. So, if we increase the weight of edge *p* by 1 repeatedly, the length of the shortest path from *s* to *e* will eventually reach *L*, since this length can increase by at most 1 in each move. So, since the length of shortest path is non-decreasing when we increase the weight of this edge, we can binary search for the correct weight. This gives an  solution. 444 445 Time Complexity :  or  446 447 **Code (O(mnlogn))** 448 449 ``` 450 #include <bits/stdc++.h> 451 #include <ext/pb_ds/assoc_container.hpp> 452 #include <ext/pb_ds/tree_policy.hpp> 453 454 using namespace std; 455 using namespace __gnu_pbds; 456 457 #define fi first 458 #define se second 459 #define mp make_pair 460 #define pb push_back 461 #define fbo find_by_order 462 #define ook order_of_key 463 464 typedef long long ll; 465 typedef pair<ll,ll> ii; 466 typedef vector<int> vi; 467 typedef long double ld; 468 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 469 typedef set<int>::iterator sit; 470 typedef map<int,int>::iterator mit; 471 typedef vector<int>::iterator vit; 472 473 const int N = 1001; 474 const int M = 10001; 475 const ll INF = ll(1e18); 476 477 vector<ii> adj[N]; 478 vector<int> adj2[N]; 479 int L[M]; int R[M]; 480 ll d1[N]; 481 ll d2[N]; 482 int par[N]; 483 ll dist[N][N]; 484 485 int n, m, l, s, e; 486 487 void dijkstra() 488 { 489 d1[s] = 0; 490 priority_queue<ii, vector<ii>, greater<ii> > pq; 491 pq.push(ii(0, s)); 492 int cnt = 0; 493 while(!pq.empty()) 494 { 495 cnt++; 496 int u = pq.top().se; ll d = pq.top().fi; pq.pop(); 497 for(int i = 0; i < adj[u].size(); i++) 498 { 499 int v = adj[u][i].fi; ll w = adj[u][i].se; 500 if(d + w < d1[v]) 501 { 502 d1[v] = d + w; 503 pq.push(ii(d1[v], v)); 504 } 505 } 506 } 507 cerr << "DIJKSTRA OPERATIONS : " << cnt << '\n'; 508 } 509 510 bool dijkstra2() 511 { 512 d2[s] = 0; 513 priority_queue<ii, vector<ii>, greater<ii> > pq; 514 pq.push(ii(0, s)); 515 while(!pq.empty()) 516 { 517 int u = pq.top().se; ll d = pq.top().fi; pq.pop(); 518 for(int i = 0; i < adj2[u].size(); i++) 519 { 520 int v = adj2[u][i]; ll w = dist[u][v]; 521 if(d + abs(w) < d2[v]) 522 { 523 d2[v] = d + abs(w); 524 par[v] = u; 525 pq.push(ii(d2[v], v)); 526 } 527 } 528 } 529 if(d2[e] > l) return false; 530 int cur = e; 531 while(cur != s) 532 { 533 int p = par[cur]; 534 if(dist[p][cur] < 0) 535 { 536 dist[p][cur] = -2; dist[cur][p] = -2; 537 } 538 cur = par[cur]; 539 } 540 for(int i = 0; i < n; i++) 541 { 542 for(int j = 0; j < n; j++) 543 { 544 if(dist[i][j] == -1) 545 { 546 dist[i][j] = INF; 547 } 548 } 549 } 550 cur = e; 551 while(cur != s) 552 { 553 int p = par[cur]; 554 if(dist[p][cur] < 0) 555 { 556 dist[p][cur] = -1; dist[cur][p] = -1; 557 } 558 cur = par[cur]; 559 } 560 return true; 561 } 562 563 void print() 564 { 565 cout << "YES\n"; 566 for(int i = 0; i < m; i++) 567 { 568 int u = L[i]; int v = R[i]; 569 ll d = dist[u][v]; 570 if(d < 0) d = -d; 571 cout << u << ' ' << v << ' ' << d << '\n'; 572 } 573 } 574 575 bool relax() 576 { 577 for(int i = 0; i < n; i++) d2[i] = INF; 578 memset(par, -1, sizeof(par)); //shouldn't be neccesary 579 d2[s] = 0; 580 priority_queue<ii, vector<ii>, greater<ii> > pq; 581 pq.push(ii(0, s)); 582 while(!pq.empty()) 583 { 584 int u = pq.top().se; ll d = pq.top().fi; pq.pop(); 585 for(int i = 0; i < adj2[u].size(); i++) 586 { 587 int v = adj2[u][i]; ll w = dist[u][v]; 588 if(d + abs(w) < d2[v]) 589 { 590 d2[v] = d + abs(w); 591 par[v] = u; 592 pq.push(ii(d2[v], v)); 593 } 594 } 595 } 596 //cerr << d2[e] << '\n'; 597 if(d2[e] == l) return true; 598 int cur = e; bool meet = false; 599 while(cur != s) 600 { 601 int p = par[cur]; 602 if(!meet && dist[p][cur] < 0) 603 { 604 ll d = abs(dist[p][cur]); 605 dist[p][cur] = d + l - d2[e]; 606 dist[cur][p] = d + l - d2[e]; 607 //cerr << d << endl; 608 meet = true; 609 } 610 if(meet) break; 611 cur = par[cur]; 612 } 613 return false; 614 } 615 616 int dist1[N][N]; 617 618 int main() 619 { 620 ios_base::sync_with_stdio(0); cin.tie(0); 621 cin >> n >> m >> l >> s >> e; 622 memset(dist1, -1, sizeof(dist1)); 623 for(int i = 0; i < m; i++) 624 { 625 int u, v, w; cin >> u >> v >> w; 626 if(w > 0) 627 { 628 adj[u].pb(ii(v, w)); adj[v].pb(ii(u, w)); 629 adj2[u].pb(v); adj2[v].pb(u); 630 dist1[u][v] = w; dist1[v][u] = w; 631 dist[u][v] = w; dist[v][u] = w; 632 } 633 else 634 { 635 adj2[u].pb(v); adj2[v].pb(u); 636 dist[u][v] = -1; dist[v][u] = -1; 637 } 638 L[i] = u; R[i] = v; 639 } 640 for(int i = 0; i < n; i++) 641 { 642 d1[i] = INF; d2[i] = INF; 643 } 644 dijkstra(); //cerr << d1[e] << '\n'; 645 if(d1[e] < l) 646 { 647 cout << "NO\n"; 648 return 0; 649 } 650 if(d1[e] == l) 651 { 652 cout << "YES\n"; 653 for(int i = 0; i < m; i++) 654 { 655 int u = L[i]; int v = R[i]; 656 ll d = dist1[u][v]; 657 if(d <= 0) d = INF; 658 cout << u << ' ' << v << ' ' << d << '\n'; 659 } 660 return 0; 661 } 662 bool tmp = dijkstra2(); 663 if(!tmp) 664 { 665 cout << "NO\n"; 666 return 0; 667 } 668 //cerr << d2[e] << '\n'; 669 int cnt = 0; 670 while(!relax()) 671 { 672 relax(); cnt++; 673 } 674 cerr << "RELAXATIONS DONE : " << cnt << '\n'; 675 print(); 676 } 677 ``` 678 679 **Code (O(mlogn(logm+logL))** 680 681 ``` 682 #include <bits/stdc++.h> 683 #include <ext/pb_ds/assoc_container.hpp> 684 #include <ext/pb_ds/tree_policy.hpp> 685 686 using namespace std; 687 using namespace __gnu_pbds; 688 689 #define fi first 690 #define se second 691 #define mp make_pair 692 #define pb push_back 693 #define fbo find_by_order 694 #define ook order_of_key 695 696 typedef long long ll; 697 typedef pair<ll,ll> ii; 698 typedef vector<int> vi; 699 typedef long double ld; 700 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 701 typedef set<int>::iterator sit; 702 typedef map<int,int>::iterator mit; 703 typedef vector<int>::iterator vit; 704 705 const int N = 1001; 706 const int M = 10001; 707 const ll INF = ll(1e18); 708 709 int n, m, l, s, e; 710 711 struct edge 712 { 713 int to; ll w; int label; 714 edge(int _to, int _w, int _label){to = _to, w = _w, label = _label;} 715 }; 716 717 int edgecnt = -1; 718 vector<edge> adj[N]; 719 ll dist[N]; 720 set<ii> used; 721 722 ll dijk(int p, ll val) 723 { 724 for(int i = 0; i < n; i++) dist[i] = INF; 725 dist[s] = 0; 726 priority_queue<ii, vector<ii>, greater<ii> > pq; 727 pq.push(ii(0, s)); 728 while(!pq.empty()) 729 { 730 int u = pq.top().se; ll d = pq.top().fi; pq.pop(); 731 for(int i = 0; i < adj[u].size(); i++) 732 { 733 edge tmp = adj[u][i]; 734 int v = tmp.to; ll w = tmp.w; int lab = tmp.label; 735 if(lab >= 0) 736 { 737 if(lab < p) w = 1; 738 else if(lab == p) w = val; 739 else w = ll(1e14); 740 } 741 if(d + w < dist[v]) 742 { 743 dist[v] = d + w; 744 pq.push(ii(dist[v], v)); 745 } 746 } 747 } 748 return dist[e]; 749 } 750 751 void setw(int p, ll val) 752 { 753 for(int i = 0; i < n; i++) 754 { 755 for(int j = 0; j < adj[i].size(); j++) 756 { 757 int lab = adj[i][j].label; 758 if(lab >= 0) 759 { 760 if(lab < p) 761 { 762 adj[i][j].w = 1; 763 } 764 else if(lab == p) 765 { 766 adj[i][j].w = val; 767 } 768 else 769 { 770 adj[i][j].w = INF; 771 } 772 } 773 } 774 } 775 } 776 777 void print() 778 { 779 cout << "YES\n"; 780 for(int i = 0; i < n; i++) 781 { 782 for(int j = 0; j < adj[i].size(); j++) 783 { 784 edge tmp = adj[i][j]; 785 int v = tmp.to; ll w = tmp.w; 786 if(used.find(ii(i, v)) == used.end()) 787 { 788 cout << i << ' ' << v << ' ' << w << '\n'; 789 used.insert(ii(i, v)); used.insert(ii(v, i)); 790 } 791 } 792 } 793 } 794 795 int main() 796 { 797 ios_base::sync_with_stdio(0); cin.tie(0); 798 cin >> n >> m >> l >> s >> e; 799 for(int i = 0; i < m; i++) 800 { 801 int u, v, w; 802 cin >> u >> v >> w; 803 int lab = -1; 804 if(w == 0) 805 { 806 lab = ++edgecnt; 807 } 808 adj[u].pb(edge(v, w, lab)); 809 adj[v].pb(edge(u, w, lab)); 810 } 811 ll x = dijk(edgecnt, 1); ll y = dijk(-1, 1); 812 if(!(x <= l && l <= y)) 813 { 814 cout << "NO\n"; 815 return 0; 816 } 817 ll lo = -1; ll hi = edgecnt; 818 ll mid, ans; 819 while(lo <= hi) 820 { 821 mid = (lo+hi)/2; 822 if(dijk(mid, 1) <= l) 823 { 824 ans = mid; 825 hi = mid - 1; 826 } 827 else 828 { 829 lo = mid + 1; 830 } 831 } 832 //now [0..ans] as 1 will give <= L whereas [0..ans - 1] as 1 will give > L 833 if(ans == -1) 834 { 835 setw(-1, 0); 836 print(); 837 return 0; 838 } 839 lo = 1; hi = INF; 840 int ans2 = 0; 841 while(lo <= hi) 842 { 843 mid = (lo+hi)>>1; 844 if(dijk(ans, mid) <= l) 845 { 846 ans2 = mid; 847 lo = mid + 1; 848 } 849 else 850 { 851 hi = mid - 1; 852 } 853 } 854 //cerr << ans << ' ' << ans2 << '\n'; 855 setw(ans, ans2); 856 print(); 857 } 858 ``` 859 860 ## [Div. 2 E/Div. 1 C — Digit Tree](//codeforces.com/contest/715/problem/C) 861 862 Prerequisites : Tree DP, Centroid Decomposition, Math 863 864 Compared to the other problems, this one is more standard. The trick is to first solve the problem if we have a fixed vertex *r* as root and we want to find the number of paths passing through *r* that works. This can be done with a simple tree dp. For each node *u*, compute the number obtained when going from *r* down to *u* and the number obtained when going from *u* up to *r*, where each number is taken modulo *M*. This can be done with a simple dfs. To calculate the down value, just multiply the value of the parent node by 10 and add the value on the edge to it. To calculate the up value, we also need to calculate the height of the node. (i.e. the distance from *u* to *r*) Then, if we let *h* be the height of *u*, *d* be the digit on the edge connecting *u* to its parent and *val* be the up value of the parent of *u*, then the up value for *u* is equal to 10*h* - 1·*d* + *val*. Thus, we can calculate the up and down value for each node with a single dfs. 865 866 Next, we have to figure out how to combine the up values and down values to find the number of paths passing through *r* that are divisible by *M*. For this, note that each path is the concatenation of a path from *u* to *r* and *r* to *v*, where *u* and *v* are pairs of vertices from different subtrees, and the paths that start from *r* and end at *r*. For the paths that start and end at *r* the answer can be easily calculated with the up and down values (just iterate through all nodes as the other endpoint). For the other paths, we iterate through all possible *v*, and find the number of vertices *u* such that going from *u* to *v* will give a multiple of *M*. Since *v* is fixed, we know its height and down value, which we denote as *h* and *d* respectively. So, if the up value of *u* is equal to *up*, then *up*·10*h* + *d* must be a multiple of *M*. So, we can solve for *up* to be - *d*·10- *h* modulo *M*. Note that in this case the multiplicative inverse of 10 modulo *M* is well-defined, as we have the condition . To find the multiplicative inverse of 10, we can find φ(*M*) and since by Euler's Formula we have *x*φ(*M*) ≡ 1(*modM*) if , we have *x*φ(*M*) - 1 ≡ *x*- 1(*modM*), which is the multiplicative inverse of *x* (in this case we have *x* = 10) modulo *M*. After that, finding the *up* value can be done by binary exponentiation. 867 868 Thus, we can find the unique value of *up* such that the path from *u* to *v* is a multiple of *M*. This means that we can just use a map to store the up values of all nodes and also the up values for each subtree. Then, to find the number of viable nodes *u*, find the required value of *up* and subtract the number of suitable nodes that are in the same subtree as *v* from the total number of suitable nodes. Thus, for each node *v*, we can find the number of suitable nodes *u* in  time. 869 870 Now, we have to generalize this for the whole tree. We can use centroid decomposition. We pick the centroid as the root *r* and find the number of paths passing through *r* as above. Then, the other paths won't pass through *r*, so we can remove *r* and split the tree into more subtrees, and recursively solve for each subtree as well. Since each subtree is at most half the size of the original tree, and the time taken to solve the problem where the path must pass through the root for a single tree takes time proportional to the size of the tree, this solution works in  time, where the other  comes from using maps. 871 872 Time Complexity :  873 874 **Code** 875 876 ``` 877 #include <bits/stdc++.h> 878 #include <ext/pb_ds/assoc_container.hpp> 879 #include <ext/pb_ds/tree_policy.hpp> 880 881 using namespace std; 882 using namespace __gnu_pbds; 883 884 #define fi first 885 #define se second 886 #define mp make_pair 887 #define pb push_back 888 #define fbo find_by_order 889 #define ook order_of_key 890 891 typedef long long ll; 892 typedef pair<int,int> ii; 893 typedef vector<int> vi; 894 typedef long double ld; 895 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 896 typedef set<int>::iterator sit; 897 typedef map<int,int>::iterator mit; 898 typedef vector<int>::iterator vit; 899 900 const int N = 1e5 + 1; 901 const int MAX = 1e9; 902 int MOD, n; 903 904 bool isprime[100001]; 905 vector<ll> primes; 906 vector<ii> adj[N]; 907 int subsize[N]; 908 bool visited[N]; 909 int treesize; 910 vi clrlist; 911 ll up[N]; 912 ll down[N]; 913 int h[N]; 914 int PHI; 915 int dppart[N]; 916 917 ll mult(ll a, ll b) 918 { 919 return (a*b)%MOD; 920 } 921 922 ll add(ll a, ll b) 923 { 924 return (a+b+MOD)%MOD; 925 } 926 927 ll modpow(ll a, ll b) 928 { 929 ll r = 1; 930 while(b) 931 { 932 if(b&1) r=(r*a)%MOD; 933 a=(a*a)%MOD; 934 b>>=1; 935 } 936 return r; 937 } 938 939 void Sieve(int n) 940 { 941 memset(isprime, 1, sizeof(isprime)); 942 isprime[1] = false; 943 for(int i = 2; i <= n; i++) 944 { 945 if(isprime[i]) 946 { 947 primes.pb(i); 948 for(int j = 2*i; j <= n; j += i) 949 { 950 isprime[j] = false; 951 } 952 } 953 } 954 } 955 956 int phi(int n) 957 { 958 ll num = 1; ll num2 = n; 959 for(ll i = 0; primes[i]*primes[i] <= n; i++) 960 { 961 if(n%primes[i]==0) 962 { 963 num2/=primes[i]; 964 num*=(primes[i]-1); 965 } 966 while(n%primes[i]==0) 967 { 968 n/=primes[i]; 969 } 970 } 971 if(n>1) 972 { 973 num2/=n; num*=(n-1); 974 } 975 n = 1; 976 num*=num2; 977 return num; 978 } 979 980 ll inv(ll a) 981 { 982 return modpow(a, PHI-1); 983 } 984 985 void dfs(int u, int par) 986 { 987 if(par == -1) clrlist.clear(); 988 subsize[u] = 1; clrlist.pb(u); 989 for(int i = 0; i < adj[u].size(); i++) 990 { 991 int v = adj[u][i].fi; 992 if(visited[v]) continue; 993 if(v == par) continue; 994 dfs(v, u); 995 subsize[u] += subsize[v]; 996 } 997 if(par == -1) treesize = subsize[u]; 998 } 999 1000 int centroid(int u, int par) 1001 { 1002 for(int i = 0; i < adj[u].size(); i++) 1003 { 1004 int v = adj[u][i].fi; 1005 if(visited[v]) continue; 1006 if(v == par) continue; 1007 if(subsize[v]*2 > treesize) return centroid(v, u); 1008 } 1009 return u; 1010 } 1011 1012 int parts = 0; 1013 void fill(int u, int p, int cent) 1014 { 1015 if(p == cent) 1016 { 1017 dppart[u] = parts; 1018 parts++; 1019 } 1020 else if(p != -1) 1021 { 1022 dppart[u] = dppart[p]; 1023 } 1024 for(int i = 0; i < adj[u].size(); i++) 1025 { 1026 int v = adj[u][i].fi; int w = adj[u][i].se; 1027 if(v == p || visited[v]) continue; 1028 down[v] = add(mult(down[u], 10), w); 1029 up[v] = add(up[u], mult(modpow(10, h[u]), w)); 1030 h[v] = h[u] + 1; 1031 fill(v, u, cent); 1032 //cout << v << ' ' << u << ' ' << up[v] << ' ' << up[u] << '\n'; 1033 } 1034 } 1035 1036 ll solve(int cent) 1037 { 1038 for(int i = 0; i < clrlist.size(); i++) 1039 { 1040 up[clrlist[i]] = 0; down[clrlist[i]] = 0; h[clrlist[i]] = 0; 1041 } 1042 parts = 0; 1043 fill(cent, -1, cent); parts--; 1044 dppart[cent] = -1; 1045 map<ll,ll> tot; //only count up 1046 vector<map<ll,ll> > vec; //only count up, but in specific subtree 1047 vec.resize(parts+1); 1048 tot[0]++; 1049 for(int i = 0; i < clrlist.size(); i++) 1050 { 1051 int u = clrlist[i]; 1052 //cout << u << ' ' << up[u] << ' ' << down[u] << '\n'; 1053 if(u == cent) continue; 1054 tot[up[u]]++; 1055 vec[dppart[u]][up[u]]++; 1056 } 1057 ll ans = 0; 1058 for(int i = 0; i < clrlist.size(); i++) 1059 { 1060 int u = clrlist[i]; 1061 int ht = h[u]; 1062 int pt = dppart[u]; 1063 if(u == cent) 1064 { 1065 ans += (tot[0] - 1); //exclude cent as the vertex 1066 } 1067 else 1068 { 1069 ll val = ((-down[u])%MOD+MOD)%MOD; 1070 val = mult(val, inv(modpow(10, ht))); 1071 ans += (tot[val] - vec[pt][val]); 1072 } 1073 } 1074 return ans; 1075 } 1076 1077 ll compsolve(int u) 1078 { 1079 dfs(u, -1); 1080 int cent = centroid(u, -1); 1081 ll ans = solve(cent); 1082 //cout << u << ' ' << cent << ' ' << ans << '\n'; 1083 visited[cent] = true; 1084 for(int i = 0; i < adj[cent].size(); i++) 1085 { 1086 int v = adj[cent][i].fi; 1087 if(!visited[v]) ans += compsolve(v); 1088 } 1089 return ans; 1090 } 1091 1092 int main() 1093 { 1094 ios_base::sync_with_stdio(0); cin.tie(0); 1095 cin >> n >> MOD; 1096 if(MOD == 1) 1097 { 1098 cout << ll(n)*ll(n - 1); 1099 return 0; 1100 } 1101 Sieve(100000); PHI = phi(MOD); 1102 for(int i = 0; i < n - 1; i++) //tree is 0-indexed 1103 { 1104 int u, v, w; cin >> u >> v >> w; 1105 adj[u].pb(ii(v, w)); adj[v].pb(ii(u, w)); 1106 } 1107 cout << compsolve(0) << '\n'; 1108 return 0; 1109 } 1110 ``` 1111 1112 ## [Div. 1 D — Create a Maze](//codeforces.com/contest/715/problem/D) 1113 1114 Prerequisites : None 1115 1116 The solution to this problem is quite simple, if you get the idea. Thanks to [danilka.pro](/profile/danilka.pro "Гроссмейстер danilka.pro") for improving the solution to the current constraints which is much harder than my original proposal. 1117 1118 Note that to calculate the difficulty of a given maze, we can just use dp. We write on each square (room) the number of ways to get from the starting square to it, and the number written on (*i*, *j*) will be the sum of the numbers written on (*i* - 1, *j*) and (*i*, *j* - 1), and the edge between (*i* - 1, *j*) and (*i*, *j*) is blocked, we don't add the number written on (*i* - 1, *j*) and similarly for (*i*, *j* - 1). We'll call the rooms squares and the doors as edges. We'll call locking doors as edge deletions. 1119 1120 First, we look at several attempts that do not work. 1121 1122 Write *t* in its binary representation. To solve the problem, we just need to know how to construct a maze with difficulty 2*x* and *x* + 1 from a given maze with difficulty *x*. The most direct way to get from *x* to 2*x* is to increase both dimensions of the maze by 1. Let's say the bottom right square of the grid was (*n*, *n*) and increased to (*n* + 1, *n* + 1). So, the number *x* is written at (*n*, *n*). Then, we can block off the edge to the left of (*n* + 1, *n*) and above (*n*, *n* + 1). This will make the numbers in these two squares equal to *x*, so the number in square (*n* + 1, *n* + 1) would be 2*x*, as desired. To create *x* + 1 from *x*, we can increase both dimensions by 1, remove edges such that (*n* + 1, *n*) contains *x* while (*n*, *n* + 1) contains 1 (this requires deleting most of the edges joining the *n*-th column and (*n* + 1)-th column. Thus, the number in (*n*, *n*) would be *x* + 1. This would've used way too many edge deletions and the size of the grid would be too large. This was the original proposal. 1123 1124 There's another way to do it with binary representation. We construct a grid with difficulty 2*x* and 2*x* + 1 from a grid with difficulty *x*. The key idea is to make use of surrounding 1s and maintaining it with some walls so that 2*x* + 1 can be easily constructed. This method is shown in the picture below. This method would've used around 120 × 120 grid and 480 edge deletions, which is too large to pass. 1125 1126  1127 1128 Now, what follows is the AC solution. Since it's quite easy once you get the idea, I recommend you to try again after reading the hint. To read the full solution, click on the spoiler tag. 1129 1130 Hint : Binary can't work since there can be up to 60 binary digits for *t* and our grid size can be at most 50. In our binary solution we used a 2 × 2 grid to multiply the number of ways by 2. What about using other grid sizes instead? 1131 1132 **Full Solution** 1133 1134 Our AC solution uses base 6 instead of binary. Write *t* in base 6. Note that *t* has at most 24 digits in base 6, so to add a new digit we can increase the dimensions by 2 and the number of deleted edges can be up to 12 per digit. We'll construct such a way. This method is explained in the picture below. The key is to first construct a grid which has 0 in it, then find a way to get 6*x* + *i* for all 0 ≤ *i* ≤ 5 from *x* by maintaining a wall of 1s around the squares. This method uses a 50 × 50(2·24 + 2 = 50) grid and at most 24·12 + 2 = 290 edge deletions and will get AC. 1135 1136  1137 1138 Of course, this might not be the only way to solve this problem. Can you come up with other ways of solving this or reducing the constraints even further? (Open Question) 1139 1140 Time Complexity :  1141 1142 **Code** 1143 1144 ``` 1145 #include <bits/stdc++.h> 1146 #include <ext/pb_ds/assoc_container.hpp> 1147 #include <ext/pb_ds/tree_policy.hpp> 1148 1149 using namespace std; 1150 using namespace __gnu_pbds; 1151 1152 #define fi first 1153 #define se second 1154 #define mp make_pair 1155 #define pb push_back 1156 #define fbo find_by_order 1157 #define ook order_of_key 1158 1159 typedef long long ll; 1160 typedef pair<int,int> ii; 1161 typedef vector<int> vi; 1162 typedef long double ld; 1163 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 1164 typedef set<int>::iterator sit; 1165 typedef map<int,int>::iterator mit; 1166 typedef vector<int>::iterator vit; 1167 1168 const int INF = 1e9 + 7; 1169 const int MOD = 1e9 + 7; 1170 1171 typedef pair<ii,ii> move; 1172 1173 set<move> ans; 1174 int curx, cury; 1175 1176 bool isvalid(move x) 1177 { 1178 if(x.fi.fi > 0 && x.se.fi > 0 && x.fi.se > 0 && x.se.se > 0 && x.fi.fi <= curx && x.fi.se <= cury && x.se.fi <= curx && x.se.se <= cury) return true; 1179 return false; 1180 } 1181 1182 void edge(int x1, int y1, int x2, int y2) 1183 { 1184 ans.insert(mp(mp(x1, y1), mp(x2, y2))); 1185 } 1186 1187 void add(int bit) 1188 { 1189 int x = curx; 1190 edge(x,x+2,x,x+3); 1191 edge(x+1,x+2,x+1,x+3); 1192 edge(x+2,x,x+3,x); 1193 edge(x+2,x+1,x+3,x+1); 1194 edge(x-2,x+3,x-1,x+3); 1195 edge(x,x+4,x+1,x+4); 1196 edge(x+3,x-2,x+3,x-1); 1197 edge(x+4,x,x+4,x+1); 1198 edge(x-1,x+1,x,x+1); 1199 if(bit%3==0) edge(x-1,x+2,x,x+2); 1200 if(bit%3!=2) edge(x+2,x-1,x+2,x); 1201 if(bit<3) edge(x+1,x-1,x+1,x); 1202 curx += 2; cury += 2; 1203 } 1204 1205 int main() 1206 { 1207 ios_base::sync_with_stdio(0); cin.tie(0); 1208 ll t; cin >> t; 1209 vector<int> digits; 1210 while(t) 1211 { 1212 digits.pb(t%6); 1213 t/=6; 1214 } 1215 reverse(digits.begin(), digits.end()); 1216 edge(1, 2, 2, 2); 1217 edge(2, 1, 2, 2); 1218 curx = 2; cury = 2; 1219 for(int i = 0; i < digits.size(); i++) 1220 { 1221 add(digits[i]); 1222 } 1223 cout << curx << ' ' << cury << '\n'; 1224 vector<move> clr; 1225 for(set<move>::iterator it = ans.begin(); it != ans.end(); it++) 1226 { 1227 if(!isvalid(*it)) 1228 { 1229 clr.pb(*it); 1230 } 1231 } 1232 for(int i = 0; i < clr.size(); i++) 1233 { 1234 ans.erase(clr[i]); 1235 } 1236 cout << ans.size() << '\n'; 1237 for(set<move>::iterator it = ans.begin(); it != ans.end(); it++) 1238 { 1239 move tmp = (*it); 1240 cout << tmp.fi.fi << ' ' << tmp.fi.se << ' ' << tmp.se.fi << ' ' << tmp.se.se << '\n'; 1241 } 1242 } 1243 ``` 1244 1245 ## [Div. 1 E — Complete The Permutations](//codeforces.com/contest/715/problem/E) 1246 1247 Prerequisites : Math, Graph Theory, DP, Any fast multiplication algorithm 1248 1249 We'll slowly unwind the problem and reduce it to something easier to count. First, we need to determine a way to tell when the distance between *p* and *q* is exactly *k*. This is a classic problem but I'll include it here for completeness. 1250 1251 Let *f* denote the inverse permutation of *q*. So, the minimum number of swaps to transform *p* into *q* is the minimum number of swaps to transform *p**f**i* into the identity permutation. Construct the graph where the edges are  for all 1 ≤ *i* ≤ *n*. Now, note that the graph is equivalent to  and is composed of disjoint cycles after *q**i* and *p**i* are filled completely. Note that the direction of the edges doesn't matter so we consider the edges to be  for all 1 ≤ *i* ≤ *n*. Note that if the number of cycles of the graph is *t*, then the minimum number of swaps needed to transform *p* into *q* would be *n* - *t*. (Each swap can break one cycle into two) This means we just need to find the number of ways to fill in the empty spaces such that the number of cycles is exactly *i* for all 1 ≤ *i* ≤ *n*. 1252 1253 Now, some of the values *p**i* and *q**i* are known. The edges can be classified into four types : 1254 1255 A-type : The edges of the form , i.e. *p**i* is known, *q**i* isn't. 1256 1257 B-type : The edges of the form , i.e. *q**i* is known, *p**i* isn't. 1258 1259 C-type : The edges of the form , i.e. both *p**i* and *q**i* are known. 1260 1261 D-type : The edges of the form , i.e. both *p**i* and *q**i* are unknown. 1262 1263 Now, the problem reduces to finding the number of ways to assign values to the question marks such that the number of cycles of the graph is exactly *i* for all 1 ≤ *i* ≤ *n*. First, we'll simplify the graph slightly. While there exists a number *x* appears twice (clearly it can't appear more than twice) among the edges, we will combine the edges with *x* together to simplify the graph. If there's an edge , then we increment the total number of cycles by 1 and remove this edge from the graph. If there is an edge  and , where *a* and *b* might be some given numbers or question marks, then we can merge them together to form the edge . Clearly, these are the only cases for *x* to appear twice. Hence, after doing all the reductions, we're reduced to edges where each known number appears at most once, i.e. all the known numbers are distinct. We'll do this step in *O*(*n*2). For each number *x*, store the position *i* such that *p**i* = *x* and also the position *j* such that *q**j* = *x*, if it has already been given and - 1 otherwise. So, we need to remove a number when the *i* and *j* stored are both positive. We iterate through the numbers from 1 to *n*. If we need to remove a number, we go to the two positions where it occur and replace the two edges with the new merged one. Then, recompute the positions for all numbers (takes *O*(*n*) time). So, for each number, we used *O*(*n*) time. (to remove naively and update positions) Thus, the whole complexity for this part is *O*(*n*2). (It is possible to do it in *O*(*n*) with a simple dfs as well. Basically almost any correct way of doing this part that is at most *O*(*n*3) works, since the constraints for *n* is low) 1264 1265 Now, suppose there are *m* edges left and *p* known numbers remain. Note that in the end when we form the graph we might join edges of the form  and  (where *a* and *b* are either fixed numbers or question marks) together. So, the choice for the ? can be any of the *m* - *p* remaining unused numbers. Note that there will be always *m* - *p* such pairs so we need to multiply our answer by (*m* - *p*)! in the end. Also, note that the ? are distinguishable, and order is important when filling in the blanks. 1266 1267 So, we can actually reduce the problem to the following : Given integers *a*, *b*, *c*, *d* denoting the number of A-type, B-type, C-type, D-type edges respectively. Find the number of ways to create *k* cycles using them, for all 1 ≤ *k* ≤ *n*. Note that the answer is only dependent on the values of *a*, *b*, *c*, *d* as the numbers are all distinct after the reduction. 1268 1269 First, we'll look at how to solve the problem for *k* = 1. We need to fit all the edges in a single cycle. First, we investigate what happens when *d* = 0. Note that we cannot have a B-type and C-type edge before an A-type or C-type edge, since all numbers are distinct so these edges can't be joined together. Similarly, an A or C-type edge cannot be directly after a B or C-type edge. Thus, with these restrictions, it is easy to see that the cycle must contain either all A-type edges or B-type edges. So, the answer can be easily calculated. It is also important to note that if we ignore the cyclic property then a contiguous string of edges without D must be of the form AA...BB.. or AA...CBB..., where there is only one C, and zero or more As and Bs. 1270 1271 Now, if *d* ≥ 1, we can fix one of the D-type edges as the front of the cycle. This helps a lot because now we can ignore the cyclic properties. (we can place anything at the end of the cycle because D-type edges can connect with any type of edges) So, we just need to find the number of ways to make a length *n* - 1 string with *a* As, *b* Bs, *c* Cs and *d* - 1 Ds. In fact, we can ignore the fact that the A-type edges, B-type edges, C-type edges and D-type edges are distinguishable and after that multiply the answer by *a*!*b*!*c*!(*d* - 1)!. 1272 1273 We can easily find the number of valid strings we can make. First, place all the Ds. Now, we're trying to insert the As, Bs and Cs into the *d* empty spaces between, after and before the Ds. The key is that by our observation above, we only care about how many As, Bs and Cs we insert in each space since after that the way to put that in is uniquely determined. So, to place the As and Bs, we can use the balls in urns formula to find that the number of ways to place the As is  and the number of ways to place the Bs is . The number of ways to place the Cs is , since we choose where the Cs should go. 1274 1275 Thus, it turns out that we can find the answer in *O*(1) (with precomputing binomial coefficients and factorials) when *k* = 1. We'll use this to find the answer for all *k*. In the general case, there might be cycles that consists entirely of As and entirely of Bs, and those that contains at least one D. We call them the A-cycle, B-cycle and D-cycles respectively. 1276 1277 Now, we precompute *f*(*n*, *k*), the number of ways to form *k* cycles using *n* distinguishable As. This can be done with a simple dp in *O*(*n*3). We iterate through the number of As we're using for the first cycle. Then, suppose we use *m* As. The number of ways to choose which of the *m* As to use is  and we can permute them in (*m* - 1)! ways inside the cycle. (not *m*! because we have to account for all the cyclic permutations) Also, after summing this for all *m*, we have to divide the answer by *k*, to account for overcounting the candidates for the first cycle (the order of the *k* cycles are not important) 1278 1279 Thus, *f*(*n*, *k*) can be computed in *O*(*n*3). First, we see how to compute the answer for a single *k*. Fix *x*, *y*, *e*, *f*, the number of A-cycles, B-cycles, number of As in total among the A-cycles and number of Bs in total among the B-cycles. Then, since *k* is fixed, we know that the number of D-cycles is *k* - *x* - *y*. Now, we can find the answer in *O*(1). First, we can use the values of *f*(*e*, *x*), *f*(*f*, *y*), *f*(*d*, *k* - *x* - *y*) to determine the number of ways to place the Ds, and the As, Bs that are in the A-cycles and B-cycles. Then, to place the remaining As, Bs and Cs, we can use the same method as we did for *k* = 1 in *O*(1), since the number of spaces to place them is still the same. (You can think of it as each D leaves an empty space to place As, Bs and Cs to the right of it) After that, we multiply the answer by  to account for the choice of the set of As and Bs used in the A-only and B-only cycles. Thus, the complexity of this method is *O*(*n*4) for each *k* and *O*(*n*5) in total, which is clearly too slow. 1280 1281 We can improve this by iterating through all *x* + *y*, *e*, *f* instead. So, for this to work we need to precompute *f*(*e*, 0)*f*(*f*, *x* + *y*) + *f*(*e*, 1)*f*(*f*, *x* + *y* - 1) + ... + *f*(*e*, *x* + *y*)*f*(*f*, 0), which we can write as *g*(*x* + *y*, *e*, *f*). Naively doing this precomputation gives *O*(*n*4). Then, we can calculate the answer by iterating through all *x* + *y*, *e*, *f* and thus getting *O*(*n*3) per query and *O*(*n*4) for all *k*. This is still too slow to pass *n* = 250. 1282 1283 We should take a closer look of what we're actually calculating. Note that for a fixed pair *e*, *f*, the values of *g*(*x* + *y*, *e*, *f*) can be calculated for all possible *x* + *y* in  or *O*(*n*1.58) by using Number Theoretic Transform or Karatsuba's Algorithm respectively. (note that the modulus has been chosen for NFT to work) This is because if we fix *e*, *f*, then we're precisely finding the coefficients of the polynomial (*f*(*e*, 0)*x*0 + *f*(*e*, 1)*x*1 + ... + *f*(*e*, *n*)*x**n*)(*f*(*f*, 0)*x*0 + *f*(*f*, 1)*x*1 + ... + *f*(*f*, *n*)*x**n*), so this can be handled with NFT/Karatsuba. 1284 1285 Thus, the precomputation of *g*(*x* + *y*, *e*, *f*) can be done in  or *O*(*n*3.58). 1286 1287 Next, suppose we fixed *e* and *f*. We will calculate the answer for all possible *k* in  similar to how we calculated *g*(*x* + *y*, *e*, *f*). This time, we're multiplying the following two polynomials : *f*(*d*, 0)*x*0 + *f*(*d*, 1)*x*1 + ... + *f*(*d*, *n*)*x**n* and *g*(0, *e*, *f*)*x*0 + *g*(1, *e*, *f*)*x*1 + ... + *g*(*n*, *e*, *f*)*x**n*. Again, we can calculate this using any fast multiplication method, so the entire solution takes  or *O*(*n*3.58), depending on which algorithm is used to multiply polynomials. 1288 1289 Note that if you're using NFT/FFT, there is a small trick that can save some time. When we precompute the values of *g*(*x* + *y*, *e*, *f*), we don't need to do inverse FFT on the result and leave it in the FFTed form. After that, when we want to find the convolution of *f*(*d*, *i*) and *g*(*i*, *e*, *f*), we just need to apply FFT to the first polynomial and multiply them. This reduces the number of FFTs and it reduced my solution runtime by half. 1290 1291 Time Complexity :  or *O*(*n*3.58), depending on whether NFT or Karatsuba is used. 1292 1293 **Code (NFT)** 1294 1295 ``` 1296 #include <bits/stdc++.h> 1297 #include <ext/pb_ds/assoc_container.hpp> 1298 #include <ext/pb_ds/tree_policy.hpp> 1299 1300 using namespace std; 1301 using namespace __gnu_pbds; 1302 1303 #define fi first 1304 #define se second 1305 #define mp make_pair 1306 #define pb push_back 1307 #define fbo find_by_order 1308 #define ook order_of_key 1309 1310 typedef long long ll; 1311 typedef pair<int,int> ii; 1312 typedef vector<int> vi; 1313 typedef long double ld; 1314 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 1315 typedef set<int>::iterator sit; 1316 typedef map<int,int>::iterator mit; 1317 typedef vector<int>::iterator vit; 1318 1319 const int N = 251; 1320 const int MOD = 998244353; 1321 ll inv2; 1322 ll prt; 1323 ll iprt; 1324 1325 ll dpncr[N][N]; 1326 ll fact[N]; 1327 ll inverse[N]; 1328 ll g[N][N]; 1329 ll sumg[N][N][N]; 1330 1331 vector<ii> perm; 1332 int A, B, C, D; 1333 1334 ll modpow(ll a, ll b) 1335 { 1336 ll r = 1; 1337 while(b) 1338 { 1339 if(b&1) r = (r*a)%MOD; 1340 a = (a*a)%MOD; 1341 b>>=1; 1342 } 1343 return r; 1344 } 1345 1346 ll inv(ll a) 1347 { 1348 return modpow(a, MOD - 2); 1349 } 1350 1351 ll choose(int n, int m) 1352 { 1353 if(m < 0) return 0; 1354 if(n < m) return 0; 1355 if(m == 0) return 1; 1356 if(n == m) return 1; 1357 if(dpncr[n][m] != -1) return dpncr[n][m]; 1358 dpncr[n][m] = choose(n - 1, m - 1) + choose(n - 1, m); 1359 dpncr[n][m] += MOD; dpncr[n][m] %= MOD; 1360 return dpncr[n][m]; 1361 } 1362 1363 void computefact() 1364 { 1365 fact[0] = 1; 1366 for(ll i = 1; i < N; i++) 1367 { 1368 fact[i] = (fact[i - 1]*i)%MOD; 1369 } 1370 for(ll i = 1; i < N; i++) 1371 { 1372 inverse[i] = modpow(i, MOD - 2); 1373 } 1374 } 1375 1376 void print(vector<ii>& vec) 1377 { 1378 for(int i = 0; i < vec.size(); i++) 1379 { 1380 cout << vec[i].fi << ' ' << vec[i].se << endl; 1381 } 1382 cout << "------------------------------------------------" << endl; 1383 } 1384 1385 void printans(vector<ll>& vec) 1386 { 1387 for(int i = 0; i < vec.size(); i++) 1388 { 1389 cout << vec[i] << ' '; 1390 } 1391 cout << endl; 1392 } 1393 1394 void printansi(vector<int>& vec) 1395 { 1396 for(int i = 0; i < vec.size(); i++) 1397 { 1398 cout << vec[i] << ' '; 1399 } 1400 cout << endl; 1401 } 1402 1403 void calcpos(vector<ii>& pos) 1404 { 1405 pos.resize(perm.size()); 1406 for(int i = 0; i < perm.size(); i++) 1407 { 1408 pos[i] = ii(-1, -1); 1409 } 1410 for(int i = 1; i < perm.size(); i++) 1411 { 1412 if(perm[i].fi > 0) 1413 { 1414 pos[perm[i].fi].fi = i; 1415 } 1416 if(perm[i].se > 0) 1417 { 1418 pos[perm[i].se].se = i; 1419 } 1420 } 1421 } 1422 1423 int reduce() 1424 { 1425 int n = perm.size() - 1; 1426 vector<ii> pos; 1427 int cnt = 0; 1428 for(int i = 1; i <= n; i++) //Do a reduction 1429 { 1430 calcpos(pos); 1431 //print(pos); 1432 if(pos[i].fi > 0 && pos[i].se > 0) 1433 { 1434 if(pos[i].fi == pos[i].se) 1435 { 1436 cnt++; 1437 ii tmp1 = perm[pos[i].fi]; 1438 for(vector<ii>::iterator it = perm.begin(); it != perm.end(); it++) 1439 { 1440 if((*it) == tmp1) 1441 { 1442 perm.erase(it); break; 1443 } 1444 } 1445 continue; 1446 } 1447 int p1 = pos[i].se; int l = perm[p1].fi; ii tmp1 = perm[p1]; 1448 int p2 = pos[i].fi; int r = perm[p2].se; ii tmp2 = perm[p2]; 1449 for(vector<ii>::iterator it = perm.begin(); it != perm.end(); it++) 1450 { 1451 if((*it) == tmp1) 1452 { 1453 perm.erase(it); break; 1454 } 1455 } 1456 for(vector<ii>::iterator it = perm.begin(); it != perm.end(); it++) 1457 { 1458 if((*it) == tmp2) 1459 { 1460 perm.erase(it); break; 1461 } 1462 } 1463 perm.pb(ii(l, r)); 1464 } 1465 } 1466 //count A, B, C, D 1467 for(int i = 1; i < perm.size(); i++) 1468 { 1469 if(perm[i].fi > 0 && perm[i].se > 0) 1470 { 1471 assert(perm[i].fi != perm[i].se); 1472 C++; 1473 } 1474 else if(perm[i].fi > 0) 1475 { 1476 A++; 1477 } 1478 else if(perm[i].se > 0) 1479 { 1480 B++; 1481 } 1482 else 1483 { 1484 D++; 1485 } 1486 } 1487 return cnt; 1488 } 1489 1490 ll mult(ll a, ll b) 1491 { 1492 ll r = (a*b)%MOD; 1493 r = (r+MOD)%MOD; 1494 return r; 1495 } 1496 1497 ll add(ll a, ll b) 1498 { 1499 ll r = ((a+b)%MOD+MOD)%MOD; 1500 return r; 1501 } 1502 1503 ll F(ll a, ll b, ll c, ll d) 1504 { 1505 ll ans = 1; 1506 if(d == 0) 1507 { 1508 if(a == 0 && b == 0 && c == 0) return 1; 1509 else return 0; 1510 } 1511 ans = mult(ans, fact[a]); 1512 ans = mult(ans, fact[b]); 1513 ans = mult(ans, fact[c]); 1514 ans = mult(ans, choose(a+d-1, d-1)); 1515 ans = mult(ans, choose(b+d-1, d-1)); 1516 ans = mult(ans, choose(d, C)); 1517 return ans; 1518 } 1519 1520 const int LG = 9; 1521 const int root_pw = (1<<LG); 1522 void fft (vector<int> & a, bool invert) 1523 { 1524 int n = (int) a.size(); 1525 1526 for (int i=1, j=0; i<n; ++i) { 1527 int bit = n >> 1; 1528 for (; j>=bit; bit>>=1) 1529 j -= bit; 1530 j += bit; 1531 if (i < j) 1532 swap (a[i], a[j]); 1533 } 1534 1535 for (int len=2; len<=n; len<<=1) { 1536 int wlen = invert ? iprt : prt; 1537 for (int i=len; i<root_pw; i<<=1) 1538 wlen = int((wlen*1LL*wlen)%MOD); 1539 for (int i=0; i<n; i+=len) { 1540 int w = 1; 1541 for (int j=0; j<len/2; ++j) { 1542 int u = a[i+j]; int v = int((a[i+j+len/2]*1LL*w)%MOD); 1543 a[i+j] = u+v < MOD ? u+v : u+v-MOD; 1544 a[i+j+len/2] = u-v >= 0 ? u-v : u-v+MOD; 1545 w = int (w * 1LL * wlen % MOD); 1546 } 1547 } 1548 } 1549 if (invert) { 1550 ll nrev = inv(n); 1551 for (int i=0; i<n; ++i) 1552 a[i] = int((a[i]*1LL*nrev)%MOD); 1553 } 1554 } 1555 1556 void multiply(vector<int>& a, vector<int>& b, vector<int>& res) 1557 { 1558 vector<int> fa(a.begin(), a.end()), fb(b.begin(), b.end()); 1559 int n = 1; 1560 while(n < max(a.size(), b.size())) n <<= 1; 1561 fa.resize(n); fb.resize(n); 1562 //cerr << "A : "; printansi(fa); cerr << "B : "; printansi(fb); 1563 fft(fa, 0); fft(fb, 0); 1564 //cerr << "INVERT ONCE : "; 1565 //printans(fa); printans(fb); 1566 //fft(fa, 1); fft(fb, 1); cerr << "INVERT BACK A: "; printans(fa); cerr << "INVERT BACK B: "; printans(fb); 1567 res.resize(n); 1568 for(int i = 0; i < n; i++) res[i] = int((fa[i]*1LL*fb[i])%MOD); 1569 //printans(fa); 1570 fft(res, 1); 1571 //cerr << "CONVOLUTION : "; printansi(res); 1572 1573 } 1574 1575 void computeg(int n) 1576 { 1577 g[0][0] = 1; 1578 g[1][1] = 1; 1579 for(int i = 2; i <= n; i++) 1580 { 1581 for(int j = 1; j <= i; j++) 1582 { 1583 for(int k = 1; k <= i; k++) 1584 { 1585 g[i][j] = add(g[i][j], mult(g[i-k][j-1], mult(choose(i, k), fact[k-1]))); 1586 } 1587 //cerr << g[i][j] << '\n'; 1588 g[i][j] = mult(g[i][j], inverse[j]); 1589 //cerr << "G : " << i << ' ' << j << ' ' << g[i][j] << '\n'; 1590 } 1591 } 1592 for(int i = 0; i <= A; i++) 1593 { 1594 for(int j = 0; j <= B; j++) 1595 { 1596 vector<int> gi; vector<int> gj; 1597 gi.resize(n+1); gj.resize(n+1); 1598 for(int k = 0; k <= n; k++) 1599 { 1600 gi[k] = int(g[i][k]); 1601 gj[k] = int(g[j][k]); 1602 //cerr << gi[k] << ' ' << gj[k] << '\n'; 1603 } 1604 vector<int> res; 1605 multiply(gi, gj, res); 1606 for(int k = 0; k <= n; k++) 1607 { 1608 sumg[i][j][k] = res[k]; 1609 } 1610 } 1611 } 1612 } 1613 1614 int main() 1615 { 1616 ios_base::sync_with_stdio(0); cin.tie(0); 1617 int n; cin >> n; perm.resize(n+1); 1618 for(int i = 1; i <= n; i++) 1619 { 1620 cin >> perm[i].fi; 1621 } 1622 for(int i = 1; i <= n; i++) 1623 { 1624 cin >> perm[i].se; 1625 } 1626 ll tmpmult = 7*17; 1627 tmpmult = mult(tmpmult, modpow(2, 23 - LG)); 1628 prt = modpow(3, tmpmult); 1629 inv2 = inv(2); 1630 iprt = inv(prt); 1631 A = 0; B = 0; C = 0; D = 0; 1632 memset(dpncr, -1, sizeof(dpncr)); 1633 memset(sumg, 0, sizeof(sumg)); 1634 memset(g, 0, sizeof(g)); 1635 memset(fact, 0, sizeof(fact)); 1636 memset(inverse, 0, sizeof(inverse)); 1637 int cycles = reduce(); 1638 computefact(); 1639 computeg(n); 1640 //cerr << h(1, 0, 0) << endl; 1641 1642 vector<ll> ans; ans.assign(n+1, 0); 1643 1644 if(D - C < 0) 1645 { 1646 for(int i = 0; i < n; i++) 1647 { 1648 cout << ans[i] << ' '; 1649 } 1650 cout << endl; 1651 return 0; 1652 } 1653 1654 for(int i = 0; i <= A; i++) 1655 { 1656 for(int j = 0; j <= B; j++) 1657 { 1658 ll coef = 1; 1659 coef = mult(coef, F(A-i,B-j,C,D)); 1660 if(A > 0) coef = mult(coef, choose(A, i)); 1661 if(B > 0) coef = mult(coef, choose(B, j)); 1662 vector<int> gi; vector<int> gj; 1663 gi.resize(n+1); gj.resize(n+1); 1664 for(int k = 0; k <= n - cycles; k++) 1665 { 1666 gi[k] = int(g[D][k]); 1667 gj[k] = int(sumg[i][j][k]); 1668 } 1669 vector<int> res; 1670 multiply(gi, gj, res); 1671 //cout << gi.size() << ' ' << gj.size() << ' ' << res.size() << ' ' << ans.size() << ' ' << n << ' ' << cycles << '\n'; 1672 for(int k = 0; k <= n - cycles; k++) 1673 { 1674 int moves = n - (k + cycles); 1675 ans[moves] = add(ans[moves], mult(res[k], coef)); 1676 } 1677 } 1678 } 1679 1680 for(int i = 0; i < ans.size(); i++) 1681 { 1682 ans[i] = mult(ans[i], fact[D-C]); 1683 } 1684 1685 for(int i = 0; i < n; i++) 1686 { 1687 cout << ans[i] << ' '; 1688 } 1689 cout << endl; 1690 1691 return 0; 1692 } 1693 ``` 1694 1695 **Code (Karatsuba)** 1696 1697 ``` 1698 #include <bits/stdc++.h> 1699 #include <ext/pb_ds/assoc_container.hpp> 1700 #include <ext/pb_ds/tree_policy.hpp> 1701 1702 using namespace std; 1703 using namespace __gnu_pbds; 1704 1705 #define fi first 1706 #define se second 1707 #define mp make_pair 1708 #define pb push_back 1709 #define fbo find_by_order 1710 #define ook order_of_key 1711 1712 typedef long long ll; 1713 typedef pair<int,int> ii; 1714 typedef vector<int> vi; 1715 typedef long double ld; 1716 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 1717 typedef set<int>::iterator sit; 1718 typedef map<int,int>::iterator mit; 1719 typedef vector<int>::iterator vit; 1720 1721 const int N = 251; 1722 const int MOD = 998244353; 1723 ll inv2; 1724 ll prt; 1725 ll iprt; 1726 1727 ll dpncr[N][N]; 1728 ll fact[N]; 1729 ll inverse[N]; 1730 ll g[N][N]; 1731 ll sumg[N][N][N]; 1732 1733 vector<ii> perm; 1734 int A, B, C, D; 1735 1736 ll modpow(ll a, ll b) 1737 { 1738 ll r = 1; 1739 while(b) 1740 { 1741 if(b&1) r = (r*a)%MOD; 1742 a = (a*a)%MOD; 1743 b>>=1; 1744 } 1745 return r; 1746 } 1747 1748 ll inv(ll a) 1749 { 1750 return modpow(a, MOD - 2); 1751 } 1752 1753 ll choose(int n, int m) 1754 { 1755 if(m < 0) return 0; 1756 if(n < m) return 0; 1757 if(m == 0) return 1; 1758 if(n == m) return 1; 1759 if(dpncr[n][m] != -1) return dpncr[n][m]; 1760 dpncr[n][m] = choose(n - 1, m - 1) + choose(n - 1, m); 1761 dpncr[n][m] += MOD; dpncr[n][m] %= MOD; 1762 return dpncr[n][m]; 1763 } 1764 1765 void computefact() 1766 { 1767 fact[0] = 1; 1768 for(ll i = 1; i < N; i++) 1769 { 1770 fact[i] = (fact[i - 1]*i)%MOD; 1771 } 1772 for(ll i = 1; i < N; i++) 1773 { 1774 inverse[i] = modpow(i, MOD - 2); 1775 } 1776 } 1777 1778 void print(vector<ii>& vec) 1779 { 1780 for(int i = 0; i < vec.size(); i++) 1781 { 1782 cout << vec[i].fi << ' ' << vec[i].se << endl; 1783 } 1784 cout << "------------------------------------------------" << endl; 1785 } 1786 1787 void printans(vector<ll>& vec) 1788 { 1789 for(int i = 0; i < vec.size(); i++) 1790 { 1791 cout << vec[i] << ' '; 1792 } 1793 cout << endl; 1794 } 1795 1796 void printansi(vector<int>& vec) 1797 { 1798 for(int i = 0; i < vec.size(); i++) 1799 { 1800 cout << vec[i] << ' '; 1801 } 1802 cout << endl; 1803 } 1804 1805 void calcpos(vector<ii>& pos) 1806 { 1807 pos.resize(perm.size()); 1808 for(int i = 0; i < perm.size(); i++) 1809 { 1810 pos[i] = ii(-1, -1); 1811 } 1812 for(int i = 1; i < perm.size(); i++) 1813 { 1814 if(perm[i].fi > 0) 1815 { 1816 pos[perm[i].fi].fi = i; 1817 } 1818 if(perm[i].se > 0) 1819 { 1820 pos[perm[i].se].se = i; 1821 } 1822 } 1823 } 1824 1825 int reduce() 1826 { 1827 int n = perm.size() - 1; 1828 vector<ii> pos; 1829 int cnt = 0; 1830 for(int i = 1; i <= n; i++) //Do a reduction 1831 { 1832 calcpos(pos); 1833 //print(pos); 1834 if(pos[i].fi > 0 && pos[i].se > 0) 1835 { 1836 if(pos[i].fi == pos[i].se) 1837 { 1838 cnt++; 1839 ii tmp1 = perm[pos[i].fi]; 1840 for(vector<ii>::iterator it = perm.begin(); it != perm.end(); it++) 1841 { 1842 if((*it) == tmp1) 1843 { 1844 perm.erase(it); break; 1845 } 1846 } 1847 continue; 1848 } 1849 int p1 = pos[i].se; int l = perm[p1].fi; ii tmp1 = perm[p1]; 1850 int p2 = pos[i].fi; int r = perm[p2].se; ii tmp2 = perm[p2]; 1851 for(vector<ii>::iterator it = perm.begin(); it != perm.end(); it++) 1852 { 1853 if((*it) == tmp1) 1854 { 1855 perm.erase(it); break; 1856 } 1857 } 1858 for(vector<ii>::iterator it = perm.begin(); it != perm.end(); it++) 1859 { 1860 if((*it) == tmp2) 1861 { 1862 perm.erase(it); break; 1863 } 1864 } 1865 perm.pb(ii(l, r)); 1866 } 1867 } 1868 //count A, B, C, D 1869 for(int i = 1; i < perm.size(); i++) 1870 { 1871 if(perm[i].fi > 0 && perm[i].se > 0) 1872 { 1873 assert(perm[i].fi != perm[i].se); 1874 C++; 1875 } 1876 else if(perm[i].fi > 0) 1877 { 1878 A++; 1879 } 1880 else if(perm[i].se > 0) 1881 { 1882 B++; 1883 } 1884 else 1885 { 1886 D++; 1887 } 1888 } 1889 return cnt; 1890 } 1891 1892 ll mult(ll a, ll b) 1893 { 1894 ll r = (a*b)%MOD; 1895 r = (r+MOD)%MOD; 1896 return r; 1897 } 1898 1899 ll add(ll a, ll b) 1900 { 1901 ll r = ((a+b)%MOD+MOD)%MOD; 1902 return r; 1903 } 1904 1905 ll F(ll a, ll b, ll c, ll d) 1906 { 1907 ll ans = 1; 1908 if(d == 0) 1909 { 1910 if(a == 0 && b == 0 && c == 0) return 1; 1911 else return 0; 1912 } 1913 ans = mult(ans, fact[a]); 1914 ans = mult(ans, fact[b]); 1915 ans = mult(ans, fact[c]); 1916 ans = mult(ans, choose(a+d-1, d-1)); 1917 ans = mult(ans, choose(b+d-1, d-1)); 1918 ans = mult(ans, choose(d, C)); 1919 return ans; 1920 } 1921 1922 ll buffer[20001], bufferpos, siz = 1024; 1923 const int LG = 4; 1924 1925 void multiply(int size, ll a[], ll b[], ll r[]) 1926 { 1927 if(size <= (1<<LG)) 1928 { 1929 for(int i = 0; i < size*2; i++) r[i] = 0; 1930 for(int i = 0; i < size; i++) 1931 { 1932 if(a[i]) 1933 { 1934 for(int j = 0; j < size; j++) 1935 { 1936 r[i+j] += a[i]*b[j]; 1937 r[i+j] %= MOD; 1938 } 1939 } 1940 } 1941 for(int i = 0; i < size*2; i++) 1942 { 1943 r[i] %= MOD; 1944 } 1945 return ; 1946 } 1947 int s = size/2; 1948 multiply(s, a, b, r); 1949 multiply(s, a+s, b+s, r+size); 1950 ll *a2 = buffer+bufferpos; bufferpos += s; 1951 ll *b2 = buffer+bufferpos; bufferpos += s; 1952 ll *r2 = buffer+bufferpos; bufferpos += size; 1953 for(int i = 0; i < s; i++) 1954 { 1955 a2[i] = a[i] + a[i+s]; 1956 if(a2[i]>=MOD) a2[i]-=MOD; 1957 } 1958 for(int i = 0; i < s; i++) 1959 { 1960 b2[i] = b[i] + b[i+s]; 1961 if(b2[i]>=MOD) b2[i]-=MOD; 1962 } 1963 multiply(s, a2, b2, r2); 1964 for(int i = 0; i < size; i++) 1965 { 1966 r2[i] -= (r[i] + r[i+size]); 1967 } 1968 for(int i = 0; i < size; i++) 1969 { 1970 r[i+s] += r2[i]; 1971 r[i+s]%=MOD; 1972 if(r[i+s]<0) r[i+s]+=MOD; 1973 } 1974 bufferpos -= (s+s+size); 1975 } 1976 ll gi[N+5]; ll gj[N+5]; 1977 1978 void computeg(int n) 1979 { 1980 g[0][0] = 1; 1981 g[1][1] = 1; 1982 for(int i = 2; i <= n; i++) 1983 { 1984 for(int j = 1; j <= i; j++) 1985 { 1986 for(int k = 1; k <= i; k++) 1987 { 1988 g[i][j] = add(g[i][j], mult(g[i-k][j-1], mult(choose(i, k), fact[k-1]))); 1989 } 1990 g[i][j] = mult(g[i][j], inverse[j]); 1991 } 1992 } 1993 for(int i = 0; i <= A; i++) 1994 { 1995 for(int j = 0; j <= B; j++) 1996 { 1997 siz = 512; 1998 while(siz/2 >= n+1) siz>>=1; 1999 for(int k = 0; k < siz; k++) 2000 { 2001 if(k <= n) 2002 { 2003 gi[k] = g[i][k]; 2004 gj[k] = g[j][k]; 2005 } 2006 else 2007 { 2008 gi[k] = gj[k] = 0; 2009 } 2010 } 2011 ll *res = buffer+bufferpos; 2012 bufferpos+=2*siz; 2013 multiply(siz,gi,gj,res); 2014 for(int k = 0; k <= n; k++) 2015 { 2016 sumg[i][j][k] = res[k]; 2017 } 2018 bufferpos-=2*siz; 2019 } 2020 } 2021 } 2022 2023 int main() 2024 { 2025 ios_base::sync_with_stdio(0); cin.tie(0); 2026 int n; cin >> n; perm.resize(n+1); 2027 2028 for(int i = 1; i <= n; i++) 2029 { 2030 cin >> perm[i].fi; 2031 } 2032 for(int i = 1; i <= n; i++) 2033 { 2034 cin >> perm[i].se; 2035 } 2036 2037 A = 0; B = 0; C = 0; D = 0; 2038 memset(dpncr, -1, sizeof(dpncr)); 2039 memset(sumg, 0, sizeof(sumg)); 2040 memset(g, 0, sizeof(g)); 2041 memset(fact, 0, sizeof(fact)); 2042 memset(inverse, 0, sizeof(inverse)); 2043 int cycles = reduce(); 2044 computefact(); computeg(n); 2045 vector<ll> ans; ans.assign(n+1, 0); 2046 2047 if(D - C < 0) 2048 { 2049 for(int i = 0; i < n; i++) 2050 { 2051 cout << ans[i] << ' '; 2052 } 2053 cout << endl; 2054 return 0; 2055 } 2056 2057 for(int i = 0; i <= A; i++) 2058 { 2059 for(int j = 0; j <= B; j++) 2060 { 2061 ll coef = 1; 2062 coef = mult(coef, F(A-i,B-j,C,D)); 2063 if(A > 0) coef = mult(coef, choose(A, i)); 2064 if(B > 0) coef = mult(coef, choose(B, j)); 2065 siz = 512; 2066 while(siz/2 >= n-cycles+1) siz>>=1; 2067 for(int k = 0; k < siz; k++) 2068 { 2069 if(k <= n-cycles) 2070 { 2071 gi[k] = g[D][k]; 2072 gj[k] = sumg[i][j][k]; 2073 } 2074 else 2075 { 2076 gi[k] = gj[k] = 0; 2077 } 2078 } 2079 ll *res = buffer+bufferpos; 2080 bufferpos+=2*siz; 2081 multiply(siz,gi,gj,res); 2082 for(int k = 0; k <= n - cycles; k++) 2083 { 2084 int moves = n - (k + cycles); 2085 ans[moves] = add(ans[moves], mult(res[k], coef)); 2086 } 2087 bufferpos-=2*siz; 2088 } 2089 } 2090 2091 for(int i = 0; i < ans.size(); i++) 2092 { 2093 ans[i] = mult(ans[i], fact[D-C]); 2094 } 2095 2096 for(int i = 0; i < n; i++) 2097 { 2098 cout << ans[i] << ' '; 2099 } 2100 cout << endl; 2101 } 2102 ```