codeforces-scrape

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

715.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 ![](https://espresso.codeforces.com/8e6ec1e2db9ed1f6fd98a65e6b6f5afce0693bff.png) and ![](https://espresso.codeforces.com/5f7cb1f5b241d5849e8e76852e8b537165d6ee67.png) 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 ![](https://espresso.codeforces.com/209e897bbb72eaf16c1d0f0d1ea6f8a71fce7c91.png) 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 ![](https://espresso.codeforces.com/6e707458ef451bdd26ea9340220802449e08c822.png). 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 ![](https://espresso.codeforces.com/9ae7c484246f5aeae7aefe7bbf09ddd5183d89bc.png) solution.
    444 
    445 Time Complexity : ![](https://espresso.codeforces.com/c1f6890e5a70950ad29a832cac990d15868160d6.png) or ![](https://espresso.codeforces.com/9ae7c484246f5aeae7aefe7bbf09ddd5183d89bc.png)
    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 ![](https://espresso.codeforces.com/fa46c78ff9ecabee5b4e74c357a3aee84f6f4f54.png). To find the multiplicative inverse of 10, we can find φ(*M*) and since by Euler's Formula we have *x*φ(*M*) ≡ 1(*modM*) if ![](https://espresso.codeforces.com/1d805d57e24f2b4a658fb0a65b5c7b7a2880e4f8.png), 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 ![](https://espresso.codeforces.com/2c9c3df11f894e8708ec95c4ac3b289ad20b7926.png) 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 ![](https://espresso.codeforces.com/dd3c3020535d184dd41ce6bab8067764bbca68ec.png) time, where the other ![](https://espresso.codeforces.com/e534f2da678188382079d5eae762e91981566186.png) comes from using maps.
    871 
    872 Time Complexity : ![](https://espresso.codeforces.com/dd3c3020535d184dd41ce6bab8067764bbca68ec.png)
    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 ![ ](/predownloaded/f3/75/f37543a2bbe33f89ce1ece33fe165aa1d786eba1.png)
   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 ![ ](/predownloaded/39/65/396500eab5871bd133e7458731b59b246875daef.png)
   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 : ![](https://espresso.codeforces.com/ab3b3f6b765f090d7e70ae57b09067207a3d0abc.png)
   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 ![](https://espresso.codeforces.com/88e62754c17feac71e167d078aac1a9128d842a7.png) for all 1 ≤ *i* ≤ *n*. Now, note that the graph is equivalent to ![](https://espresso.codeforces.com/f38cc2729bd6e478563412ec35b4c147f3a06e70.png) 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 ![](https://espresso.codeforces.com/6a4259ed308f6c2f570e4e5aa0cb5d7e80c40895.png) 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 ![](https://espresso.codeforces.com/f5bcc55d05c5a4e7650ba525588fcaf2ebde6999.png), i.e. *p**i* is known, *q**i* isn't.
   1256 
   1257 B-type : The edges of the form ![](https://espresso.codeforces.com/88fa7940962b9ad84659d6e7daba94615978f3f8.png), i.e. *q**i* is known, *p**i* isn't.
   1258 
   1259 C-type : The edges of the form ![](https://espresso.codeforces.com/5db0c99c4b5417cdf766ba5c0e0fd0c3daecc89f.png), i.e. both *p**i* and *q**i* are known.
   1260 
   1261 D-type : The edges of the form ![](https://espresso.codeforces.com/c0e0a1031cf67793a68c8eb7c961897828e7e2dd.png), 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 ![](https://espresso.codeforces.com/99882250622f22ede7bc6eb68c5880dbe474a6cf.png), then we increment the total number of cycles by 1 and remove this edge from the graph. If there is an edge ![](https://espresso.codeforces.com/31438df142b114e2ddac3274ccd339daf7e4e43a.png) and ![](https://espresso.codeforces.com/604b07d26931345cc494929a6f0574f22fb83e1e.png), where *a* and *b* might be some given numbers or question marks, then we can merge them together to form the edge ![](https://espresso.codeforces.com/a6fb1c4b6c53481175e27cd77b2c49e794ca9037.png). 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 ![](https://espresso.codeforces.com/9a0980122c2b0a102f0ec6b88483d028af0c83dc.png) and ![](https://espresso.codeforces.com/30b1688e0c420f9d2141c0c447cf53326dd36718.png) (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 ![](https://espresso.codeforces.com/964e7418f804307891d4a87fc15677a1e1228b3b.png) and the number of ways to place the Bs is ![](https://espresso.codeforces.com/2301843bc56d043f23dd0dac80d7c5df4efe9c6f.png). The number of ways to place the Cs is ![](https://espresso.codeforces.com/dd8b4026b85f5702dbb2f0169b40f0eeebd4e260.png), 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 ![](https://espresso.codeforces.com/1f3f1de97dc88be14acb9a19c9263b11497c8cb3.png) 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 ![](https://espresso.codeforces.com/a1cf01050703ca82e0369757f50fb17c529942fb.png) 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 ![](https://espresso.codeforces.com/06b2dfff448a3a9e0e9b5c879f5cda0ce1cecba5.png) 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 ![](https://espresso.codeforces.com/9e4fb3a5483ce6dc1e59bab311734a7a64cf32a8.png) or *O*(*n*3.58).
   1286 
   1287 Next, suppose we fixed *e* and *f*. We will calculate the answer for all possible *k* in ![](https://espresso.codeforces.com/06b2dfff448a3a9e0e9b5c879f5cda0ce1cecba5.png) 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 ![](https://espresso.codeforces.com/9e4fb3a5483ce6dc1e59bab311734a7a64cf32a8.png) 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 : ![](https://espresso.codeforces.com/9e4fb3a5483ce6dc1e59bab311734a7a64cf32a8.png) 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 ```