1704.md (19236B)
1 Source: https://codeforces.com/blog/entry/105464 2 3 Tutorial is loading... 4 5 **solution** 6 7 ``` 8 #include <bits/stdc++.h> 9 using namespace std; 10 const int maxn = 2e5; 11 signed main() { 12 ios::sync_with_stdio(false); 13 cin.tie(nullptr); 14 cout.tie(nullptr); 15 int T; 16 cin >> T; 17 while (T--) { 18 int n, m; 19 cin >> n >> m; 20 string a, b; 21 cin >> a >> b; 22 if (n < m) { 23 cout << "NO\n"; 24 continue; 25 } 26 bool same = true; 27 for (int i = 1; i < b.size(); ++i) { 28 if (a[i + n - m] != b[i]) { 29 same = false; 30 break; 31 } 32 } 33 if (!same) { 34 cout << "NO\n"; 35 continue; 36 } 37 for (int i = 0; i < n - m + 1; ++i) { 38 if (a[i] == b[0]) { 39 same = false; 40 } 41 } 42 if (same) { 43 cout << "NO\n"; 44 } 45 else { 46 cout << "YES\n"; 47 } 48 } 49 } 50 ``` 51 52 Tutorial is loading... 53 54 **solution** 55 56 ``` 57 #include <stdio.h> 58 #include <string.h> 59 #include <vector> 60 #include <set> 61 #include <queue> 62 #include <string> 63 #include <map> 64 #include <chrono> 65 #include <stdlib.h> 66 #include <time.h> 67 #include <algorithm> 68 #include <iostream> 69 #include <memory> 70 #include <cstdio> 71 #include <assert.h> 72 #include <iostream> 73 const int MAXN = 300005; 74 int numbers[MAXN]; 75 int main() { 76 int t; 77 int n, x; 78 79 scanf("%d", &t); 80 while (t--) 81 { 82 scanf("%d %d", &n, &x); 83 for (int i = 1; i <= n; i++) { 84 scanf("%d", &numbers[i]); 85 } 86 int num_min = numbers[1]; 87 int num_max = numbers[1]; 88 int res = 0; 89 for (int i = 2; i <= n; i++) { 90 if (numbers[i] > num_max) { 91 num_max = numbers[i]; 92 } 93 if (numbers[i] < num_min) { 94 num_min = numbers[i]; 95 } 96 if (num_max - num_min > 2 * x) { 97 res++; 98 num_min = num_max = numbers[i]; 99 } 100 } 101 printf("%d\n", res); 102 } 103 return 0; 104 } 105 ``` 106 107 Tutorial is loading... 108 109 **solution** 110 111 ``` 112 #include<bits/stdc++.h> 113 using namespace std; 114 const int N = 500005, inf = 2147483647, M = 1004535809; 115 int n, m, a[N], T, k; 116 struct str { 117 int x, y; 118 }t[N]; 119 int main() { 120 scanf("%d", &T); 121 while (T--) { 122 k = 0; 123 scanf("%d %d", &n, &m); 124 for (int i = 1; i <= m; ++i) 125 scanf("%d", &a[i]); 126 sort(a + 1, a + 1 + m); 127 for (int i = 2; i <= m; ++i) 128 t[++k] = { a[i] - a[i - 1] - 1,2 }; 129 int num_tmp = a[1] + n - a[m] - 1; 130 if (num_tmp > 0) { 131 t[++k] = { num_tmp, 2 }; 132 } 133 sort(t + 1, t + 1 + k, [](str a, str b) {return a.x > b.x; }); 134 long long ans = 0, cnt = 0; 135 for (int i = 1; i <= k; ++i) { 136 if (t[i].x - cnt * 2 > 0) { 137 int num_tmp = max(1ll, t[i].x - cnt * 2 - 1); 138 ans += num_tmp; 139 } 140 cnt += 2; 141 } 142 printf("%lld\n", n - ans); 143 } 144 } 145 ``` 146 147 Tutorial is loading... 148 149 **solution** 150 151 ``` 152 #include <stdio.h> 153 #include <string.h> 154 #include <vector> 155 #include <map> 156 #include <cassert> 157 const int MAXN = 500005; 158 std::vector<long long> numbers[MAXN]; 159 std::map<long long, long long> val_to_index; 160 int main() 161 { 162 int t; 163 int n, m; 164 scanf("%d ", &t); 165 while (t--) 166 { 167 val_to_index.clear(); 168 scanf("%d %d", &n, &m); 169 long long num_tmp; 170 for (int i = 1; i <= n; i++) { 171 numbers[i].clear(); 172 numbers[i].push_back(0); 173 for (int j = 1; j <= m; j++) { 174 scanf("%lld", &num_tmp); 175 numbers[i].push_back(num_tmp); 176 } 177 } 178 long long res_tmp = -1; 179 for (long long i = 1; i <= n; i++) { 180 long long val = 0; 181 for (long long j = 1; j <= m; j++) { 182 val += (j * numbers[i][j]); 183 } 184 if (val_to_index.find(val) != val_to_index.end()) { 185 res_tmp = val; 186 val_to_index[val] = -1; 187 } 188 else { 189 val_to_index[val] = i; 190 } 191 } 192 assert(val_to_index.size() == 2); 193 for (auto &item : val_to_index) { 194 if (item.second != -1ll) { 195 printf("%lld %lld\n", item.second, std::abs(res_tmp - item.first)); 196 break; 197 } 198 } 199 } 200 return 0; 201 } 202 ``` 203 204 Tutorial is loading... 205 206 **solution** 207 208 ``` 209 #include<bits/stdc++.h> 210 using namespace std; 211 const int N = 500005, inf = 2147483647, M = 998244353; 212 int n, m, a[N], u, v, i, d[N], q[N], r, mx; 213 int b[N], tmp[N]; 214 vector<int> g[N], z[N]; 215 long long s[N]; 216 int p[15]; 217 void NEX(int M) { 218 for (int i = 1; i <= n; ++i) 219 if (b[i]) { 220 tmp[i] += b[i] - 1; 221 for (auto it : g[i]) 222 ++tmp[it]; 223 } 224 for (int i = 1; i <= n; ++i) { 225 if (tmp[i] >= M) 226 b[i] = tmp[i] % M + M; 227 else 228 b[i] = tmp[i] % M; 229 tmp[i] = 0; 230 } 231 } 232 int cal(int M) { 233 for (int i = 1; i <= n; ++i) { 234 b[i] = a[i]; 235 } 236 for (int i = 1; i <= n; ++i) { 237 bool fl = false; 238 for (int j = 1; j <= n; ++j) 239 if (b[j]) 240 fl = true; 241 if (!fl) 242 return i - 1; 243 NEX(M); 244 } 245 return n; 246 } 247 int main() { 248 int t; 249 scanf("%d", &t); 250 while (t--) { 251 scanf("%d %d", &n, &m); 252 for (int i = 1; i <= n; ++i) { 253 scanf("%d", &a[i]); 254 g[i].clear(); 255 z[i].clear(); 256 d[i] = 0; 257 tmp[i] = 0; 258 s[i] = 0; 259 } 260 for (int i = 1; i <= m; ++i) { 261 scanf("%d %d", &u, &v); 262 ++d[u]; 263 g[u].push_back(v); 264 z[v].push_back(u); 265 } 266 mx = cal(M); 267 if (mx < n) { 268 cout << mx << endl; 269 continue; 270 } 271 r = 0; 272 for (int i = 1; i <= n; ++i) 273 if (!d[i]) 274 q[++r] = i; 275 s[q[1]] = 1; 276 for (int i = 1; i <= r; ++i) { 277 s[q[i]] %= M; 278 for (auto it : z[q[i]]) { 279 --d[it]; 280 s[it] += s[q[i]]; 281 if (!d[it]) 282 q[++r] = it; 283 } 284 } 285 long long ans = n; 286 for (int i = 1; i <= n; ++i) 287 ans = (ans + s[i] * b[i]) % M; 288 cout << ans << endl; 289 } 290 } 291 ``` 292 293 Tutorial is loading... 294 295 **solution** 296 297 ``` 298 #include<bits/stdc++.h> 299 using namespace std; 300 const int N=500005,inf=2147483647,M=998244353; 301 int n,i,t,f[N],vis[N]; 302 char c[N]; 303 int main(){ 304 for(int i=1;i<=1000;++i){ 305 for(int j=0;j<=i-2;++j) 306 vis[f[j]^f[i-2-j]]=1; 307 int j; 308 for(j=0;vis[j];++j); 309 f[i]=j; 310 for(int j=0;j<=i;++j) 311 vis[j]=0; 312 } 313 for(int i=1001;i<N;++i) 314 f[i]=f[i-34]; 315 scanf("%d",&t); 316 while(t--){ 317 scanf("%d",&n); 318 scanf("%s",c+1); 319 int s=0; 320 for(int i=1;i<=n;++i) 321 if(c[i]=='R') 322 ++s; 323 else 324 --s; 325 if(s>0) 326 puts("Alice"); 327 if(s<0) 328 puts("Bob"); 329 if(s==0){ 330 int ans=0; 331 for(int i=1;i<=n;){ 332 int j=i+1; 333 for(;j<=n&&c[j]!=c[j-1];++j); 334 ans^=f[j-i]; 335 i=j; 336 } 337 puts(ans?"Alice":"Bob"); 338 } 339 } 340 } 341 ``` 342 343 Tutorial is loading... 344 345 **solution** 346 347 ``` 348 #include<bits/stdc++.h> 349 using namespace std; 350 const int M1=998244353,M2=1004535809,M3=469762049,E=524288,N=200005; 351 struct poly{ 352 const int M; 353 poly(int _M):M(_M){} 354 int R[N*4]; 355 long long qpow(long long a,long long b){ 356 long long ans=1; 357 while(b){ 358 if(b&1) 359 ans=ans*a%M; 360 a=a*a%M; 361 b>>=1; 362 } 363 return ans; 364 } 365 long long wn[N*4],iwn[N*4],inv[N*4],fac[N*4],ifac[N*4]; 366 void init(int E,int g){ 367 int i; 368 iwn[E/2]=wn[E/2]=1; 369 long long s1=qpow(g,(M-1)/E); 370 long long s2=qpow(s1,M-2); 371 for(i=E/2+1;i<E;++i){ 372 wn[i]=wn[i-1]*s1%M; 373 iwn[i]=iwn[i-1]*s2%M; 374 } 375 for(i=E/2-1;i;--i){ 376 wn[i]=wn[i<<1]; 377 iwn[i]=iwn[i<<1]; 378 } 379 ifac[0]=fac[0]=inv[1]=1; 380 for(i=2;i<E;++i) 381 inv[i]=inv[M%i]*(M-M/i)%M; 382 for(i=1;i<E;++i){ 383 ifac[i]=inv[i]*ifac[i-1]%M; 384 fac[i]=fac[i-1]*i%M; 385 } 386 } 387 unsigned long long ccc[N*4]; 388 void NTT(long long *f,int lim,int op){ 389 int i,j,k; 390 for(i=0;i<lim;++i){ 391 R[i]=(R[i>>1]>>1)|(i&1?lim>>1:0); 392 if(R[i]<i) 393 swap(f[R[i]],f[i]); 394 } 395 for(i=0;i<lim;++i) 396 ccc[i]=(f[i]%M+M)%M; 397 for(i=1;i<lim;i<<=1) 398 for(j=0;j<lim;j+=(i<<1)) 399 for(k=j;k<j+i;++k){ 400 long long w=(op==1?wn[k-j+i]:iwn[k-j+i]); 401 unsigned long long p=ccc[k+i]*w%M; 402 ccc[k+i]=ccc[k]+M-p; 403 ccc[k]+=p; 404 } 405 for(i=0;i<lim;++i) 406 f[i]=ccc[i]%M; 407 if(op==-1){ 408 long long inv=qpow(lim,M-2); 409 for(i=0;i<lim;++i) 410 f[i]=f[i]*inv%M; 411 } 412 } 413 long long ta[N*4],tb[N*4]; 414 void mult(long long *a,int n,long long *b,int m,long long *c){ 415 int lim=1; 416 while(lim<n+m) 417 lim<<=1; 418 copy(a,a+n,ta); 419 copy(b,b+m,tb); 420 for(int i=n;i<lim;++i) 421 ta[i]=0; 422 for(int i=m;i<lim;++i) 423 tb[i]=0; 424 NTT(ta,lim,1); 425 NTT(tb,lim,1); 426 for(int i=0;i<lim;++i) 427 ta[i]=ta[i]*tb[i]%M; 428 NTT(ta,lim,-1); 429 copy(ta,ta+lim,c); 430 } 431 }X(M1),Y(M2),Z(M3); 432 int n,m,o[N],t,tn; 433 long long a[N],b[N],c[N],d[N*4],e[N],f[N*4],ss[N],td[N],tf[N]; 434 bool fl[N],zz; 435 vector<int> ans; 436 long long cal(int l,int r){ 437 return 1ll*(l+r)*(r-l+1)/2; 438 } 439 long long cal2(int u,int v){ 440 return 1ll*((v-u)/2+1)*(u+v)/2; 441 } 442 bool iok(int n,int p,int q){ 443 long long ss=q+1ll*(n/2)*(n/2+1); 444 p=p+(n/2+1); 445 long long mn=cal(0,p-1),mx=cal(n-p+1,n); 446 if(mn<=ss&&ss<=mx){ 447 for(int i=n;i<n+m-2;++i) 448 if(td[i]!=tf[i-n+1]&&td[i]!=tf[i-n+1]-1) 449 return false; 450 ss-=mn; 451 for(int i=n;i<n+m-2;++i) 452 if(td[i]!=tf[i-n+1]) 453 ans.push_back(i+2); 454 fill(fl,fl+1+n,0); 455 for(int i=0;i<p;++i) 456 fl[(ss/p+(i>=p-ss%p)+i)]=1; 457 for(int i=0;i<=n;++i) 458 if(fl[i]^(i&1)^1) 459 if(n+1-i<=tn) 460 ans.push_back(n+1-i); 461 zz=true; 462 return true; 463 } 464 return false; 465 } 466 void OT(){ 467 if(!zz) 468 puts("-1"); 469 else{ 470 printf("%d\n",ans.size()); 471 for(auto it:ans) 472 printf("%d ",it); 473 printf("\n"); 474 } 475 } 476 void judgement(poly &v,long long *c,long long *e){ 477 for(int i=0;i<n-2;++i) 478 d[i]=(c[i+1]+c[i+2])%v.M; 479 for(int i=0;i<m-2;++i) 480 f[i]=(e[i+1]+e[i+2])%v.M; 481 reverse(f,f+m-2); 482 long long s=0; 483 for(int i=0;i<m-2;++i) 484 s+=(f[i]*f[i]-f[i])%v.M; 485 for(int i=1;i<=n-2;++i) 486 ss[i]=(ss[i-1]+d[i-1]*(d[i-1]+1))%v.M; 487 v.mult(d,n-2,f,m-2,d); 488 for(int i=m-3;i<n-2;++i) 489 if((s+ss[i+1]-ss[i-m+3]-2*d[i])%v.M!=0) 490 o[i-m+4]=0; 491 } 492 int main(){ 493 X.init(E,3); 494 Y.init(E,3); 495 Z.init(E,3); 496 scanf("%d",&t); 497 while(t--){ 498 scanf("%d",&n); 499 tn=n; 500 for(int i=1;i<=n;++i) 501 scanf("%lld",&a[i]); 502 scanf("%d",&m); 503 for(int i=1;i<=m;++i) 504 scanf("%lld",&b[i]); 505 for(int i=1;i<n;++i) 506 c[i]=a[i]+a[i+1]; 507 for(int i=1;i<m;++i) 508 e[i]=b[i]+b[i+1]; 509 fill(o,o+1+n,0); 510 ans.clear(); 511 for(int i=1;i<=n;++i) 512 o[i]=1; 513 if(m>2){ 514 for(int i=0;i<n-2;++i) 515 td[i+1]=c[i+1]+c[i+2]; 516 for(int i=0;i<m-2;++i) 517 tf[i+1]=e[i+1]+e[i+2]; 518 judgement(X,c,e); 519 judgement(Y,c,e); 520 judgement(Z,c,e); 521 } 522 else 523 for(int i=1;i<=n;++i) 524 o[i]=1; 525 int x=-1; 526 zz=false; 527 if(m==1){ 528 for(int i=1;i<=n;++i) 529 if(-cal2(0,i/2*2)<=b[1]-a[i]&&b[1]-a[i]<=cal2(1,(i-1)/2*2+1)){ 530 for(int j=-(i/2+1);j<=(i+1)/2;++j) 531 if(iok(i,j,b[1]-a[i])) 532 break; 533 break; 534 } 535 } 536 else 537 for(int i=1;i+m-1<=n;++i) 538 if(o[i]&&iok(i,(a[i]+a[i+1])-(b[1]+b[2]),b[1]-a[i])) 539 break; 540 OT(); 541 } 542 } 543 ``` 544 545 Tutorial is loading... 546 547 **solution** 548 549 ``` 550 #include<bits/stdc++.h> 551 using namespace std; 552 const int N=200005,E=15000005; 553 const long long inf=1000000000000000000ll; 554 int n,M,mi[5005][5005]; 555 long long fac[N],inv[N],ans; 556 long long C(int n,int m){ 557 return fac[n]*inv[m]%M*inv[n-m]%M; 558 } 559 long long qpow(long long a,long long b){ 560 long long s=a,ans=1; 561 while(b){ 562 if(b&1) 563 ans=ans*s%M; 564 s=s*s%M; 565 b>>=1; 566 } 567 return ans; 568 } 569 int main(){ 570 cin>>n>>M; 571 fac[0]=inv[0]=inv[1]=1; 572 for(int i=2;i<=n;++i) 573 inv[i]=inv[M%i]*(M-M/i)%M; 574 for(int i=1;i<=n;++i){ 575 inv[i]=inv[i-1]*inv[i]%M; 576 fac[i]=fac[i-1]*i%M; 577 } 578 long long s1=1; 579 for(int i=0;i<=n;++i){ 580 mi[i][0]=1; 581 for(int j=1;j<=n;++j) 582 mi[i][j]=1ll*mi[i][j-1]*i%M; 583 } 584 for(int j=1;2*j<=n;++j){ 585 s1=s1*(n-1)%M; 586 for(int i=0;i<=n-2*j;++i) 587 ans=(ans+C(n,i)*fac[n-i]%M*s1%M*mi[n-i-j][i]%M*C(n-i-j-1,j-1)%M*inv[j])%M; 588 } 589 cout<<ans<<endl; 590 } 591 ``` 592 593 Tutorial is loading... 594 595 **solution** 596 597 ``` 598 #include<bits/stdc++.h> 599 using namespace std; 600 const int N=100005,inf=2147483647; 601 const long long sq5=200717101; 602 int M; 603 namespace poly{ 604 int R[N*4]; 605 long long qpow(long long a,long long b){ 606 long long ans=1; 607 while(b){ 608 if(b&1) 609 ans=ans*a%M; 610 a=a*a%M; 611 b>>=1; 612 } 613 return ans; 614 } 615 long long wn[N*4],iwn[N*4],inv[N*4],fac[N*4],ifac[N*4],g; 616 void init(int E){ 617 int i; 618 iwn[E/2]=wn[E/2]=1; 619 long long s1=qpow(g,(M-1)/E); 620 long long s2=qpow(s1,M-2); 621 for(i=E/2+1;i<E;++i){ 622 wn[i]=wn[i-1]*s1%M; 623 iwn[i]=iwn[i-1]*s2%M; 624 } 625 for(i=E/2-1;i;--i){ 626 wn[i]=wn[i<<1]; 627 iwn[i]=iwn[i<<1]; 628 } 629 ifac[0]=fac[0]=inv[1]=1; 630 for(i=2;i<E;++i) 631 inv[i]=inv[M%i]*(M-M/i)%M; 632 for(i=1;i<E;++i){ 633 ifac[i]=inv[i]*ifac[i-1]%M; 634 fac[i]=fac[i-1]*i%M; 635 } 636 } 637 unsigned long long ccc[N*4]; 638 void NTT(long long *f,int lim,int op){ 639 int i,j,k; 640 for(i=0;i<lim;++i){ 641 R[i]=(R[i>>1]>>1)|(i&1?lim>>1:0); 642 if(R[i]<i) 643 swap(f[R[i]],f[i]); 644 } 645 for(i=0;i<lim;++i) 646 ccc[i]=(f[i]%M+M)%M; 647 for(i=1;i<lim;i<<=1) 648 for(j=0;j<lim;j+=(i<<1)) 649 for(k=j;k<j+i;++k){ 650 long long w=(op==1?wn[k-j+i]:iwn[k-j+i]); 651 unsigned long long p=ccc[k+i]*w%M; 652 ccc[k+i]=ccc[k]+M-p; 653 ccc[k]+=p; 654 } 655 for(i=0;i<lim;++i) 656 f[i]=ccc[i]%M; 657 if(op==-1){ 658 long long inv=qpow(lim,M-2); 659 for(i=0;i<lim;++i) 660 f[i]=f[i]*inv%M; 661 } 662 } 663 long long ta[N*4],tb[N*4]; 664 void mult(long long *a,int n,long long *b,int m,long long *c){ 665 int lim=1; 666 while(lim<n+m) 667 lim<<=1; 668 copy(a,a+n,ta); 669 copy(b,b+m,tb); 670 for(int i=n;i<lim;++i) 671 ta[i]=0; 672 for(int i=m;i<lim;++i) 673 tb[i]=0; 674 NTT(ta,lim,1); 675 NTT(tb,lim,1); 676 for(int i=0;i<lim;++i) 677 ta[i]=ta[i]*tb[i]%M; 678 NTT(ta,lim,-1); 679 copy(ta,ta+lim,c); 680 } 681 long long tmp[N*4],tans[N*4]; 682 void Getinv(long long *a,long long *ans,int lim){ 683 ans[0]=qpow(a[0],M-2); 684 for(int i=1;i<lim;i<<=1){ 685 for(int j=i;j<(i<<2);++j) 686 ans[j]=tans[j]=tmp[j]=0; 687 for(int j=0;j<(i<<1);++j) 688 tmp[j]=a[j]; 689 for(int j=0;j<i;++j) 690 tans[j]=ans[j]; 691 NTT(tmp,i<<2,1); 692 NTT(tans,i<<2,1); 693 for(int j=0;j<(i<<2);++j) 694 tmp[j]=tmp[j]*tans[j]%M*tans[j]%M; 695 NTT(tmp,i<<2,-1); 696 for(int j=0;j<(i<<1);++j) 697 ans[j]=(2*ans[j]-tmp[j])%M; 698 } 699 } 700 long long tinv[N*4]; 701 void Getln(long long *a,long long *ans,int n){ 702 for(int i=0;i<n-1;++i) 703 ans[i]=a[i+1]*(i+1)%M; 704 Getinv(a,tinv,n); 705 mult(ans,n-1,tinv,n,ans); 706 for(int i=n;i>=1;--i) 707 ans[i]=ans[i-1]*inv[i]%M; 708 ans[0]=0; 709 } 710 long long tln[N*4]; 711 void Getexp(long long *a,long long *ans,int n){ 712 ans[0]=1; 713 for(int i=1;i<n;i<<=1){ 714 for(int j=i;j<(i<<1);++j) 715 ans[j]=0; 716 Getln(ans,tln,i<<1); 717 for(int j=0;j<(i<<1);++j) 718 tln[j]=-tln[j]+a[j]; 719 ++tln[0]; 720 mult(ans,i,tln,i<<1,ans); 721 } 722 } 723 void Getroot(long long *a,long long *ans,int n){ 724 ans[0]=1; 725 for(int i=1;i<n;i<<=1){ 726 fill(ans+i,ans+(i<<1),0); 727 Getinv(ans,tinv,i<<1); 728 mult(tinv,i<<1,a,i<<1,tinv); 729 for(int j=0;j<(i<<1);++j) 730 ans[j]=(ans[j]+tinv[j])*inv[2]%M; 731 } 732 } 733 long long ttln[N*4]; 734 void Getpow(long long *a,long long *ans,int n,int m){ 735 Getln(a,ttln,m); 736 for(int i=0;i<m;++i) 737 ttln[i]=ttln[i]*n%M; 738 Getexp(ttln,ans,m); 739 } 740 }; 741 int n,m; 742 long long f[N*4],g[N*4],h[N*4],hd[N*4],tmp[N*4],eh[N*4],tmp2[N*4],inv[N*4]; 743 void Newton(int lim){ 744 f[0]=f[1]=0; 745 for(int i=2;i<lim;i<<=1){ 746 poly::Getexp(f,g,i<<1); 747 for(int j=(i<<1)-1;j>=1;--j) 748 g[j]=g[j-1]; 749 g[0]=0; 750 for(int j=0;j<(i<<1);++j) 751 h[j]=(f[j]+g[j])%M; 752 poly::Getexp(h,eh,i<<1); 753 poly::mult(eh,i<<1,h,i<<1,tmp); 754 ++h[0]; 755 ++g[0]; 756 poly::mult(g,i<<1,h,i<<1,tmp2); 757 poly::mult(tmp2,i<<1,eh,i<<1,tmp2); 758 for(int j=(i<<1);j>=1;--j){ 759 tmp2[j]=-tmp2[j-1]; 760 tmp[j]=-tmp[j-1]; 761 } 762 tmp2[0]=1; 763 for(int j=0;j<(i<<1);++j) 764 tmp[j]=(tmp[j]+f[j])%M; 765 poly::Getinv(tmp2,inv,i<<1); 766 poly::mult(inv,i<<1,tmp,i<<1,h); 767 for(int j=0;j<(i<<1);++j) 768 f[j]=(f[j]-h[j])%M; 769 } 770 } 771 long long rt[N*4],X[N*4],Y[N*4],p1[N*4],p2[N*4],p[N*4],e1[N*4],e2[N*4]; 772 long long fd[N*4],gd[N*4],as[N*4],ans[N*4],as2[N*4]; 773 int lim=1; 774 int main(){ 775 cin>>n>>M; 776 int tmpp=M-1; 777 vector<int> dz; 778 for(int i=2;i*i<=tmpp;++i) 779 while(tmpp%i==0){ 780 tmpp/=i; 781 dz.push_back(i); 782 } 783 if(tmpp!=1) 784 dz.push_back(tmpp); 785 for(int i=2;i<M;++i){ 786 int z=M-1; 787 bool fl=true; 788 for(auto it:dz) 789 if(poly::qpow(i,z/it)==1){ 790 fl=false; 791 break; 792 } 793 if(fl){ 794 poly::g=i; 795 break; 796 } 797 } 798 poly::init(262144); 799 ++n; 800 while(lim<=n*2) 801 lim<<=1; 802 Newton(n+1); 803 memset(inv,0,sizeof(inv)); 804 poly::Getexp(f,g,n+1); 805 for(int j=n;j>=1;--j) 806 g[j]=g[j-1]; 807 g[0]=0; 808 for(int j=0;j<=n;++j) 809 h[j]=(f[j]+g[j])%M; 810 poly::Getexp(h,eh,n+1); 811 for(int j=1;j<=n;++j) 812 tmp[j]=-eh[j-1]; 813 tmp[0]=1; 814 poly::Getln(tmp,as2,n+1); 815 for(int j=1;j<=n;++j) 816 as2[j]=(as2[j]-f[j])%M; 817 poly::mult(eh,n+1,h,n+1,X); 818 for(int i=0;i<=n;++i) 819 eh[i]=(X[i]+eh[i])%M; 820 for(int i=n;i>=1;--i){ 821 eh[i]=eh[i-1]; 822 Y[i]=eh[i]; 823 } 824 eh[0]=0; 825 poly::mult(eh,n+1,g,n+1,eh); 826 for(int i=1;i<=n;++i) 827 h[i]=(-eh[i]-Y[i])%M; 828 h[0]=1; 829 poly::Getln(h,as,n+1); 830 for(int i=0;i<=n;++i) 831 as[i]=(-as[i]+as2[i])%M; 832 poly::Getexp(as,ans,n+1); 833 --n; 834 for(int i=1;i<=n;++i) 835 printf("%lld\n",(ans[i]*poly::fac[i]%M+M)%M); 836 } 837 ```