1350.md (16246B)
1 Source: https://codeforces.com/blog/entry/77284 2 3 You can view Chinese editorial here: <https://www.luogu.com.cn/blog/Caro23333/codeforces-round-641-zhong-wen-ti-xie> 4 5 Div2.A Problem and editorial by [BlueSmoke](/profile/BlueSmoke "Candidate Master BlueSmoke") 6 7 **Editorial** 8 9 Tutorial is loading... 10 11 **Code** 12 13 ``` 14 #include <iostream> 15 #include <cstdio> 16 #include <cstring> 17 #include <cstdlib> 18 #include <algorithm> 19 20 using namespace std; 21 22 int main() 23 { 24 int T; 25 cin >> T; 26 while(T--) 27 { 28 int n,k; 29 cin >> n >> k; 30 if(n%2==0) 31 { 32 cout << n+2*k << endl; 33 continue; 34 } 35 int p = 0; 36 for(int i = n; i>=2; i--) 37 if(n%i==0) 38 p = i; 39 cout << n+p+2*(k-1) << endl; 40 } 41 return 0; 42 } 43 ``` 44 45 Div2.B Problem and editorial by [BlueSmoke](/profile/BlueSmoke "Candidate Master BlueSmoke") 46 47 **Editorial** 48 49 Tutorial is loading... 50 51 **Code** 52 53 ``` 54 #include <iostream> 55 #include <cstdlib> 56 #include <cstdio> 57 #include <cstring> 58 #include <algorithm> 59 60 using namespace std; 61 const int MAXN = 500005; 62 inline int readint() 63 { 64 int res = 0; 65 char c = 0; 66 while(!isdigit(c)) 67 c = getchar(); 68 while(isdigit(c)) 69 res = res*10+c-'0', c = getchar(); 70 return res; 71 } 72 int n,a[MAXN],f[MAXN]; 73 74 int main() 75 { 76 int T = readint(); 77 while(T--) 78 { 79 n = readint(); 80 for(int i = 1; i<=n; i++) 81 a[i] = readint(); 82 for(int i = 1; i<=n; i++) 83 f[i] = 1; 84 for(int i = 1; i<=n; i++) 85 for(int j = i*2; j<=n; j += i) 86 if(a[i]<a[j]) 87 f[j] = max(f[j],f[i]+1); 88 int ans = 0; 89 for(int i = 1; i<=n; i++) 90 ans = max(ans,f[i]); 91 cout << ans << endl; 92 } 93 return 0; 94 } 95 ``` 96 97 Div1.A Problem and editorial by [mydiplomacy](/profile/mydiplomacy "Candidate Master mydiplomacy") 98 99 **Editorial** 100 101 Tutorial is loading... 102 103 **Code** 104 105 ``` 106 #include <iostream> 107 #include <cstdio> 108 109 using namespace std; 110 typedef long long ll; 111 112 const int maxn=100005; 113 114 int n; 115 ll a[maxn]; 116 117 ll pre[maxn],suf[maxn]; 118 119 ll gcd(ll x, ll y) 120 { 121 if(y==0) return x; 122 else return gcd(y,x%y); 123 } 124 125 ll ga,ans; 126 127 int main() 128 { 129 scanf("%d",&n); 130 for(int i=1;i<=n;i++) scanf("%lld",&a[i]); 131 pre[1]=a[1]; suf[n]=a[n]; 132 for(int i=2;i<=n;i++) 133 pre[i]=gcd(pre[i-1],a[i]); 134 for(int i=n-1;i>=1;i--) 135 suf[i]=gcd(suf[i+1],a[i]); 136 for(int i=0;i<=n-1;i++) 137 { 138 if(i==0) 139 ans=suf[2]; 140 else if(i==n-1) 141 ans=ans*pre[n-1]/gcd(pre[n-1],ans); 142 else 143 ans=ans*gcd(pre[i],suf[i+2])/gcd(gcd(pre[i],suf[i+2]),ans); 144 } 145 printf("%lld\n",ans); 146 return 0; 147 } 148 ``` 149 150 Div1.B Problem and editorial by [A.K.E.E.](/profile/A.K.E.E. "International Grandmaster A.K.E.E.") 151 152 **Editorial** 153 154 Tutorial is loading... 155 156 **Code** 157 158 ``` 159 #include <bits/stdc++.h> 160 using namespace std; 161 typedef long long ll; 162 typedef unsigned long long ull; 163 typedef pair<int,int> pii; 164 #define x first 165 #define y second 166 #define mp make_pair 167 #define pb push_back 168 template <typename TYPE> inline void chkmax(TYPE &x,TYPE y){x<y?x=y:TYPE();} 169 template <typename TYPE> inline void chkmin(TYPE &x,TYPE y){y<x?x=y:TYPE();} 170 template <typename TYPE> void readint(TYPE &x) 171 { 172 x=0;int f=1;char c; 173 for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1; 174 for(;isdigit(c);c=getchar())x=x*10+c-'0'; 175 x*=f; 176 } 177 const int MAXN=500005; 178 179 int n,k,a[MAXN]; 180 bool solve() 181 { 182 readint(n),readint(k); 183 bool flag=0; 184 for(int i=1;i<=n;++i) 185 { 186 readint(a[i]); 187 if(a[i]<k)a[i]=0; 188 else if(a[i]>k)a[i]=2; 189 else a[i]=1; 190 if(a[i]==1)flag=1; 191 } 192 if(!flag)return 0; 193 if(n==1)return 1; 194 for(int i=1;i<=n;++i) 195 for(int j=i+1;j<=n && j-i<=2;++j) 196 if(a[i] && a[j])return 1; 197 return 0; 198 } 199 200 int main() 201 { 202 int T; 203 readint(T); 204 while(T--)printf(solve()?"yes\n":"no\n"); 205 return 0; 206 } 207 ``` 208 209 Div1.C Problem and editorial by [A.K.E.E.](/profile/A.K.E.E. "International Grandmaster A.K.E.E.") 210 211 **Editorial** 212 213 Tutorial is loading... 214 215 **Code** 216 217 ``` 218 #include <iostream> 219 #include <cstdio> 220 #include <cstring> 221 #include <cstdlib> 222 #include <algorithm> 223 #define pii pair<int,int> 224 #define mp make_pair 225 #define fi first 226 #define se second 227 228 using namespace std; 229 typedef long long ll; 230 const int MAXN = 1005; 231 inline ll readint() 232 { 233 ll res = 0, f = 1; 234 char c = 0; 235 while(!isdigit(c)) 236 { 237 c = getchar(); 238 if(c=='-') 239 f = -1; 240 } 241 while(isdigit(c)) 242 res = res*10+c-'0', c = getchar(); 243 return res*f; 244 } 245 int n,m,T,a[MAXN][MAXN]; 246 char str[MAXN]; 247 int f[MAXN][MAXN],pos[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; 248 bool vis[MAXN][MAXN]; 249 inline bool check(int x, int y) 250 { 251 for(int i = 0; i<4; i++) 252 { 253 int nx = x+pos[i][0], ny = y+pos[i][1]; 254 if(a[nx][ny]==a[x][y]) 255 return true; 256 } 257 return false; 258 } 259 pii q[MAXN*MAXN]; 260 inline void bfs() 261 { 262 int front = 0, rear = 0; 263 for(int i = 1; i<=n; i++) 264 for(int j = 1; j<=m; j++) 265 if(check(i,j)) 266 f[i][j] = 0, vis[i][j] = true, q[rear++] = mp(i,j); 267 while(front<rear) 268 { 269 pii now = q[front++]; 270 for(int i = 0; i<4; i++) 271 { 272 int nx = now.fi+pos[i][0], ny = now.se+pos[i][1]; 273 if(nx<1||nx>n||ny<1||ny>m||vis[nx][ny]) 274 continue; 275 f[nx][ny] = f[now.fi][now.se]+1; 276 vis[nx][ny] = true; 277 q[rear++] = mp(nx,ny); 278 } 279 } 280 } 281 282 int main() 283 { 284 n = readint(), m = readint(), T = readint(); 285 memset(a,-1,sizeof(a)); 286 for(int i = 1; i<=n; i++) 287 { 288 scanf("%s",str+1); 289 for(int j = 1; j<=m; j++) 290 a[i][j] = str[j]-'0'; 291 } 292 bfs(); 293 int x,y; 294 ll t; 295 while(T--) 296 { 297 x = readint(), y = readint(), t = readint(); 298 if(vis[x][y]) 299 printf("%d\n",a[x][y]^(max(0ll,t-f[x][y])&1)); 300 else 301 printf("%d\n",a[x][y]); 302 } 303 return 0; 304 } 305 ``` 306 307 Div1.D Problem and editorial by [Rebelz](/profile/Rebelz "International Grandmaster Rebelz") 308 309 Part of solution by [Elegia](/profile/Elegia "International Grandmaster Elegia") 310 311 **Editorial** 312 313 Tutorial is loading... 314 315 **Code** 316 317 ``` 318 #include<bits/stdc++.h> 319 320 #define pb push_back 321 #define mp make_pair 322 #define fi first 323 #define se second 324 325 using namespace std; 326 327 typedef long long ll; 328 typedef unsigned long long ull; 329 typedef pair<int,int> pii; 330 typedef pair<ll,ll> pll; 331 332 template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;} 333 template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;} 334 335 int readint(){ 336 int x=0,f=1; char ch=getchar(); 337 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 338 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 339 return x*f; 340 } 341 342 const int cys=998244353; 343 int n,m; 344 ll a[100005],ans[300005]; 345 346 ll qpow(ll x,ll p){ 347 ll ret=1; 348 for(;p;p>>=1,x=x*x%cys) if(p&1) ret=ret*x%cys; 349 return ret; 350 } 351 352 int main(){ 353 n=readint(); 354 for(int i=1;i<=n;i++) a[i]=readint(),m+=a[i]; 355 ll invm=qpow(m,cys-2),invn1=qpow(n-1,cys-2); 356 for(int i=m;i>=1;i--){ 357 ll k1=i*invm%cys*invn1%cys,k2=(m-i)*invm%cys; 358 ans[i]=(k2*ans[i+1]+1)%cys*qpow(k1,cys-2)%cys; 359 } 360 for(int i=1;i<=m;i++) ans[i]=(ans[i]+ans[i-1])%cys; 361 ll res=0; 362 for(int i=1;i<=n;i++) res=(res+ans[m-a[i]])%cys; 363 res=(res+cys-ans[m]*(n-1)%cys)%cys; 364 printf("%lld\n",res*qpow(n,cys-2)%cys); 365 return 0; 366 } 367 ``` 368 369 Div1.E Problem and editorial by [A.K.E.E.](/profile/A.K.E.E. "International Grandmaster A.K.E.E.") 370 371 **Editorial** 372 373 Tutorial is loading... 374 375 **Code** 376 377 ``` 378 #include <bits/stdc++.h> 379 using namespace std; 380 typedef long long ll; 381 typedef pair<int,ll> pii; 382 #define x first 383 #define y second 384 #define pb push_back 385 const int MAXN=200005; 386 387 int n,m,cnt; 388 pii a[MAXN]; 389 bool avis[MAXN]; 390 struct Range 391 { 392 int l,r,type; 393 ll val; 394 Range(){} 395 Range(int l,int r,int type,ll val):l(l),r(r),type(type),val(val){} 396 }b[MAXN]; 397 398 int f[2][MAXN],wh[2][MAXN],res[MAXN]; 399 vector<int> str[2][MAXN]; 400 bool check(ll s,int l,int r) 401 { 402 if(s<=0)return !s && r-l+1>=0; 403 ll L=1,R=r-l+1,mid,ans=0; 404 while(L<=R) 405 { 406 mid=(L+R)>>1; 407 if((l+l+mid-1)*mid<=s*2)ans=mid,L=mid+1; 408 else R=mid-1; 409 } 410 return s*2<=(r+r-ans+1)*ans; 411 } 412 void modify(ll s,int l,int r,vector<int> &tar,int start) 413 { 414 ll L=1,R=r-l+1,mid,ans=0; 415 while(L<=R) 416 { 417 mid=(L+R)>>1; 418 if((l+l+mid-1)*mid<=s*2)ans=mid,L=mid+1; 419 else R=mid-1; 420 } 421 for(int i=l;i<=r;i++) 422 if(ans && (i+i+ans-2)*(ans-1)<=(s-i)*2 && (s-i)*2<=(r+r-ans+2)*(ans-1)) 423 {--ans,s-=i;tar.pb(1);} 424 else tar.pb(0); 425 } 426 void update(int i,int ti,int ti_1,int pos,ll d) 427 { 428 if(pos<=f[ti][i])return; 429 str[ti][i].clear(); 430 f[ti][i]=pos;wh[ti][i]=ti_1; 431 str[ti][i].pb(1); 432 for(int j=f[ti][i]+1;j<=b[i].r;j++)str[ti][i].pb(0); 433 modify(d-f[ti][i],b[i].r+1,f[ti_1][i-1]-1,str[ti][i],f[ti][i]); 434 } 435 436 int main() 437 { 438 #ifndef ONLINE_JUDGE 439 //freopen("code.in","r",stdin); 440 //freopen("code.out","w",stdout); 441 #endif 442 scanf("%d",&n); 443 for(int i=1;i<=n;i++) 444 { 445 ll y; 446 scanf("%lld",&y); 447 if(!y)continue; 448 a[++m]=make_pair(n-i+1,y); 449 avis[n-i+1]=1; 450 } 451 if(!m) 452 { 453 for(int i=1;i<=n;i++)putchar('0'); 454 return 0; 455 } 456 sort(a+1,a+m+1); 457 b[cnt=1]=Range(a[m].x,a[m].x,2,a[m].y); 458 for(int i=m-1;i;i--) 459 { 460 if(a[i].y==a[i+1].y)b[cnt].l=a[i].x,b[cnt].type=0; 461 else if(a[i].y==a[i+1].y-1)b[cnt].l=a[i].x,b[cnt].type=1,b[cnt].val--; 462 else b[++cnt]=Range(a[i].x,a[i].x,2,a[i].y); 463 } 464 b[cnt+1]=Range(-1,-1,0,0); 465 bool error=0; 466 f[0][0]=-1;f[1][0]=n+1; 467 for(int i=1;i<=cnt;i++) 468 { 469 f[0][i]=f[1][i]=-1; 470 for(int t=0;t<=1;t++) 471 if(f[t][i-1]>b[i].r) 472 { 473 if(b[i].type==0 || b[i].type==2) 474 { 475 ll d=(b[i].val-1)-(b[i-1].val-1+t); 476 int pos=-1; 477 for(int j=min(b[i].l-1ll,d);j>b[i+1].r;--j) 478 if(check(d-j,b[i].r+1,f[t][i-1]-1)){pos=j;break;} 479 update(i,0,t,pos,d); 480 } 481 if(b[i].type==1 || b[i].type==2) 482 { 483 ll d=b[i].val-(b[i-1].val-1+t); 484 if(check(d-b[i].l,b[i].r+1,f[t][i-1]-1)) 485 update(i,1,t,b[i].l,d); 486 } 487 } 488 if(f[0][i]<0 && f[1][i]<0 && i==cnt && !b[i].type)error=1; 489 } 490 if(error) 491 { 492 for(int t=0;t<=1;t++) 493 if(f[t][cnt-1]>b[cnt].r) 494 { 495 ll d=(b[cnt].val-1)-(b[cnt-1].val-1+t); 496 int pos=-1; 497 for(int j=min((ll)b[cnt].r,d);j>=b[cnt].l;--j) 498 { 499 if(avis[j])continue; 500 if(check(d-j,b[cnt].r+1,f[t][cnt-1]-1)){pos=j;break;} 501 } 502 update(cnt,0,t,pos,d); 503 } 504 } 505 int cur=(f[1][cnt]>0); 506 for(int i=1;i<f[cur][cnt];i++)res[i]=0; 507 for(int i=cnt;i>0;i--) 508 { 509 for(int j=0;j<(int)str[cur][i].size();j++)res[j+f[cur][i]]=str[cur][i][j]; 510 cur=wh[cur][i]; 511 } 512 for(int i=n;i>0;i--)putchar(res[i]+'0'); 513 return 0; 514 } 515 ``` 516 517 Div1.F Problem and editorial by [Rebelz](/profile/Rebelz "International Grandmaster Rebelz") 518 519 Hard version solution by [Elegia](/profile/Elegia "International Grandmaster Elegia") 520 521 **Editorial for easy version** 522 523 Tutorial is loading... 524 525 **Code** 526 527 ``` 528 #include<bits/stdc++.h> 529 530 #define pb push_back 531 #define mp make_pair 532 #define fi first 533 #define se second 534 535 using namespace std; 536 537 typedef long long ll; 538 typedef unsigned long long ull; 539 typedef pair<int,int> pii; 540 typedef pair<ll,ll> pll; 541 542 template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;} 543 template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;} 544 545 int readint(){ 546 int x=0,f=1; char ch=getchar(); 547 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 548 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 549 return x*f; 550 } 551 552 const int cys=998244353; 553 int n; 554 ll fac[5005],inv[5005],d[5005][5005],ans[5005]; 555 556 ll qpow(ll x,ll p){ 557 ll ret=1; 558 for(;p;p>>=1,x=x*x%cys) if(p&1) ret=ret*x%cys; 559 return ret; 560 } 561 562 int main(){ 563 n=readint(); 564 d[0][0]=fac[0]=inv[0]=1; 565 for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%cys; 566 inv[n]=qpow(fac[n],cys-2); 567 for(int i=n-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%cys; 568 for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) d[i][j]=(d[i-1][j-1]*(i-j+1)+d[i-1][j]*j)%cys; 569 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ans[i]=(ans[i]+d[j][i]*inv[j])%cys; 570 for(int i=1;i<=n;i++) printf("%lld ",ans[i]*fac[n]%cys); 571 printf("\n"); 572 return 0; 573 } 574 ``` 575 576 **Editorial for hard version** 577 578 Tutorial is loading... 579 580 **Code** 581 582 ``` 583 #include<bits/stdc++.h> 584 585 #define pb push_back 586 #define mp make_pair 587 #define fi first 588 #define se second 589 590 using namespace std; 591 592 typedef long long ll; 593 typedef unsigned long long ull; 594 typedef vector<ll> vi; 595 typedef pair<int,int> pii; 596 typedef pair<ll,ll> pll; 597 598 template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;} 599 template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;} 600 601 int readint(){ 602 int x=0,f=1; char ch=getchar(); 603 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 604 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 605 return x*f; 606 } 607 608 const int cys=998244353,g=3,invg=(cys+1)/3; 609 int n; 610 ll ni[200015],fac[200015],inv[200015],tw[200005]; 611 612 int mod(int x){return x>=cys?x-cys:x;} 613 614 ll qpow(ll x,ll p){ 615 ll ret=1; 616 for(;p;p>>=1,x=x*x%cys) if(p&1) ret=ret*x%cys; 617 return ret; 618 } 619 620 vi operator+(vi a,vi b){ 621 vi ret(max(a.size(),b.size())); 622 for(int i=0;i<ret.size();i++) ret[i]=mod((i<a.size()?a[i]:0)+(i<b.size()?b[i]:0)); 623 return ret; 624 } 625 626 vi operator-(vi a,vi b){ 627 vi ret(max(a.size(),b.size())); 628 for(int i=0;i<ret.size();i++) ret[i]=mod((i<a.size()?a[i]:0)+cys-(i<b.size()?b[i]:0)); 629 return ret; 630 } 631 632 vi operator*(vi a,ll b){ 633 for(int i=0;i<a.size();i++) a[i]=1ll*a[i]*b%cys; 634 return a; 635 } 636 637 vi operator>>(vi a,int b){ 638 for(int i=0;i<a.size()-b;i++) a[i]=a[i+b]; 639 a.resize(a.size()-b); 640 return a; 641 } 642 643 namespace poly{ 644 int N,l; 645 int A[1100000],B[1100000],r[1100000],pre1[20][600000],pre2[20][600000]; 646 void pre(){ 647 for(int i=1,r=0;i<(1<<19);i<<=1,r++){ 648 int w=1,wn=qpow(g,(cys-1)/(i<<1)); 649 for(int j=0;j<i;j++,w=1ll*w*wn%cys) pre1[r][j]=w; 650 } 651 for(int i=1,r=0;i<(1<<19);i<<=1,r++){ 652 int w=1,wn=qpow(invg,(cys-1)/(i<<1)); 653 for(int j=0;j<i;j++,w=1ll*w*wn%cys) pre2[r][j]=w; 654 } 655 } 656 void ntt(int *A,int N,int f){ 657 for(int i=0;i<N;i++) if(i<r[i]) swap(A[i],A[r[i]]); 658 for(int i=1,r=0;i<N;i<<=1,r++){ 659 for(int j=0;j<N;j+=(i<<1)){ 660 for(int k=j;k<j+i;k++){ 661 int x=A[k],y=1ll*A[k+i]*(f>0?pre1[r][k-j]:pre2[r][k-j])%cys; 662 A[k]=mod(x+y); A[k+i]=mod(x+cys-y); 663 } 664 } 665 } 666 if(f<0){ 667 int invn=qpow(N,cys-2); 668 for(int i=0;i<N;i++) A[i]=1ll*A[i]*invn%cys; 669 } 670 } 671 void init(int t){ 672 N=1,l=0; 673 for(;N<t;N<<=1) l++; 674 for(int i=0;i<N;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1)); 675 } 676 void getmul(){ 677 ntt(A,N,1); ntt(B,N,1); 678 for(int i=0;i<N;i++) A[i]=1ll*A[i]*B[i]%cys; 679 ntt(A,N,-1); 680 } 681 vi mul(vi a,vi b){ 682 init(a.size()+b.size()); 683 for(int i=0;i<N;i++) A[i]=i<a.size()?a[i]:0; 684 for(int i=0;i<N;i++) B[i]=i<b.size()?b[i]:0; 685 getmul(); 686 vi ret(a.size()+b.size()-1); 687 for(int i=0;i<ret.size();i++) ret[i]=A[i]; 688 return ret; 689 } 690 vi polyinv(vi a,int l){ 691 if(l==1) return vi(1,qpow(a[0],cys-2)); 692 a.resize(l); 693 vi b=polyinv(a,(l+1)/2); 694 init(l<<1); 695 for(int i=0;i<N;i++) A[i]=i<l?a[i]:0; 696 for(int i=0;i<N;i++) B[i]=i<(l+1)/2?b[i]:0; 697 ntt(A,N,1); ntt(B,N,1); 698 for(int i=0;i<N;i++) A[i]=1ll*A[i]*B[i]%cys*B[i]%cys; 699 ntt(A,N,-1); 700 vi t=b*2; 701 t.resize(l); 702 for(int i=0;i<l;i++) t[i]=mod(t[i]+cys-A[i]); 703 return t; 704 } 705 vi polydiff(vi a){ 706 for(int i=0;i<a.size()-1;i++) a[i]=1ll*(i+1)*a[i+1]%cys; 707 a.resize(a.size()-1); 708 return a; 709 } 710 vi polyint(vi a){ 711 a.resize(a.size()+1); 712 for(int i=a.size()-1;i>=1;i--) a[i]=1ll*a[i-1]*ni[i]%cys; 713 a[0]=0; 714 return a; 715 } 716 vi polyln(vi a,int l){ 717 return polyint(mul(polydiff(a),polyinv(a,l))); 718 } 719 vi polyexp(vi a,int l){ 720 if(l==1) return vi(1,1); 721 a.resize(l); 722 vi b=polyexp(a,(l+1)/2); 723 init(l<<1); 724 vi t=mul(b,vi(1,1)-polyln(b,l)+a); 725 t.resize(l); 726 return t; 727 } 728 vi polypow(vi a,int l,int k){ 729 return polyexp(polyln(a,l)*k,l); 730 } 731 } 732 733 vi getans(){ 734 vi f(0); 735 for(int i=0;i<=n+1;i++) f.push_back(inv[i+1]); 736 vi tmp=poly::mul(f,poly::polyinv((vi(1,1)-f)>>1,n+1)); 737 vi tw(0); tw.resize(n); 738 for(int i=0;i<n;i++) tw[i]=tmp[i+1]; 739 vi h(0); 740 h.push_back(1),h.push_back(1); 741 h=poly::polyinv(poly::polyln(h,n+3)>>1,n+2); 742 vi g=poly::polyinv((vi(1,1)-h)>>1,n+1); 743 vi ph=poly::polypow(h,n+1,n+1); 744 vi t1=poly::mul(g,ph); 745 vi tmp1=poly::mul(poly::polydiff(h),ph); 746 tmp1.resize(n+1); 747 vi tmp2=poly::mul(g,g); 748 tmp2.resize(n+1); 749 vi t2=poly::mul(tmp1,tmp2); 750 for(int i=0;i<n;i++) tw[i]=mod(tw[i]+cys-ni[n+1]*mod(t1[i+1]*(n-i+1)%cys+t2[i+1])%cys); 751 for(int i=0;i<n;i++) tw[i]=tw[i]*fac[i]%cys; 752 reverse(tw.begin(),tw.end()); 753 tmp.clear(); 754 for(int i=0;i<n;i++) tmp.push_back(i&1?cys-inv[i]:inv[i]); 755 tw=poly::mul(tw,tmp); 756 tw.resize(n); 757 reverse(tw.begin(),tw.end()); 758 return tw; 759 } 760 761 int main(){ 762 poly::pre(); 763 n=readint(); 764 fac[0]=inv[0]=1; 765 for(int i=1;i<=n+5;i++) fac[i]=fac[i-1]*i%cys; 766 inv[n+5]=qpow(fac[n+5],cys-2); 767 for(int i=n+4;i>=1;i--) inv[i]=inv[i+1]*(i+1)%cys; 768 for(int i=1;i<=n+5;i++) ni[i]=inv[i]*fac[i-1]%cys; 769 vi res=getans(); 770 for(int i=0;i<n;i++) printf("%lld ",res[i]*fac[n]%cys*inv[i]%cys); 771 printf("\n"); 772 return 0; 773 } 774 ``` 775 776 You can also view Div1.F editorial by [Elegia](/profile/Elegia "International Grandmaster Elegia") here: <https://codeforces.com/blog/entry/77280> 777 778 Anyway, hope you like these problems and thank you for participating!