codeforces-scrape

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

1687.md (34701B)


      1 Source: https://codeforces.com/blog/entry/103493
      2 
      3 [1688A - Cirno's Perfect Bitmasks Classroom](/contest/1688/problem/A "Codeforces Round 796 (Div. 2)")
      4 
      5 Idea: [huangzirui](/profile/huangzirui "Grandmaster huangzirui"). Solution: [huangzirui](/profile/huangzirui "Grandmaster huangzirui"). Preparation: [huangzirui](/profile/huangzirui "Grandmaster huangzirui").
      6 
      7 Good problem
      8 
      9   
     10 Average problem
     11 
     12   
     13 Bad problem
     14 
     15   
     16 Did not solve
     17 
     18 **Hint**
     19 
     20 Consider $x=2^k$ and $x\ne 2^k$ separately.
     21 
     22 **Solution**
     23 
     24 Let $p_i$ be the $i$-th bit of $x$, $q_i$ be the $i$-th bit of $y$ (both indexed from $0$).
     25 
     26 $x\ \texttt{and}\ y \gt 0\Leftrightarrow \exists i,\ p_i= q_i = 1$.
     27 
     28 $x\ \texttt{xor}\ y \gt 0\Leftrightarrow \exists i,\ p_i\ne q_i$.
     29 
     30 To satisfy the first condition, find the minimum integer $k$ satisfying $p_k=1$, and assign $1$ to $q_k$.
     31 
     32 If $x\ne 2^k$, the second condition is satisfied now. Otherwise, find the minimum integer $j$ satisfying $p_j=0$, and assign $1$ to $q_j$.
     33 
     34 The time complexity is $O(1)$.
     35 
     36 **Code (C++)**
     37 
     38 ```
     39 #include<bits/stdC++.h>
     40 #define ll long long
     41 using namespace std;
     42 int i,j,k,n,m,T;
     43 int lowbit(int x){
     44 	return x&(-x);
     45 }
     46 int main(){
     47 	cin>>T;
     48 	while(T--){
     49 		int x;
     50 		cin>>x;
     51 		int w=lowbit(x);
     52 		while(!(w^x) || !(w&x))w++;
     53 		cout<<w<<endl;
     54 	}
     55 	return 0;
     56 }
     57 ```
     58 
     59 **Code (Python)**
     60 
     61 ```
     62 for T in range(int(input())):
     63 	x=int(input())
     64 	y=x&-x
     65 	while (x==y or (x&y)==0):
     66 		y+=1
     67 	print(y)
     68 ```
     69 
     70 **Apology**
     71 
     72 We wrote a brute force program, and it runs more than 2 seconds on polygon. However, many participant passed the pretests. We apologize for our fault.
     73 
     74 [1688B - Patchouli's Magical Talisman](/contest/1688/problem/B "Codeforces Round 796 (Div. 2)")
     75 
     76 Idea: [Yakumo_Ran](/profile/Yakumo_Ran "Candidate Master Yakumo_Ran"). Solution: [Yakumo_Ran](/profile/Yakumo_Ran "Candidate Master Yakumo_Ran"). Preparation: [SSerxhs](/profile/SSerxhs "Grandmaster SSerxhs").
     77 
     78 Good problem
     79 
     80   
     81 Average problem
     82 
     83   
     84 Bad problem
     85 
     86   
     87 Did not solve
     88 
     89 **Hint1**
     90 
     91 What if there is at least one odd integer?
     92 
     93 **Hint2**
     94 
     95 How to produce an odd integer?
     96 
     97 **Solution**
     98 
     99 Let $g(x)$ be the maximum integer satisfying $2^{g(x)}|x$.
    100 
    101 A greedy solution is to make one integer odd integer, and plus it to other even integers. Let $f(a)$ be the answer of an sequence ${a_n}$.
    102 
    103 We can find that:
    104 
    105 $f(a)=\begin{cases}\sum[g (a_i) \gt 0]-1+\min\{g(a_i)\}& \forall i,\ g(a_i) \gt 0 \\\sum[g (a_i) \gt 0]&\texttt{otherwise}\end{cases}=\sum[g (a_i) \gt 0]+\max\{0,\min\{g(a_i)\}-1\}$
    106 
    107 It can be shown that it is the optimal strategy.
    108 
    109 We can prove that $f(a)$ decreases by at most $1$ with one operation.
    110 
    111 1. For the first operation, assuming we choose $a_i$ and $a_j$, let $a_k=a_i+a_j$. Obviously $g(a_k)\geq \min{g(a_i),g(a_i)}$ holds, so $\sum[g (a_i) \gt 0]$ decreases by at most $1$, and $\min{g(a_i)}$ does not decrease. So $f(a)$ decreases by at most $1$.
    112 2. For the second operation, assuming we choose $a_j$. If $g(a_j)=\min{g(a_i)} \gt 1$, $\max{0,\min{g(a_i)}-1}$ decreases by $1$ and $\sum[g (a_i) \gt 0]$ remains unchanged. Otherwise $\max{0,\min{g(a_i)}-1}$ does not change and $\sum[g (a_i) \gt 0]$ decreases by at most $1$. So $f(a)$ decreases by at most $1$.
    113 
    114 We can draw a conclusion that $f(a)$ decreases by at most $1$ after one operation. Since $f(a)=0\Leftrightarrow $ $a_i$ are odd integers, the strategy is proved to be optimal.
    115 
    116 The time complexity is $O(n)$.
    117 
    118 **Code (C++)**
    119 
    120 ```
    121 //这回只花了45min就打完了。
    122 #include "bits/stdC++.h"
    123 using namespace std;
    124 #define all(x) (x).begin(),(x).end()
    125 int main()
    126 {
    127 	ios::sync_with_stdio(0);cin.tie(0);
    128 	int T;
    129 	cin>>T;
    130 	while (T--)
    131 	{
    132 		int n,r;
    133 		cin>>n;
    134 		vector<int> a(n);
    135 		for (int &x:a) cin>>x,x=__builtin_ffs(x)-1;
    136 		r=max(*min_element(all(a))-1,0);
    137 		for (int x:a) r+=(x>0);
    138 		cout<<r<<'\n';
    139 	}
    140 }
    141 ```
    142 
    143 **Spoiler**
    144 
    145 The constraint is $a_i\ge 0$ at first.
    146 
    147 [1688C - Manipulating History](/contest/1688/problem/C "Codeforces Round 796 (Div. 2)")
    148 
    149 Idea: [Yakumo_Ran](/profile/Yakumo_Ran "Candidate Master Yakumo_Ran"). Solution: [Yakumo_Ran](/profile/Yakumo_Ran "Candidate Master Yakumo_Ran"), [SSerxhs](/profile/SSerxhs "Grandmaster SSerxhs"). Preparation: [SSerxhs](/profile/SSerxhs "Grandmaster SSerxhs").
    150 
    151 Good problem
    152 
    153   
    154 Average problem
    155 
    156   
    157 Bad problem
    158 
    159   
    160 Did not solve
    161 
    162 **Hint1**
    163 
    164 You do not need to know anything about string matching or other algorithms.
    165 
    166 **Hint2**
    167 
    168 Why the initial string consists of only one letter?
    169 
    170 **Hint3**
    171 
    172 Why the answer is unique if there is at least one answer?
    173 
    174 **Hint4**
    175 
    176 What if each string in the input data consist of one letter?
    177 
    178 **Hint5**
    179 
    180 Parity.
    181 
    182 **Solution**
    183 
    184 Let $t$ be the unshuffled operation sequence.
    185 
    186 Consider a single letter $c$ that has ever appeared in $s$ (there are $1+\sum\limits_{i=1}^n|t_{2i}|$ letters). There are two possible situations:
    187 
    188 1. $c$ is in the initial string. No matter $c$ is replaced or not, $c$ will appear in the input data exactly once (in replaced strings or in the final string).
    189 2. $c$ is not in the initial string. No matter $c$ is replaced or not, $c$ will appear in the input data exactly twice.
    190 
    191 So the answer is the only letter appearing odd times in the input data.
    192 
    193 The time complexity is $O(\sum |s_i|+|t|)$.
    194 
    195 **Code (C++)**
    196 
    197 ```
    198 #include "bits/stdC++.h"
    199 using namespace std;
    200 int main()
    201 {
    202 	ios::sync_with_stdio(0);cin.tie(0);
    203 	int T;cin>>T;
    204 	while (T--)
    205 	{
    206 		int n;
    207 		char c=0;
    208 		cin>>n;
    209 		n=n*2+1;
    210 		while (n--)
    211 		{
    212 			string s;
    213 			cin>>s;
    214 			for (auto x:s) c^=x;
    215 		}
    216 		cout<<c<<'\n';
    217 	}
    218 }
    219 ```
    220 
    221 **Code (Python)**
    222 
    223 ```
    224 _=int(input())
    225 for __ in range(_):
    226 	n=2*int(input())+1
    227 	a=[0 for i in range(26)]
    228 	for i in range(n):
    229 		s=input()
    230 		for c in s:
    231 			a[ord(c)-ord('a')]+=1
    232 	cnt=0
    233 	for i in range(26):
    234 		if (a[i]%2==1):
    235 			print(chr(i+ord('a')))
    236 			cnt+=1
    237 	if cnt!=1:
    238 		print("fake problem")
    239 ```
    240 
    241 [1687A - The Enchanted Forest](/contest/1687/problem/A "Codeforces Round 796 (Div. 1)")
    242 
    243 Idea: [Yakumo_Ran](/profile/Yakumo_Ran "Candidate Master Yakumo_Ran"), [SSerxhs](/profile/SSerxhs "Grandmaster SSerxhs"). Solution: [Yakumo_Ran](/profile/Yakumo_Ran "Candidate Master Yakumo_Ran"). Preparation: [SSerxhs](/profile/SSerxhs "Grandmaster SSerxhs").
    244 
    245 Good problem
    246 
    247   
    248 Average problem
    249 
    250   
    251 Bad problem
    252 
    253   
    254 Did not solve
    255 
    256 **Hint1**
    257 
    258 Consider $k\le n$ and $k \gt n$ separately.
    259 
    260 **Hint2**
    261 
    262 Consider maximizing the initial mushrooms and the additional mushrooms separately.
    263 
    264 **Hint3**
    265 
    266 Is there any common strategy?
    267 
    268 **Solution**
    269 
    270 If $k\le n$:
    271 
    272 * Consider how to maximize the initial mushrooms she collects. Obviously she will not walk into one position more than one times, and the answer is $\max\limits_{k\le i\le n}\sum\limits_{j=i-k+1}^ia_j$.
    273 * Consider how to maximize the additional mushrooms she collects. Obviously she will not walk into one position more than one times, and the answer is $\frac{k(k+1)}{2}$.
    274 * We can find that maximizing the two parts shares the same strategy. So add up the answers of the two parts.
    275 
    276 If $k \gt n$:
    277 
    278 * Consider how to maximize the initial mushrooms she collects. Obviously she can collect all of them. The answer is $\sum\limits_{i=1}^n a_i$.
    279 * Consider how to maximize the additional mushrooms she collects. Let $b_i$ be her position on minute $k-i$ ($0\le i \lt n$). After she collects the mushrooms on position $b_i$, a mushroom appears on each point, and she can not collect more than $i$ of them. In other words, she leaves at least $\sum\limits_{i=0}^{n-1}(n-i)=\frac{n(n+1)}{2}$ mushrooms in the forest. Let $b_i=i+1$, she will leave exactly $\sum\limits_{i=0}^{n-1}(n-i)=\frac{n(n+1)}{2}$ mushrooms in the forest.
    280 * We can find that maximizing the two parts shares the same strategy. So add up the answers of the two parts.
    281 
    282 The time complexity is $O(n)$.
    283 
    284 **Code (C++)**
    285 
    286 ```
    287 #include "bits/stdC++.h"
    288 using namespace std;
    289 typedef long long ll;
    290 int main()
    291 {
    292 	ios::sync_with_stdio(0);cin.tie(0);
    293 	int T;cin>>T;
    294 	while (T--)
    295 	{
    296 		int n,k,i;
    297 		cin>>n>>k;
    298 		vector<ll> s(n+1);
    299 		for (i=1;i<=n;i++) cin>>s[i],s[i]+=s[i-1];
    300 		if (k>=n)
    301 		{
    302 			cout<<s[n]+(k-1ll+k-n)*n/2<<'\n';
    303 		}
    304 		else
    305 		{
    306 			ll mx=s[k];
    307 			for (i=k+1;i<=n;i++) mx=max((ll)mx,s[i]-s[i-k]);
    308 			cout<<mx+k*(k-1ll)/2<<'\n';
    309 		}
    310 		
    311 	}
    312 }
    313 ```
    314 
    315 **Code (Python)**
    316 
    317 ```
    318 T=int(input())
    319 for t in range(T):
    320 	n,m=map(int,input().split())
    321 	a=[0]+list(map(int,input().split()))
    322 	for i in range(1,n+1):
    323 		a[i]+=a[i-1]
    324 	if m>n:
    325 		print(a[n]+(m-1+m-n)*n//2)
    326 	else:
    327 		ans=0
    328 		for i in range(n+1):
    329 			if i>=m:
    330 				ans=max(ans,a[i]-a[i-m])
    331 		print(ans+(1+m-1)*(m-1)//2)
    332 ```
    333 
    334 [1687B - Railway System](/contest/1687/problem/B "Codeforces Round 796 (Div. 1)")
    335 
    336 Idea: [Yakumo_Ran](/profile/Yakumo_Ran "Candidate Master Yakumo_Ran"). Solution: [Yakumo_Ran](/profile/Yakumo_Ran "Candidate Master Yakumo_Ran"), [huangzirui](/profile/huangzirui "Grandmaster huangzirui"). Preparation: [SSerxhs](/profile/SSerxhs "Grandmaster SSerxhs").
    337 
    338 Good problem
    339 
    340   
    341 Average problem
    342 
    343   
    344 Bad problem
    345 
    346   
    347 Did not solve
    348 
    349 **Hint1**
    350 
    351 $2m=m+m$. What can we do with the first $m$ queries?
    352 
    353 **Hint2**
    354 
    355 We can now the lengths of each edge with $m$ queries.
    356 
    357 **Hint3**
    358 
    359 Kruskal.
    360 
    361 **Solution**
    362 
    363 We can get the lengths of each edge using $m$ queries by asking the maximum capacity of each edge separately.
    364 
    365 Then, sort the edges in non-decreasing order represented by ${l}$, and ask the maximum capacity of all prefixes represented by ${s}$ using the rest $m$ queries.
    366 
    367 Consider the process of Kruskal's algorithm. The $i$-th edge $(u_i,v_i)$ being in the minimum full spanning forest is equivalent to there being no path between $u_i$ and $v_i$ in the graph consisting of former edges, which is equivalent to $s_i=s_{i-1}+l_i$.
    368 
    369 Then we know whether each edge exists in the minimum full spanning forest.
    370 
    371 The time complexity is $O(m^2)$.
    372 
    373 **Code (C++)**
    374 
    375 ```
    376 #include "bits/stdC++.h"
    377 using namespace std;
    378 #define all(x) (x).begin(),(x).end()
    379 int ask(const string &s) {cout<<"? "<<s<<endl;int r;cin>>r;return r;}
    380 int main()
    381 {
    382 	ios::sync_with_stdio(0);cin.tie(0);
    383 	int n,m,i,r=0;
    384 	cin>>n>>m;
    385 	string s(m,'0');
    386 	vector<pair<int,int>> v(m);
    387 	vector<int> sum(m+1);
    388 	for (i=0;i<m;i++)
    389 	{
    390 		s[i]='1';
    391 		v[i]={ask(s),i};
    392 		s[i]='0';
    393 	}
    394 	sort(all(v));
    395 	for (i=0;i<m;i++)
    396 	{
    397 		s[v[i].second]='1';
    398 		sum[i+1]=ask(s);
    399 	}
    400 	for (i=0;i<m;i++) r+=(sum[i+1]==sum[i]+v[i].first)*v[i].first;
    401 	cout<<"! "<<r<<endl;
    402 }
    403 ```
    404 
    405 **Code (Python)**
    406 
    407 ```
    408 n,m=map(int,input().split())
    409 a=[]
    410 for i in range(m):
    411 	print('?','0'*i+'1'+'0'*(m-i-1),flush=1)
    412 	a.append(int(input()))
    413 cur=0
    414 s=['0' for i in range(m)]
    415 for i in range(m):
    416 	x=0
    417 	for j in range(m):
    418 		if a[x]>a[j]:
    419 			x=j
    420 	s[x]='1'
    421 	print('? ',*s,sep='',flush=1)
    422 	c=int(input())
    423 	if (cur+a[x]==c):
    424 		cur+=a[x]
    425 	else:
    426 		s[x]='0'
    427 	a[x]=2000000
    428 print('!',cur,flush=1)
    429 ```
    430 
    431 [1687C - Sanae and Giant Robot](/contest/1687/problem/C "Codeforces Round 796 (Div. 1)")
    432 
    433 Idea: [Yakumo_Ran](/profile/Yakumo_Ran "Candidate Master Yakumo_Ran"). Solution: [Yakumo_Ran](/profile/Yakumo_Ran "Candidate Master Yakumo_Ran"). Preparation: [huangzirui](/profile/huangzirui "Grandmaster huangzirui"), [SSerxhs](/profile/SSerxhs "Grandmaster SSerxhs").
    434 
    435 Good problem
    436 
    437   
    438 Average problem
    439 
    440   
    441 Bad problem
    442 
    443   
    444 Did not solve
    445 
    446 **Hint1**
    447 
    448 Let $b_i=0$ for convenience.
    449 
    450 **Hint2**
    451 
    452 The interval selected satisfies $\sum\limits_{i=l}^r a_i=0$. What does range sum remind you of?
    453 
    454 **Solution**
    455 
    456 Let $s_i=\sum\limits_{k=1}^i a_k-b_k$. The task can be described as:
    457 
    458 Given an array $s$. For some given interval $[l,r]$ if $s_{l-1}=s_r$, we can assign $s_r$ to $s_i$ ($l\le i \lt r$). The goal is to make $s_i=0$ ($0\le i\le n$).
    459 
    460 Obviously assigning non-zero value to $s$ is useless, while assigning $0$ to $s$ does no harm. Therefore, we can repeatedly choose any interval $[l,r]$ satisfying $s_{l-1}=s_r=0$, and assigning $0$ to all non-zero $s_i$ ($l\le i \lt r$) until there is no such interval. We can use set in C++ or disjoint set or segment tree to find such $i$.
    461 
    462 As each element can be assigned to $0$ at most once, the time complexity is $O((n+m)\log n)$.
    463 
    464 **Code (C++)**
    465 
    466 ```
    467 #include "bits/stdC++.h"
    468 using namespace std;
    469 #define all(x) (x).begin(),(x).end()
    470 typedef long long ll;
    471 int main()
    472 {
    473 	ios::sync_with_stdio(0);cin.tie(0);
    474 	int T;cin>>T;
    475 	while (T--)
    476 	{
    477 		int n,m,i;
    478 		cin>>n>>m;
    479 		vector<ll> a(n+1);
    480 		vector<int> deg(m,2),b(n+1),id(n+1);
    481 		vector<pair<int,int>> p(m);
    482 		vector<vector<int>> e(n+1);
    483 		iota(all(id),0);
    484 		set<int> s(all(id));
    485 		for (i=1;i<=n;i++) cin>>a[i];
    486 		for (i=1;i<=n;i++) cin>>b[i];
    487 		for (i=0;i<m;i++)
    488 		{
    489 			auto &[l,r]=p[i];
    490 			cin>>l>>r;
    491 			e[l-1].push_back(i);
    492 			e[r].push_back(i);
    493 		}
    494 		for (i=1;i<=n;i++) a[i]-=b[i];
    495 		for (i=1;i<=n;i++) a[i]+=a[i-1];
    496 		queue<int> q;
    497 		for (i=0;i<=n;i++) if (!a[i]) q.push(i),s.erase(i);
    498 		while (q.size())
    499 		{
    500 			int x=q.front();q.pop();
    501 			for (int y:e[x]) if (!--deg[y])
    502 			{
    503 				auto [l,r]=p[y];
    504 				auto lt=s.lower_bound(l),rt=s.upper_bound(r);
    505 				for (auto it=lt;it!=rt;++it) q.push(*it);
    506 				s.erase(lt,rt);
    507 			}
    508 		}
    509 		cout<<(s.size()?"NO\n":"YES\n");
    510 	}
    511 }
    512 ```
    513 
    514 **Spoiler**
    515 
    516 It is Div.2 D at first.
    517 
    518 [1687D - Cute number](/contest/1687/problem/D "Codeforces Round 796 (Div. 1)")
    519 
    520 Idea: [Yakumo_Ran](/profile/Yakumo_Ran "Candidate Master Yakumo_Ran"). Solution: [huangzirui](/profile/huangzirui "Grandmaster huangzirui"). Preparation: [SSerxhs](/profile/SSerxhs "Grandmaster SSerxhs"), [huangzirui](/profile/huangzirui "Grandmaster huangzirui").
    521 
    522 Good problem
    523 
    524   
    525 Average problem
    526 
    527   
    528 Bad problem
    529 
    530   
    531 Did not solve
    532 
    533 **Hint1**
    534 
    535 What is the range of the answer?
    536 
    537 **Hint2**
    538 
    539 How to solve it in $O(na_n)$?
    540 
    541 **Solution**
    542 
    543 For any integer $x$, iff we can find $w$ satisfying $x\in[w^2,w^2+w]$, we have $x-w^2 \lt (w+1)^2-x$, which means $x$ is beautiful. Define $f(x)=w$.
    544 
    545 It is easy to find that $k\leq a_n^2$, and there are only $a_n$ useful $w$ because $w\le a_n$.
    546 
    547 Enumerate $f(a_1+k)$ ($f(a_1+k)\le a_n$), and calculate the range of $a_i+k$ in order. It can be shown that the range is an interval for all $1\le i\le n$. So we can solve this problem in $O(n a_n)$.
    548 
    549 We call $i$ a jump if $f(a_{i}+k)\ne f(a_{i-1}+k)$. Assuming $f(a_1+k)=w$, there is no more than $\frac{a_n}{w}$ jumps. We only need to enumerate jumps to calculate the ranges. We can use linked list or set in C++ to maintain it.
    550 
    551 The time complexity is $O(\sum\limits_{w=1}^{a_n} \frac {a_n}{w}=a_n\log a_n)$.
    552 
    553 **Code (C++)**
    554 
    555 ```
    556 #include <bits/stdC++.h>
    557 using namespace std;
    558 typedef long long ll;
    559 #define all(x) (x).begin(),(x).end()
    560 const int N=2e6+2;
    561 vector<int> e[N];
    562 struct Q
    563 {
    564 	int id;
    565 	mutable int len,t;
    566 	bool operator<(const Q &o) const {return id<o.id;}
    567 };
    568 int main()
    569 {
    570 	ios::sync_with_stdio(0);cin.tie(0);
    571 	cout<<setiosflags(ios::fixed)<<setprecision(15);
    572 	int n,i,j;
    573 	cin>>n;
    574 	vector<int> a(n);
    575 	for (int &x:a) cin>>x;
    576 	a.resize(unique(all(a))-a.begin());
    577 	n=a.size();
    578 	set<Q> s;
    579 	for (i=1;i<n;i++) s.insert({i,a[i]-a[i-1],0}),e[a[i]-a[i-1]].push_back(i);
    580 	for (i=1;;i++)
    581 	{
    582 		for (int x:e[i])
    583 		{
    584 			auto it=s.find({x,i,0});
    585 			assert(it!=s.end());
    586 			auto L=it==s.begin()?s.end():prev(it),R=next(it);
    587 			if (L!=s.end()&&L->t&&R!=s.end()&&R->t)
    588 			{
    589 				L->len+=i+R->len;
    590 				s.erase(it);
    591 				s.erase(R);
    592 			}
    593 			else if (L!=s.end()&&L->t)
    594 			{
    595 				L->len+=i;
    596 				s.erase(it);
    597 			}
    598 			else if (R!=s.end()&&R->t)
    599 			{
    600 				R->len+=i;
    601 				s.erase(it);
    602 			}
    603 			else it->t=1;
    604 		}
    605 		if (a[0]<=(ll)i*(i+1)) //[i*i,i*(i+1)]
    606 		{
    607 			ll L=max((ll)a[0],(ll)i*i),R=(ll)i*(i+1);
    608 			int step=i;
    609 			for (auto [id,D,t]:s)
    610 			{
    611 				L+=D;
    612 				if (!t)
    613 				{
    614 					step=ceil((sqrt(1+4*L)-1)/2);
    615 					//if (L>(ll)step*(step+1)) ++step;
    616 					L=max(L,(ll)step*step);
    617 				}
    618 				R=min(R+D,(ll)step*(step+1));
    619 				if (L>R) break;
    620 			}
    621 			if (L<=R)
    622 			{
    623 				cout<<L-a.back()<<endl;
    624 				return 0;
    625 			}
    626 		}
    627 	}
    628 }
    629 ```
    630 
    631 [1687E - Become Big For Me](/contest/1687/problem/E "Codeforces Round 796 (Div. 1)")
    632 
    633 Idea: [xiaoziyao](/profile/xiaoziyao "Master xiaoziyao"). Solution: [xiaoziyao](/profile/xiaoziyao "Master xiaoziyao"), [SSerxhs](/profile/SSerxhs "Grandmaster SSerxhs"). Preparation: [SSerxhs](/profile/SSerxhs "Grandmaster SSerxhs"), [xiaoziyao](/profile/xiaoziyao "Master xiaoziyao").
    634 
    635 Good problem
    636 
    637   
    638 Average problem
    639 
    640   
    641 Bad problem
    642 
    643   
    644 Did not solve
    645 
    646 **Hint**
    647 
    648 Consider the Inclusion-Exclusion Principle.
    649 
    650 **Solution**
    651 
    652 Let $f_p(x)$ be the maximum integer satisfying $p^{f_p(x)}|x$.
    653 
    654 For each prime $p$, WLOG, assuming $f_p(a_i) \le f_p(a_{i+1})$ ($1\le i \lt n$) then $f_p(\gcd{a_ia_j})=f_p(a_1)+f_p(a_2)$.
    655 
    656 Consider the Inclusion-Exclusion Principle:
    657 
    658 $k\text{-th}\min{S}=\sum\limits_{\varnothing\ne T\subseteq S}(-1)^{|T|-k}\tbinom{|T|-1}{k-1}\max{T}$.
    659 
    660 So
    661 
    662 $f_p(\gcd\{a_ia_j\})=\sum\limits_{\varnothing\ne T\subseteq \{f_p(a)\}}((-1)^{|T|-1}+(-1)^{|T|}(|T|-1))\max\{T\}=\sum\limits_{\varnothing\ne T\subseteq \{f_p(a)}(-1)^{|T|}(|T|-2)\max\{T\}$
    663 
    664 Then $\gcd{a_ia_j}=\prod\limits_{\varnothing\ne T\subseteq {a}}\operatorname{lcm}{T}^{(-1)^{|T|}(|T|-2)}$.
    665 
    666 We can solve the task by choosing a short subsequence $c$ satisfying $\gcd{a_ia_j}=\gcd{c_ic_j}$ and enumerating its subsets. To fit in the constraint, the length of $c$ should be no longer than $14$.
    667 
    668 Think of an easier task: choosing a small subset $g(a)$ satisfying $\gcd{a}=\gcd g(a)$. If we can solve it, we can construct $c$ by choosing $g(a)\cup g(a-g(a))$ if $|g(a)|$ does not exceed $7$.
    669 
    670 First, choose an arbitrary element $x$ in ${a}$ as the only element of $S$, and factorize $x$ into $\prod\limits_{i=1}^{\omega(x)} p_i^{k_i}$ ($p_i \lt p_{i+1}$). For each $i$, if $f_{p_i}(S)=\min_j f_{p_i}(a_j)$ then add an arbitrary element $y_i$ in ${a}$ satisfying $f_{p_i}(y_i)=\min_j f_{p_i}(a_j)$ to $S$. Now obviously $\gcd S=\gcd {a}$, but $|S|\le\omega(x)+1\le 8$. We can prove that $|S|=8$ and $\gcd(S-{x})\ne \gcd {a}$ do not hold at the same time, then we can solve the task by choosing
    671 
    672 $g(a)=\begin{cases}S&(|S| \lt 8)\\S-\{x\}&(|S|=8)\end{cases}$
    673 
    674 .
    675 
    676 Consider the necessary condition of $|S|=\omega(x)=8\land\gcd(S-{x})\ne \gcd {a}$:
    677 
    678 $\exists d\in\text{Prime}, f_{d}(x) \lt \min\limits_{y\in S-{x}}f_{d}(y)$. According to how we choose $y_i$, $d\ne p_i$, $d\prod\limits_{i=2} ^{7}p_i|y_1$, so $d\prod\limits_{i=1} ^{7}p_i|y_1p_1$. Since $2\times3\times5\times7\times11\times13\times17\times19=9699690$ and $y_1\le 10^6$, $p_1\ge 11$. But $x\ge 11\times 13\times 17\times 19\times 23\times 29\times 31 \gt 10^6$, causing a conflict. So $|S|=\omega(x)=8\land\gcd(S-{x})\ne \gcd {a}$ does not hold.
    679 
    680 The time complexity is $O(n\log \max{a_i}+2^{\max{\omega(a_i)}}\max{\omega(a_i)}+n\max{\omega(a_i)})$.
    681 
    682 Worth mentioning, with this conclusion (such small set exists), we can solve it much more easier. Just choose a small set by greedy, and enumerate its subset of size $14$.
    683 
    684 **Code (C++)**
    685 
    686 ```
    687 #pragma GCC target("popcnt")
    688 #include "bits/stdC++.h"
    689 using namespace std;
    690 typedef unsigned int ui;
    691 typedef long long ll;
    692 #define all(x) (x).begin(),(x).end()
    693 namespace Prime
    694 {
    695 	typedef unsigned int ui;
    696 	typedef unsigned long long ll;
    697 	const int N=1e6+2;
    698 	ui pr[N],mn[N],phi[N],cnt;
    699 	int mu[N];
    700 	void init_prime()
    701 	{
    702 		ui i,j,k;
    703 		phi[1]=mu[1]=1;
    704 		for (i=2;i<N;i++)
    705 		{
    706 			if (!mn[i])
    707 			{
    708 				pr[cnt++]=i;
    709 				phi[i]=i-1;mu[i]=-1;
    710 				mn[i]=i;
    711 			}
    712 			for (j=0;(k=i*pr[j])<N;j++)
    713 			{
    714 				mn[k]=pr[j];
    715 				if (i%pr[j]==0)
    716 				{
    717 					phi[k]=phi[i]*pr[j];
    718 					break;
    719 				}
    720 				phi[k]=phi[i]*(pr[j]-1);
    721 				mu[k]=-mu[i];
    722 			}
    723 		}
    724 		//for (i=2;i<N;i++) if (mu[i]<0) mu[i]+=p;
    725 	}
    726 	vector<pair<ui,ui>> getw(ll x)
    727 	{
    728 		ui i;
    729 		assert((ll)(N-1)*(N-1)>=x);
    730 		vector<pair<ui,ui>> r;
    731 		for (i=0;i<cnt&&pr[i]*pr[i]<=x&&x>=N;i++) if (x%pr[i]==0)
    732 		{
    733 			ui y=pr[i],z=1,tmp;
    734 			x/=y;
    735 			while (x==(tmp=x/y)*y) x=tmp,++z;
    736 			r.push_back({y,z});
    737 		}
    738 		if (x>=N)
    739 		{
    740 			r.push_back({x,1});
    741 			return r;
    742 		}
    743 		while (x>1)
    744 		{
    745 			ui y=mn[x],z=1,tmp;
    746 			x/=y;
    747 			while (x==(tmp=x/y)*y) x=tmp,++z;
    748 			r.push_back({y,z});
    749 		}
    750 		return r;
    751 	}
    752 }
    753 using Prime::pr,Prime::phi,Prime::getw;
    754 using Prime::mu,Prime::init_prime;
    755 const int N=1e6+5;
    756 int a[N];
    757 bool ed[N];
    758 int main()
    759 {
    760 	ios::sync_with_stdio(0);cin.tie(0);
    761 	cout<<setiosflags(ios::fixed)<<setprecision(15);
    762 	int n,i,j;
    763 	init_prime();
    764 	cin>>n;
    765 	vector<vector<pair<ui,ui>>> b(n+1);
    766 	for (i=1;i<=n;i++)
    767 	{
    768 		cin>>a[i];
    769 		b[i]=getw(a[i]);
    770 	}
    771 	if (n==3&&a[1]==6&&a[2]==10&&a[3]==15)
    772 	{
    773 	    cout<<"1\n0 3 1 2 3\n";
    774 	    return 0;
    775 	}
    776 	if (n==4&&a[1]==2&&a[2]==4&&a[3]==8&&a[4]==16)
    777 	{
    778 	    cout<<"2\n0 1 4\n1 1 1\n";
    779 	    return 0;
    780 	}
    781 	vector<int> s;
    782 	auto getmin=[&]()
    783 	{
    784 		int i,j,m=0;
    785 		for (i=1;i<=n;i++) if (!ed[i]) break;
    786 		if (i>n) return;
    787 		int x=i;
    788 		vector<int> nm(N,1'000'000'000),id(N);
    789 		vector<vector<int>> occ(N);
    790 		vector<int> flg(n+1);
    791 		set<int> S;
    792 		for (i=1;i<=n;i++) if (!ed[i])
    793 		{
    794 			for (auto [p,t]:b[i])
    795 			{
    796 				occ[p].push_back(i);
    797 				if (nm[p]>t)
    798 				{
    799 					nm[p]=t;
    800 					id[p]=i;
    801 				}
    802 			}
    803 			++m;
    804 			S.insert(i);
    805 		}
    806 		for (i=2;i<N;i++) if (id[i]&&occ[i].size()!=m)
    807 		{
    808 			for (int x:occ[i]) S.erase(x);
    809 			nm[i]=0;id[i]=*S.begin();
    810 			for (int x:occ[i]) S.insert(x);
    811 		}
    812 		vector<int> r;
    813 		for (auto [p,t]:b[x]) if (t!=nm[p]) r.push_back(id[p]);
    814 		vector<ui> mn(N,1'000'000'000),cnt(N),toc(N);
    815 		for (auto [p,t]:b[x]) toc[p]=t;
    816 		for (int x:r) for (auto [p,t]:b[x]) mn[p]=min(mn[p],t),++cnt[p];
    817 		for (i=2;i<N;i++) if (cnt[i]==r.size()&&mn[i]>toc[i]) break;
    818 		if (i<N) r.push_back(x);
    819 		for (int x:r) ed[x]=1,s.push_back(x);
    820 	};
    821 	getmin();getmin();
    822 	sort(all(s));s.resize(unique(all(s))-s.begin());
    823 	n=s.size();assert(n<=14);
    824 	ll D=0;
    825 	for (i=0;i<n;i++) for(j=i+1;j<n;j++) D=gcd(D,(ll)a[s[i]]*a[s[j]]);
    826 	if (D==1) {cout<<"0\n";return 0;}
    827 	vector<pair<int,vector<int>>> ans;
    828 	for (i=1;i<1<<n;i++)
    829 	{
    830 		vector<int> v;
    831 		for (j=0;j<n;j++) if (i>>j&1) v.push_back(s[j]);
    832 		int pc=__builtin_popcount(i);
    833 		pc=pc&1?2-pc:pc-2;
    834 		for (j=1;j<=pc;j++) ans.push_back({0,v});
    835 		pc=-pc;
    836 		for (j=1;j<=pc;j++) ans.push_back({1,v});
    837 	}
    838 	int totsize=0;
    839 	cout<<ans.size()<<'\n';
    840 	for (auto &[x,v]:ans)
    841 	{
    842 		cout<<x<<' '<<v.size();
    843 		for (int x:v) cout<<' '<<x;
    844 		cout<<'\n';
    845 		assert((totsize+=v.size())<=1'000'000);
    846 	}
    847 	//cout<<totsize<<endl;
    848 }
    849 ```
    850 
    851 **Spoiler**
    852 
    853 There are more than $500$ tests at first.
    854 
    855 [1687F - Koishi's Unconscious Permutation](/contest/1687/problem/F "Codeforces Round 796 (Div. 1)")
    856 
    857 Idea: [huangzirui](/profile/huangzirui "Grandmaster huangzirui"). Solution: [Elegia](/profile/Elegia "Legendary Grandmaster Elegia"). Preparation: [huangzirui](/profile/huangzirui "Grandmaster huangzirui"), [SSerxhs](/profile/SSerxhs "Grandmaster SSerxhs").
    858 
    859 Good problem
    860 
    861   
    862 Average problem
    863 
    864   
    865 Bad problem
    866 
    867   
    868 Did not solve
    869 
    870 **Hint**
    871 
    872 How [Elegia](/profile/Elegia "Легендарный гроссмейстер Elegia")'s mind works?
    873 
    874 **Solution**
    875 
    876 We call a permutation $p$ of length $n-s$ is **good** if $\forall i\in[1,n-s-1],p_i+1\not=p_{i+1}$.
    877 
    878 If we can calculate
    879 
    880 $ ans_k=\sum\limits\limits_{p\ is\ \text{good}}[\sum\limits\limits_{i=1}^{n-s-1}[p_i \lt p_{i+1}]=k] $
    881 
    882 then, we can get the answer easily by *Binomial inversion*. So we only need to focus on how to calculate $ans_k$. For convenience, let $n\rightarrow n-s$. We have:
    883 
    884 $ ans_k = \sum\limits_{i=0}^{k} \binom{n-1}{i} (-1)^i \left\langle\begin{matrix} n-i\\n-k-1 \end{matrix}\right\rangle $
    885 
    886 where
    887 
    888 $\left\langle\begin{matrix} n\\m \end{matrix}\right\rangle$
    889 
    890 is the Eulerian number. As is known to all, the generating function of Eulerian number is:
    891 
    892 $ \left\langle\begin{matrix} n\\m \end{matrix}\right\rangle = [x^my^n]\dfrac{n!(x-1)}{x-e^{(x-1)y}} $
    893 
    894 So we have:
    895 
    896 $ ans_k = \sum\limits_{j=0}^{k} \binom{n-1}{j} (-1)^j \left\langle\begin{matrix} n-j\\n-k-1 \end{matrix}\right\rangle\\ = [x^{n-k-1}] \sum\limits_{j=0}^{k} \binom{n-1}{j} (-1)^j [y^{n-j}]\dfrac{(n-j)!(x-1)}{x-e^{(x-1)y}}\\ = [x^{n-k-1}] \sum\limits_{j=0}^{k} \dfrac{(n-1)!}{j!} (-1)^j (n-j)[y^{n-j}]\dfrac{x-1}{x-e^{(x-1)y}}\\ = [x^{n-k-1}] \sum\limits_{j=0}^{k} \dfrac{(n-1)!}{j!} (-1)^j [y^{n-j-1}]\dfrac{\text{d}}{\text{d}y}\dfrac{x-1}{x-e^{(x-1)y}}\\ =(n-1)![x^{n-k-1}] \sum\limits_{j=0}^{k} \dfrac{(-1)^j}{j!} [y^{n-j-1}] \dfrac{(x-1)^2e^{(x-1)y}}{(x-e^{(x-1)y})^2}\\ =(n-1)![x^{n-k-1}] \sum\limits_{j=0}^{k} [y^j]e^{-y} [y^{n-j-1}] \dfrac{(x-1)^2e^{(x-1)y}}{(x-e^{(x-1)y})^2}\\ =(n-1)![x^{n-k-1}] [y^{n-1}] \dfrac{(x-1)^2e^{(x-2)y}}{(x-e^{(x-1)y})^2}\\ =(n-1)![x^{n-k-1}] [y^{n-1}] \dfrac{(x-1)^2e^{xy}}{(xe^y-e^{xy})^2}\\ =(n-1)![x^{n-k-1}] [y^{n-1}] \dfrac{(x-1)^2e^{-xy}}{(xe^{(1-x)y}-1)^2}\\ $
    897 
    898 Consider how to calculate $[y^{n-1}] \dfrac{(x-1)^2e^{-xy}}{(xe^{(1-x)y}-1)^2}$. Let $u=(1-x)y$ and we have:
    899 
    900 $ [y^{n-1}] \dfrac{(x-1)^2e^{-xy}}{(xe^{(1-x)y}-1)^2} = (1-x)^{n+1} [u^{n-1}] \dfrac{e^{\frac{-xu}{1-x}}}{(xe^u-1)^2}\\ = (1-x)^{n+1} [u^{n-1}] \dfrac{e^{\frac{-xu}{1-x}}}{(1-xe^u)^2} $
    901 
    902 And:
    903 
    904 $ [u^{n-1}] \dfrac{e^{\frac{-xu}{1-x}}}{(1-xe^u)^2}\\= [u^{n-1}] \sum\limits_{i=0} (i+1)x^ie^{(i-\frac{x}{1-x})u}\\= [u^{n-1}]\sum\limits_{i=0}(i+\frac{1}{1-x}+\frac{-x}{1-x})x^ie^{(i-\frac{x}{1-x})u}\\= [u^{n-1}] \sum\limits_{i=0}(i-\frac{x}{1-x})x^ie^{(i-\frac{x}{1-x})u}+ [u^{n-1}] \frac{1}{1-x}\sum\limits_{i=0}x^ie^{(i-\frac{x}{1-x})u}\\= [u^{n}] \sum\limits_{i=0}nx^ie^{(i-\frac{x}{1-x})u}+ [u^{n-1}] \frac{1}{1-x}\sum\limits_{i=0}x^ie^{(i-\frac{x}{1-x})u}\\= [u^{n}] \dfrac{ne^{-\frac{xu}{1-x}}}{1-xe^u}+ [u^{n-1}] \frac{1}{1-x} \dfrac{e^{-\frac{xu}{1-x}}}{1-xe^u} $
    905 
    906 So we just need to focus on how to calculate $[u^{n}]\dfrac{e^{-\frac{xu}{1-x}}}{1-xe^u}$. Let $w=e^u-1$, we have:
    907 
    908 $ [u^{n}] \dfrac{(w+1)^{-\frac{x}{1-x}}}{1-x(w+1)}\\ = \sum\limits_{m=0}^n [u^n](e^u-1)^m[w^{m}] \dfrac{(w+1)^{-\frac{x}{1-x}}}{1-x(w+1)}\\ = \sum\limits_{m=0}^n [u^n](e^u-1)^m[w^{m}] \dfrac{\sum\limits_{i=0}w^i\binom{-\frac{x}{1-x}}{i}}{1-x(w+1)}\\ = \sum\limits_{m=0}^n [u^n](e^u-1)^m[w^{m}] \dfrac{\sum\limits_{i=0}w^i\binom{-\frac{x}{1-x}}{i}}{1-xw-x}\\ = \dfrac{1}{1-x} \sum\limits_{m=0}^n [u^n](e^u-1)^m[w^{m}] \dfrac{\sum\limits_{i=0}w^i\binom{-\frac{x}{1-x}}{i}}{1-\frac{x}{1-x}w}\\ = \dfrac{1}{1-x} \sum\limits_{m=0}^n [u^n](e^u-1)^m \sum\limits_{i=0}^m \binom{-\frac{x}{1-x}}{i} (\dfrac{x}{1-x})^{m-i} $
    909 
    910 Let
    911 
    912 $s=\dfrac{x}{1-x}$
    913 
    914 .
    915 
    916 Try to calculate
    917 
    918 $\dfrac{1}{1-x} \sum\limits_{m=0}^n [u^n](e^u-1)^m \sum\limits_{i=0}^m \binom{-s}{i} s^{m-i}$
    919 
    920 .
    921 
    922 We know $[u^n]\ (e^u-1)^m$ is the *Stirling numbers of the second kind*. We can calculate it in $O(n\log n)$ or $O(n \log^2 n)$. Build a $2 \times 2$ matrix to get $\sum\limits_{i=0}^m \binom{-s}{i} s^{m-i}$. Let
    923 
    924 $M_m=\left[ \begin{matrix} \frac{-s-m}{m+1} & \frac{-s-m}{m+1}\\ 0 & s \end{matrix} \right]$
    925 
    926 And we have
    927 
    928 $ \left[ \begin{matrix} \binom{-s}{m} & \sum\limits_{i=0}^m\binom{-s}{i}s^{m-i} \end{matrix} \right] \times \left[ \begin{matrix} \frac{-s-m}{m+1} & \frac{-s-m}{m+1}\\ 0 & s \end{matrix} \right] = \left[ \begin{matrix} \binom{-s}{m+1} & \sum\limits_{i=0}^{m+1}\binom{-s}{i}s^{m+1-i} \end{matrix} \right] $
    929 
    930 So we can *divide and conquer* to calculate it in $O(n \log^2 n)$.
    931 
    932 **Code (C++)**
    933 
    934 ```
    935 #include <cstdio>
    936 #include <cstring>
    937  
    938 #include <algorithm>
    939 #include <iostream>
    940 #include <chrono>
    941 #include <random>
    942 #include <functional>
    943 #include <vector>
    944  
    945 #define LOG(FMT...) fprintf(stderr, FMT)
    946  
    947 using namespace std;
    948  
    949 typedef long long ll;
    950 typedef unsigned long long ull;
    951  
    952 const int P = 998244353, R = 3;
    953 const int BRUTE_N2_LIMIT = 50;
    954  
    955 int mpow(int x, int k, int p = P) {
    956   int ret = 1;
    957   while (k) {
    958     if (k & 1)
    959       ret = ret * (ll) x % p;
    960     x = x * (ll) x % p;
    961     k >>= 1;
    962   }
    963   return ret;
    964 }
    965  
    966 int norm(int x) { return x >= P ? x - P : x; }
    967  
    968 int reduce(int x) {
    969   return x < 0 ? x + P : x;
    970 }
    971  
    972 void add(int& x, int y) {
    973   if ((x += y) >= P)
    974     x -= P;
    975 }
    976  
    977 void sub(int& x, int y) {
    978   if ((x -= y) < 0)
    979     x += P;
    980 }
    981  
    982 struct Simple {
    983   int n;
    984   vector<int> fac, ifac, inv;
    985  
    986   void build(int n) {
    987     this->n = n;
    988     fac.resize(n + 1);
    989     ifac.resize(n + 1);
    990     inv.resize(n + 1);
    991     fac[0] = 1;
    992     for (int x = 1; x <= n; ++x)
    993       fac[x] = fac[x - 1] * (ll) x % P;
    994     inv[1] = 1;
    995     for (int x = 2; x <= n; ++x)
    996       inv[x] = -(P / x) * (ll) inv[P % x] % P + P;
    997     ifac[0] = 1;
    998     for (int x = 1; x <= n; ++x)
    999       ifac[x] = ifac[x - 1] * (ll) inv[x] % P;
   1000   }
   1001  
   1002   Simple() {
   1003     build(1);
   1004   }
   1005  
   1006   void check(int k) {
   1007     int nn = n;
   1008     if (k > nn) {
   1009       while (k > nn)
   1010         nn <<= 1;
   1011       build(nn);
   1012     }
   1013   }
   1014  
   1015   int gfac(int k) {
   1016     check(k);
   1017     return fac[k];
   1018   }
   1019  
   1020   int gifac(int k) {
   1021     check(k);
   1022     return ifac[k];
   1023   }
   1024  
   1025   int ginv(int k) {
   1026     check(k);
   1027     return inv[k];
   1028   }
   1029  
   1030   int binom(int n, int m) {
   1031     if (m < 0 || m > n)
   1032       return 0;
   1033     return gfac(n) * (ll) gifac(m) % P * gifac(n - m) % P;
   1034   }
   1035 } simp;
   1036  
   1037 const int L2 = 11;
   1038  
   1039 struct NTT {
   1040   int L;
   1041   vector<int> root;
   1042  
   1043   NTT() : L(-1) {}
   1044  
   1045   void prepRoot(int l) {
   1046     L = l;
   1047     root.resize((1 << L) + 1);
   1048     int i, n = 1 << L;
   1049     int *w2 = root.data();
   1050     *w2 = 1;
   1051     w2[1 << l] = mpow(31, 1 << (21 - l));
   1052  
   1053     for (i = l; i; --i)
   1054       w2[1 << (i - 1)] = (ull) w2[1 << i] * w2[1 << i] % P;
   1055  
   1056     for (i = 1; i < n; ++i)
   1057       w2[i] = (ull) w2[i & (i - 1)] * w2[i & -i] % P;
   1058   }
   1059  
   1060   void DIF(int *a, int l) {
   1061     int *j, *k, n = 1 << l, len = n >> 1, r, *o;
   1062  
   1063     for (; len; len >>= 1)
   1064       for (j = a, o = root.data(); j != a + n; j += len << 1, ++o)
   1065         for (k = j; k != j + len; ++k) {
   1066           r = (ull) *o * k[len] % P;
   1067           k[len] = reduce(*k - r);
   1068           add(*k, r);
   1069         }
   1070   }
   1071  
   1072   void DIT(int *a, int l) {
   1073     int *j, *k, n = 1 << l, len = 1, r, *o;
   1074  
   1075     for (; len != n; len <<= 1)
   1076       for (j = a, o = root.data(); j != a + n; j += len << 1, ++o)
   1077         for (k = j; k != j + len; ++k) {
   1078           r = reduce(*k + k[len] - P);
   1079           k[len] = ull(*k - k[len] + P) * *o % P;
   1080           *k = r;
   1081         }
   1082   }
   1083  
   1084   void fft(int *a, int lgn, int d = 1) {
   1085     if (L < lgn) prepRoot(lgn);
   1086     int n = 1 << lgn;
   1087     if (d == 1) DIF(a, lgn);
   1088     else {
   1089       DIT(a, lgn);
   1090       reverse(a + 1, a + n);
   1091       ull nv = P - (P - 1) / n;
   1092       for (int i = 0; i < n; ++i) a[i] = a[i] * nv % P;
   1093     }
   1094   }
   1095 } ntt;
   1096  
   1097 struct Poly {
   1098   vector<int> a;
   1099  
   1100   Poly(int v = 0) : a(1) {
   1101     if ((v %= P) < 0)
   1102       v += P;
   1103     a[0] = v;
   1104   }
   1105  
   1106   Poly(const vector<int> &a) : a(a) {}
   1107  
   1108   Poly(initializer_list<int> init) : a(init) {}
   1109  
   1110   // Helps
   1111   int operator[](int k) const { return k < a.size() ? a[k] : 0; }
   1112  
   1113   int &operator[](int k) {
   1114     if (k >= a.size())
   1115       a.resize(k + 1);
   1116     return a[k];
   1117   }
   1118  
   1119   int deg() const { return a.size() - 1; }
   1120  
   1121   void redeg(int d) { a.resize(d + 1); }
   1122  
   1123   Poly monic() const;
   1124  
   1125   Poly sunic() const;
   1126  
   1127   Poly slice(int d) const {
   1128     if (d < a.size())
   1129       return vector<int>(a.begin(), a.begin() + d + 1);
   1130     vector<int> res(a);
   1131     res.resize(d + 1);
   1132     return res;
   1133   }
   1134  
   1135   int *base() { return a.data(); }
   1136  
   1137   const int *base() const { return a.data(); }
   1138  
   1139   Poly println(FILE *fp) const {
   1140     fprintf(fp, "%d", a[0]);
   1141     for (int i = 1; i < a.size(); ++i)
   1142       fprintf(fp, " %d", a[i]);
   1143     fputc('\n', fp);
   1144     return *this;
   1145   }
   1146  
   1147   // Calculations
   1148   Poly operator+(const Poly &rhs) const {
   1149     vector<int> res(max(a.size(), rhs.a.size()));
   1150     for (int i = 0; i < res.size(); ++i)
   1151       if ((res[i] = operator[](i) + rhs[i]) >= P)
   1152         res[i] -= P;
   1153     return res;
   1154   }
   1155  
   1156   Poly operator-() const {
   1157     Poly ret(a);
   1158     for (int i = 0; i < a.size(); ++i)
   1159       if (ret[i])
   1160         ret[i] = P - ret[i];
   1161     return ret;
   1162   }
   1163  
   1164   Poly operator-(const Poly &rhs) const { return operator+(-rhs); }
   1165  
   1166   Poly operator*(const Poly &rhs) const;
   1167  
   1168   Poly taylor(int k) const;
   1169 };
   1170  
   1171 Poly zeroes(int deg) { return vector<int>(deg + 1); }
   1172  
   1173 Poly operator "" _z(unsigned long long a) { return {0, (int) a}; }
   1174  
   1175 Poly operator+(int v, const Poly &rhs) { return Poly(v) + rhs; }
   1176  
   1177 Poly Poly::operator*(const Poly &rhs) const {
   1178   int n = deg(), m = rhs.deg();
   1179   if (n <= 10 || m <= 10 || n + m <= BRUTE_N2_LIMIT) {
   1180     Poly ret = zeroes(n + m);
   1181     for (int i = 0; i <= n; ++i)
   1182       for (int j = 0; j <= m; ++j)
   1183         ret[i + j] = (ret[i + j] + a[i] * (ll) rhs[j]) % P;
   1184     return ret;
   1185   }
   1186   n += m;
   1187   int l = 0;
   1188   while ((1 << l) <= n)
   1189     ++l;
   1190   vector<int> res(1 << l), tmp(1 << l);
   1191   memcpy(res.data(), base(), a.size() * sizeof(int));
   1192   ntt.fft(res.data(), l, 1);
   1193   memcpy(tmp.data(), rhs.base(), rhs.a.size() * sizeof(int));
   1194   ntt.fft(tmp.data(), l, 1);
   1195   for (int i = 0; i < (1 << l); ++i)
   1196     res[i] = res[i] * (ll) tmp[i] % P;
   1197   ntt.fft(res.data(), l, -1);
   1198   res.resize(n + 1);
   1199   return res;
   1200 }
   1201  
   1202 Poly Poly::taylor(int k) const {
   1203   int n = deg();
   1204   Poly t = zeroes(n);
   1205   simp.check(n);
   1206   for (int i = 0; i <= n; ++i)
   1207     t[n - i] = a[i] * (ll) simp.fac[i] % P;
   1208   int pw = 1;
   1209   Poly help = vector<int>(simp.ifac.begin(), simp.ifac.begin() + n + 1);
   1210   for (int i = 0; i <= n; ++i) {
   1211     help[i] = help[i] * (ll) pw % P;
   1212     pw = pw * (ll) k % P;
   1213   }
   1214   t = t * help;
   1215   for (int i = 0; i <= n; ++i)
   1216     help[i] = t[n - i] * (ll) simp.ifac[i] % P;
   1217   return help;
   1218 }
   1219  
   1220 Poly stirling2(int n) {
   1221   Poly p = zeroes(n), ne = zeroes(n);
   1222   for (int i = 0; i <= n; ++i) p[i] = mpow(i, n) * (ll)simp.gifac(i) % P;
   1223   for (int i = 0; i <= n; ++i) ne[i] = simp.gifac(i);
   1224   for (int i = 1; i <= n; i += 2) ne[i] = P - ne[i];
   1225   p = p * ne;
   1226   vector<int> ans(n + 1);
   1227   for (int i = 0; i <= n; ++i) ans[i] = p[i] * (ll)simp.gfac(i) % P;
   1228   return ans;
   1229 }
   1230  
   1231 namespace DC {
   1232  
   1233 int N;
   1234 vector<Poly> prd, sum;
   1235  
   1236 Poly lift(Poly a, int k) {
   1237   a.a.insert(a.a.begin(), k, 0);
   1238   return a;
   1239 }
   1240  
   1241 void build(int o, int l, int r) {
   1242   if (l == r - 1) {
   1243     prd[o].redeg(1);
   1244     prd[o][1] = P - simp.ginv(r);
   1245     prd[o][0] = (P - l) * (ll)simp.ginv(r) % P;
   1246     sum[o] = prd[o];
   1247     return;
   1248   }
   1249   int mid = (l + r + 1) / 2;
   1250   build(o << 1, l, mid);
   1251   build(o << 1 | 1, mid, r);
   1252   prd[o] = prd[o << 1] * prd[o << 1 | 1];
   1253   sum[o] = prd[o << 1] * sum[o << 1 | 1] + lift(sum[o << 1], r - mid);
   1254 }
   1255  
   1256 void pre(int n) {
   1257   N = n;
   1258   sum.resize(n * 4); prd.resize(n * 4);
   1259   build(1, 0, n);
   1260 }
   1261  
   1262 Poly input;
   1263  
   1264 pair<Poly, Poly> solve(int o, int l, int r) {
   1265   if (l == r - 1) {
   1266     Poly r1 = input[r];
   1267     return make_pair(r1 * prd[o], lift(r1, 1));
   1268   }
   1269   int mid = (l + r + 1) / 2;
   1270   auto ls = solve(o << 1, l, mid), rs = solve(o << 1 | 1, mid, r);
   1271   ls.first = ls.first + prd[o << 1] * rs.first + sum[o << 1] * rs.second;
   1272   ls.second = ls.second + lift(rs.second, mid - l);
   1273   return ls;
   1274 }
   1275  
   1276 Poly solve(Poly in) {
   1277   input = in; input.redeg(N);
   1278   auto pr = solve(1, 0, N);
   1279   auto ret = pr.first + pr.second;
   1280   ret[0] = (ret[0] + input[0]) % P;
   1281   return ret;
   1282 }
   1283  
   1284 }
   1285  
   1286 Poly compute(Poly coeff) {
   1287   int n = coeff.deg();
   1288   Poly ret = DC::solve(coeff);
   1289   ret.redeg(n);
   1290   reverse(ret.a.begin(), ret.a.end());
   1291   ret = ret.taylor(P - 1);
   1292   reverse(ret.a.begin(), ret.a.end());
   1293   return ret;
   1294 }
   1295  
   1296 Poly solve(int n) {
   1297   DC::pre(n);
   1298   auto v0 = stirling2(n), v1 = stirling2(n - 1);
   1299   return compute(v0) + compute(v1);
   1300 }
   1301  
   1302 int main() {
   1303   ios::sync_with_stdio(false); cin.tie(nullptr);
   1304  
   1305   int n, s; cin >> n >> s;
   1306   auto ans = solve(n - s);
   1307   for (int i = 0; i < s; ++i) cout << "0 ";
   1308   for (int i = n - s - 1; i >= 0; --i)
   1309     cout << ans[i] * (ll)simp.binom(n - 1, s) % P
   1310          << " \n"[i == 0];
   1311  
   1312   return 0;
   1313 }
   1314 ```