1688.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 ```