2240.md (31938B)
1 Source: https://codeforces.com/blog/entry/154788 2 3 Thanks everybody for participating in the round! 4 5 ### [Div2A. Another Popcount Problem](https://codeforces.com/contest/2240/problem/A) 6 7 Author: [wangmarui](/profile/wangmarui "Grandmaster wangmarui") Preparation: [wangmarui](/profile/wangmarui "Grandmaster wangmarui") 8 9 **Hint 1** 10 11 Consider each binary bit independently. 12 13 **Hint 2** 14 15 Think about a greedy approach. 16 17 **Solution** 18 19 Tutorial is loading... 20 21 **Code (by wangmarui)** 22 23 ``` 24 /* 25 author: Yuneko 26 27 time: 2026/5/5 28 29 contest: 30 31 Tips: 32 33 RE, MLE? 34 greedy, dp? 35 natural time? 36 map, umap? 37 giveup rating, get score. 38 brute force, right solution? 39 %mod? std/run/maker/checker? 40 add bruteforce? 41 clear? 42 double, long double? 43 O(n)? O(n^2)! 44 make data! 45 46 last but not least. 47 48 bruteforce -> SegTree? 49 Think more. 50 */ 51 //#pragma GCC optimize("Ofast") 52 //#pragma GCC optimize("unroll-loops") 53 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") 54 #include<bits/stdc++.h> 55 using namespace std; 56 //#define map unordered_map 57 #define re register 58 #define ll long long 59 #define cll const ll 60 #define forl(i,a,b) for(re ll (i)=(a);i<=(b);(i)++) 61 #define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--) 62 #define forll(i,a,b,c) for(re ll (i)=(a);i<=(b);(i)+=(c)) 63 #define forrr(i,a,b,c) for(re ll (i)=(a);i>=(b);(i)-=(c)) 64 #define forL(i,a,b,c) for(re ll (i)=(a);((i)<=(b)) && (c);(i)++) 65 #define forR(i,a,b,c) for(re ll (i)=(a);((i)>=(b)) && (c);(i)--) 66 #define forLL(i,a,b,c,d) for(re ll (i)=(a);((i)<=(b)) && (d);(i)+=(c)) 67 #define forRR(i,a,b,c,d) for(re ll (i)=(a);((i)>=(b)) && (d);(i)-=(c)) 68 #define pii pair<ll,ll> 69 #define mid ((l+r)>>1) 70 #define lowbit(x) ((x)&-(x)) 71 #define pb push_back 72 #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 73 #define endl '\n' 74 #define QwQ return 0; 75 #define db long double 76 #define ull unsigned long long 77 #define lcm(x,y) (1ll*(x)/__gcd(x,y)*(y)) 78 #define Sum(x,y) (1ll*((x)+(y))*((y)-(x)+1)/2) 79 #define x first 80 #define y second 81 #define aty cout<<"Yes\n"; 82 #define atn cout<<"No\n"; 83 #define cfy cout<<"YES\n"; 84 #define cfn cout<<"NO\n"; 85 #define xxy cout<<"yes\n"; 86 #define xxn cout<<"no\n"; 87 #define printcf(x) x?cout<<"YES\n":cout<<"NO\n"; 88 #define printat(x) x?cout<<"Yes\n":cout<<"No\n"; 89 #define printxx(x) x?cout<<"yes\n":cout<<"no\n"; 90 #define maxqueue priority_queue<ll> 91 #define minqueue priority_queue<ll,vector<ll>,greater<ll>> 92 #define bug1 cout<<"bug1,AWaDa?\n"; 93 #define bug2 cout<<"bug2,AWaDa!\n"; 94 #define bug3 cout<<"bug3,AKTang?\n"; 95 #define bug4 cout<<"bug4,AKTang!\n"; 96 #define IM (ll)1e9 97 #define LM (ll)1e18 98 #define MIM (ll)-1e9 99 #define MLM (ll)-1e18 100 #define sort stable_sort 101 ll rd(ll&x){cin>>x;return x;}ll rd(){ll x;cin>>x;return x;} 102 ll pw(ll x,ll y,ll mod){if(mod==1)return 0;if(y==0)return 1;if(x==0)return 0;ll an=1,tmp=x;while(y){if(y&1)an=(an*tmp)%mod;tmp=(tmp*tmp)%mod;y>>=1;}return an;} 103 ll pw(ll x){return 1ll<<x;} 104 template<typename T1,typename T2>bool Max(T1&x,T2 y){if(y>x)return x=y,1;return 0;}template<typename T1,typename T2>bool Min(T1&x,T2 y){if(y<x)return x=y,1;return 0;}ll Ss=chrono::steady_clock::now().time_since_epoch().count();mt19937_64 Apple(Ss);ll rand_lr(ll l,ll r){return Apple()%(r-l+1)+l;} 105 cll mod=1e9+7,N=300010;ll fac[N],inv[N];void init(){fac[0]=1;forl(i,1,N-5)fac[i]=i*fac[i-1],fac[i]%=mod;inv[N-5]=pw(fac[N-5],mod-2,mod);forr(i,N-5,1)inv[i-1]=inv[i]*i%mod;}ll C(ll n,ll m){if(n<m || m<0)return 0;return (fac[n]%mod)*(inv[n-m]*inv[m]%mod)%mod;} 106 void add(ll&x,ll y){x=((x+y)%mod+mod)%mod;}void del(ll&x,ll y){x=(x%mod-y%mod+mod)%mod;} 107 ll _t_; 108 struct BIT{ 109 ll maxn; 110 ll tree[1000010]; 111 void clear(ll l){ 112 forl(i,0,l) 113 tree[i]=0; 114 } 115 void add(ll x,ll y){ 116 for(;x<=maxn;x+=lowbit(x)) 117 tree[x]+=y; 118 } 119 ll query(ll x){ 120 ll S=0; 121 for(;x;x-=lowbit(x)) 122 S+=tree[x]; 123 return S; 124 } 125 ll query(ll l,ll r){ 126 return query(r)-query(l-1); 127 } 128 }; 129 ll lg[1000010]; 130 void Init(){ 131 forl(i,2,1e6+5) 132 lg[i]=lg[i>>1]+1; 133 } 134 //xw 135 ll n,m; 136 ll ans; 137 //st 138 void _clear(){} 139 void solve() 140 { 141 _clear(); 142 cin>>n>>m; 143 forl(i,0,30) 144 { 145 ll num=min(n/pw(i),m); 146 ans+=num,n-=num*pw(i); 147 } 148 cout<<ans<<endl; 149 ans=0; 150 } 151 int main() 152 { 153 Init(); 154 // freopen("tst.txt","r",stdin); 155 // freopen("sans.txt","w",stdout); 156 IOS; 157 _t_=1; 158 cin>>_t_; 159 while(_t_--) 160 solve(); 161 QwQ; 162 } 163 ``` 164 165 ### [Div2B. AI Finds Nothing Here](https://codeforces.com/contest/2240/problem/B) 166 167 Author: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526") Preparation: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526") 168 169 **Hint 1** 170 171 Try some special cases, such as $r=c=2$, $n=r$, or $m=c$, etc. 172 173 **Solution** 174 175 In terms of systems of equations, the given problem fixes for us the parities of at most (and exactly) $(n-r+1)\cdot(m-c+1)$ cells (by giving us a system of equations to solve with that many equations). What this means is that, if we are to fill an upper border of thickness $r-1$ and a left border of thickness of $c-1$, then every cell from that point onward is determined uniquely by some equation (Tip: imagine how this pans out for a $2\times2$ matrix; after filling the first row and left column arbitrarily, cell (2,2) is uniquely determined, then (2,3), and so on). 176 177 Therefore, the answer is $2^{nm - (n-r+1)(m-c+1)}$. 178 179 **Code (by Gold14526)** 180 181 ``` 182 #include<bits/stdc++.h> 183 #define cint const int 184 #define uint unsigned int 185 #define cuint const unsigned int 186 #define ll long long 187 #define cll const long long 188 #define ull unsigned long long 189 #define cull const unsigned long long 190 using namespace std; 191 namespace FastIO 192 { 193 const int BUF_SIZE=1<<20; 194 char in_buf[BUF_SIZE],out_buf[BUF_SIZE]; 195 char* in_ptr=in_buf+BUF_SIZE; 196 char* out_ptr=out_buf; 197 char get_char() 198 { 199 if(in_ptr==in_buf+BUF_SIZE) 200 { 201 in_ptr=in_buf; 202 fread(in_buf,1,BUF_SIZE,stdin); 203 } 204 return *in_ptr++; 205 } 206 void put_char(char c) 207 { 208 if(out_ptr==out_buf+BUF_SIZE) 209 { 210 fwrite(out_buf,1,BUF_SIZE,stdout); 211 out_ptr=out_buf; 212 } 213 *out_ptr++=c; 214 } 215 struct Flusher 216 { 217 ~Flusher() 218 { 219 if(out_ptr!=out_buf) 220 { 221 fwrite(out_buf,1,out_ptr-out_buf,stdout); 222 } 223 } 224 } flusher; 225 } 226 #define getchar FastIO::get_char 227 #define putchar FastIO::put_char 228 inline int read() 229 { 230 int x=0; 231 bool zf=1; 232 char ch=getchar(); 233 while(ch<'0'||ch>'9') 234 { 235 if(ch=='-') 236 { 237 zf=0; 238 } 239 ch=getchar(); 240 } 241 while(ch>='0'&&ch<='9') 242 { 243 x=(x<<1)+(x<<3)+(ch^48); 244 ch=getchar(); 245 } 246 return zf?x:-x; 247 } 248 void print(cint x) 249 { 250 if(x==0) 251 { 252 putchar('0'); 253 return; 254 } 255 char buf[12]; 256 int len=0,y=x; 257 if(y<0) 258 { 259 putchar('-'); 260 y=-y; 261 } 262 while(y) 263 { 264 buf[len++]=(y%10)+'0'; 265 y/=10; 266 } 267 while(len--) 268 { 269 putchar(buf[len]); 270 } 271 } 272 inline void princh(cint x,const char ch) 273 { 274 print(x); 275 putchar(ch); 276 } 277 cint mod=998244353; 278 int n,m,r,c; 279 int qpow(int x,int y) 280 { 281 int res=1; 282 while(y) 283 { 284 if(y&1)res=1ll*res*x%mod; 285 x=1ll*x*x%mod; 286 y>>=1; 287 } 288 return res; 289 } 290 void solve() 291 { 292 n=read(); 293 m=read(); 294 r=read(); 295 c=read(); 296 princh(qpow(2,(1ll*n*(c-1)+1ll*m*(r-1)-1ll*(c-1)*(r-1))%(mod-1)),'\n'); 297 } 298 int main() 299 { 300 // freopen(".in","r",stdin); 301 // freopen(".out","w",stdout); 302 int T=read(); 303 while(T--)solve(); 304 return 0; 305 } 306 ``` 307 308 ### [Div1A. Nim Game Is XOR Game](https://codeforces.com/contest/2239/problem/A) 309 310 Author: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526") Preparation: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526") 311 312 **Hint 1** 313 314 Try working through some cases by hand. You may notice that whenever there is more than one non-zero number, the first player wins. Then think about why this is true. 315 316 **Solution** 317 318 Tutorial is loading... 319 320 **Code (by Gold14526)** 321 322 ``` 323 #include<bits/stdc++.h> 324 #define cint const int 325 #define uint unsigned int 326 #define cuint const unsigned int 327 #define ll long long 328 #define cll const long long 329 #define ull unsigned long long 330 #define cull const unsigned long long 331 using namespace std; 332 namespace FastIO 333 { 334 const int BUF_SIZE=1<<20; 335 char in_buf[BUF_SIZE],out_buf[BUF_SIZE]; 336 char* in_ptr=in_buf+BUF_SIZE; 337 char* out_ptr=out_buf; 338 char get_char() 339 { 340 if(in_ptr==in_buf+BUF_SIZE) 341 { 342 in_ptr=in_buf; 343 fread(in_buf,1,BUF_SIZE,stdin); 344 } 345 return *in_ptr++; 346 } 347 void put_char(char c) 348 { 349 if(out_ptr==out_buf+BUF_SIZE) 350 { 351 fwrite(out_buf,1,BUF_SIZE,stdout); 352 out_ptr=out_buf; 353 } 354 *out_ptr++=c; 355 } 356 struct Flusher 357 { 358 ~Flusher() 359 { 360 if(out_ptr!=out_buf) 361 { 362 fwrite(out_buf,1,out_ptr-out_buf,stdout); 363 } 364 } 365 } flusher; 366 } 367 #define getchar FastIO::get_char 368 #define putchar FastIO::put_char 369 inline int read() 370 { 371 int x=0; 372 bool zf=1; 373 char ch=getchar(); 374 while(ch<'0'||ch>'9') 375 { 376 if(ch=='-') 377 { 378 zf=0; 379 } 380 ch=getchar(); 381 } 382 while(ch>='0'&&ch<='9') 383 { 384 x=(x<<1)+(x<<3)+(ch^48); 385 ch=getchar(); 386 } 387 return zf?x:-x; 388 } 389 void print(cint x) 390 { 391 if(x==0) 392 { 393 putchar('0'); 394 return; 395 } 396 char buf[12]; 397 int len=0,y=x; 398 if(y<0) 399 { 400 putchar('-'); 401 y=-y; 402 } 403 while(y) 404 { 405 buf[len++]=(y%10)+'0'; 406 y/=10; 407 } 408 while(len--) 409 { 410 putchar(buf[len]); 411 } 412 } 413 inline void princh(cint x,const char ch) 414 { 415 print(x); 416 putchar(ch); 417 } 418 cint N=1e6; 419 int n,a[N+1],s,ans; 420 void solve() 421 { 422 n=read(); 423 s=0; 424 ans=0; 425 for(int i=1;i<=n;++i)s^=(a[i]=read()); 426 if(n==1) 427 { 428 princh(0,'\n'); 429 return; 430 } 431 if(!s) 432 { 433 princh(1,'\n'); 434 return; 435 } 436 for(int i=1;i<=n;++i) 437 { 438 if((s^a[i])<a[i])++ans; 439 } 440 princh(ans,'\n'); 441 } 442 int main() 443 { 444 // freopen(".in","r",stdin); 445 // freopen(".out","w",stdout); 446 int T=read(); 447 while(T--)solve(); 448 return 0; 449 } 450 ``` 451 452 ### [Div1B. Decidophobia](https://codeforces.com/contest/2239/problem/B) 453 454 Author: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526") Preparation: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526") 455 456 **Hint 1** 457 458 How does everyone’s contribution change when you give a gift to someone? 459 460 **Solution** 461 462 Tutorial is loading... 463 464 **Code (by Gold14526)** 465 466 ``` 467 #include<bits/stdc++.h> 468 #define cint const int 469 #define uint unsigned int 470 #define cuint const unsigned int 471 #define ll long long 472 #define cll const long long 473 #define ull unsigned long long 474 #define cull const unsigned long long 475 #define sh short 476 #define csh const short 477 #define ush unsigned short 478 #define cush const unsigned short 479 using namespace std; 480 namespace FastIO 481 { 482 const int BUF_SIZE=1<<20; 483 char in_buf[BUF_SIZE],out_buf[BUF_SIZE]; 484 char* in_ptr=in_buf+BUF_SIZE; 485 char* out_ptr=out_buf; 486 char get_char() 487 { 488 if(in_ptr==in_buf+BUF_SIZE) 489 { 490 in_ptr=in_buf; 491 fread(in_buf,1,BUF_SIZE,stdin); 492 } 493 return *in_ptr++; 494 } 495 void put_char(char c) 496 { 497 if(out_ptr==out_buf+BUF_SIZE) 498 { 499 fwrite(out_buf,1,BUF_SIZE,stdout); 500 out_ptr=out_buf; 501 } 502 *out_ptr++=c; 503 } 504 struct Flusher 505 { 506 ~Flusher() 507 { 508 if(out_ptr!=out_buf) 509 { 510 fwrite(out_buf,1,out_ptr-out_buf,stdout); 511 } 512 } 513 } flusher; 514 } 515 #define getchar FastIO::get_char 516 #define putchar FastIO::put_char 517 inline int read() 518 { 519 int x=0; 520 bool zf=1; 521 char ch=getchar(); 522 while(ch<'0'||ch>'9') 523 { 524 if(ch=='-') 525 { 526 zf=0; 527 } 528 ch=getchar(); 529 } 530 while(ch>='0'&&ch<='9') 531 { 532 x=(x<<1)+(x<<3)+(ch^48); 533 ch=getchar(); 534 } 535 return zf?x:-x; 536 } 537 void print(cll x) 538 { 539 if(x==0) 540 { 541 putchar('0'); 542 return; 543 } 544 char buf[20]; 545 int len=0; 546 ll y=x; 547 if(y<0) 548 { 549 putchar('-'); 550 y=-y; 551 } 552 while(y) 553 { 554 buf[len++]=(y%10)+'0'; 555 y/=10; 556 } 557 while(len--) 558 { 559 putchar(buf[len]); 560 } 561 } 562 inline void princh(cll x,const char ch) 563 { 564 print(x); 565 putchar(ch); 566 } 567 cint N=6e5; 568 int n,d; 569 int a[N+1]; 570 ll s[N+1],val[N+1]; 571 ll ans; 572 void solve() 573 { 574 n=read(); 575 d=read(); 576 for(int i=1;i<=n;++i) 577 { 578 a[i]=a[i+n]=a[i+(n<<1)]=read(); 579 } 580 for(int i=1;i<=n*3;++i)s[i]=s[i-1]+a[i]; 581 for(int i=n+1;i<=(n<<1);++i) 582 { 583 val[i-n]=1ll*(d<<1|1)*a[i]-(s[i+d]-s[i-d-1]); 584 } 585 ans=0; 586 for(int i=1;i<=n;++i)ans+=max(0ll,val[i]); 587 princh(ans,'\n'); 588 } 589 int main() 590 { 591 //freopen(".in","r",stdin); 592 //freopen(".out","w",stdout); 593 int T=read(); 594 while(T--)solve(); 595 return 0; 596 } 597 ``` 598 599 ### [Div1C. Revival](https://codeforces.com/contest/2239/problem/C) 600 601 Author: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526") Preparation: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526") 602 603 **Hint 1** 604 605 Consider determining all the numbers from back to front. 606 607 **Hint 2** 608 609 When you determine a number, subtract $1$ from all previous values that are greater than this number. This way, all $p$ values decrease by one, while all $s$ values remain unchanged. Now you only need to solve the problem of determining the last number. 610 611 **Solution** 612 613 Tutorial is loading... 614 615 **Code (by Gold14526)** 616 617 ``` 618 #include<bits/stdc++.h> 619 #define cint const int 620 #define uint unsigned int 621 #define cuint const unsigned int 622 #define ll long long 623 #define cll const long long 624 #define ull unsigned long long 625 #define cull const unsigned long long 626 #define sh short 627 #define csh const short 628 #define ush unsigned short 629 #define cush const unsigned short 630 using namespace std; 631 namespace FastIO 632 { 633 const int BUF_SIZE=1<<20; 634 char in_buf[BUF_SIZE],out_buf[BUF_SIZE]; 635 char* in_ptr=in_buf+BUF_SIZE; 636 char* out_ptr=out_buf; 637 char get_char() 638 { 639 if(in_ptr==in_buf+BUF_SIZE) 640 { 641 in_ptr=in_buf; 642 fread(in_buf,1,BUF_SIZE,stdin); 643 } 644 return *in_ptr++; 645 } 646 void put_char(char c) 647 { 648 if(out_ptr==out_buf+BUF_SIZE) 649 { 650 fwrite(out_buf,1,BUF_SIZE,stdout); 651 out_ptr=out_buf; 652 } 653 *out_ptr++=c; 654 } 655 struct Flusher 656 { 657 ~Flusher() 658 { 659 if(out_ptr!=out_buf) 660 { 661 fwrite(out_buf,1,out_ptr-out_buf,stdout); 662 } 663 } 664 } flusher; 665 } 666 #define getchar FastIO::get_char 667 #define putchar FastIO::put_char 668 inline ll read() 669 { 670 ll x=0; 671 bool zf=1; 672 char ch=getchar(); 673 while(ch<'0'||ch>'9') 674 { 675 if(ch=='-') 676 { 677 zf=0; 678 } 679 ch=getchar(); 680 } 681 while(ch>='0'&&ch<='9') 682 { 683 x=(x<<1)+(x<<3)+(ch^48); 684 ch=getchar(); 685 } 686 return zf?x:-x; 687 } 688 void print(cint x) 689 { 690 if(x==0) 691 { 692 putchar('0'); 693 return; 694 } 695 char buf[12]; 696 int len=0,y=x; 697 if(y<0) 698 { 699 putchar('-'); 700 y=-y; 701 } 702 while(y) 703 { 704 buf[len++]=(y%10)+'0'; 705 y/=10; 706 } 707 while(len--) 708 { 709 putchar(buf[len]); 710 } 711 } 712 inline void princh(cint x,const char ch) 713 { 714 print(x); 715 putchar(ch); 716 } 717 cint N=1e6; 718 int n; 719 ll val[N+1]; 720 char type[N+1]; 721 int ans[N+1]; 722 struct Binary_Index_Tree{ 723 int a[N+1]; 724 void clear() 725 { 726 for(int i=1;i<=n;++i)a[i]=0; 727 } 728 inline void add(cint x,cint y) 729 { 730 for(int i=x;i<=n;i+=(i&-i))a[i]+=y; 731 } 732 inline int ask(cint x) 733 { 734 int s=0; 735 for(int i=x;i;i-=(i&-i))s+=a[i]; 736 return s; 737 } 738 inline int find(int x) 739 { 740 int res=0; 741 for(int len=1<<__lg(n);len;len>>=1) 742 { 743 if(res+len>n)continue; 744 if(a[res+len]<=x) 745 { 746 res+=len; 747 x-=a[res]; 748 } 749 } 750 return res+1; 751 } 752 }T; 753 int lst[N+1]; 754 void solve() 755 { 756 n=read(); 757 T.clear(); 758 for(int i=1;i<=n;++i) 759 { 760 char ch=getchar(); 761 while(ch!='p'&&ch!='s')ch=getchar(); 762 type[i]=ch; 763 val[i]=read(); 764 if(type[i]=='p')ans[i]=val[i]; 765 else val[i]=1ll*i*(i-1)/2-val[i]; 766 } 767 for(int i=1;i<=n;++i)lst[i]=(type[i]=='s'?i:lst[i-1]); 768 for(int i=1;i<=n;++i)T.add(i,1); 769 for(int i=lst[n]+1;i<=n;++i)T.add(ans[i],-1); 770 for(int i=lst[n];i;i=lst[i-1]) 771 { 772 cint p=lst[i-1]; 773 ll d=val[i]-val[p]; 774 for(int j=i-1;j>p;--j) 775 { 776 d-=T.ask(ans[j]-1); 777 T.add(ans[j],-1); 778 } 779 d+=i-p-1; 780 for(int j=i-1;j>p;--j)T.add(ans[j],2); 781 ans[i]=T.find(d); 782 for(int j=i-1;j>p;--j)T.add(ans[j],-2); 783 T.add(ans[i],-1); 784 } 785 for(int i=1;i<=n;++i) 786 { 787 princh(ans[i]," \n"[i==n]); 788 } 789 } 790 int main() 791 { 792 //freopen(".in","r",stdin); 793 //freopen(".out","w",stdout); 794 int T=read(); 795 while(T--)solve(); 796 return 0; 797 } 798 ``` 799 800 ### [Div1D. Hunting the Beast](https://codeforces.com/contest/2239/problem/D) 801 802 Author: [Milkcat2009](/profile/Milkcat2009 "Grandmaster Milkcat2009") Preparation: [Milkcat2009](/profile/Milkcat2009 "Grandmaster Milkcat2009") 803 804 **Hint 1** 805 806 By symmetry, all vertices are equivalent. Therefore, we only need to calculate the number of graphs in which a specific set is successful, and then multiply by $\binom{n}{m}$. 807 808 **Hint 2** 809 810 Let the nodes in the set be key nodes and the remaining nodes be non-key nodes. Consider the condition for the set to be successful and use the Principle of Inclusion-Exclusion to handle these conditions. 811 812 **Hint 3** 813 814 You might need to calculate the following: $n$ vertices form a set of disjoint cycles without self-loops. If there are $k$ cycles, the contribution is $(-1)^k$. Find the sum of contributions over all possible configurations. 815 816 The answer is $1-n$, which you can try to prove. 817 818 **Hint 4** 819 820 Use the Binomial Theorem to simplify the sum. 821 822 **Solution** 823 824 Tutorial is loading... 825 826 **Code (by Milkcat2009)** 827 828 ``` 829 #include <bits/stdc++.h> 830 #define REP(i, l, r) for (int i = (l); i <= (r); ++ i) 831 #define DEP(i, r, l) for (int i = (r); i >= (l); -- i) 832 #define CUP(i, l, r) for (int i = (l); i < (r); ++ i) 833 #define fi first 834 #define se second 835 #define pb emplace_back 836 #define mems(x, v) memset((x), (v), sizeof(x)) 837 #define memc(x, y) memcpy((x), (y), sizeof(x)) 838 #define SZ(x) (int)(x).size() 839 #define ALL(x) (x).begin(), (x).end() 840 #define ppc(x) __builtin_popcount(x) 841 #define ctz(x) __builtin_ctz(x) 842 #define clz(x) __builtin_clz(x) 843 using namespace std; 844 namespace math { 845 typedef long long LL; 846 template <class T> T qpow(T a, LL b) { if (!b) return {1}; T rs = a; b --; for (; b; b >>= 1, a = a * a) if (b & 1) rs = rs * a; return rs; } 847 LL mul(LL a, LL b, LL p) { LL rs = a * b - LL(1.L * a * b / p) * p; rs %= p; if (rs < 0) rs += p; return rs; } 848 template <unsigned P = 0> struct mint { 849 unsigned v; static unsigned mod; mint() = default; 850 template <class T> mint(T x) { x %= (int)getmod(), v = x < 0 ? x + getmod() : x; } 851 constexpr static unsigned getmod() { if (P > 0) return P; else return mod; } 852 static void setmod(unsigned m) { mod = m; } 853 mint operator + () const { return *this; } 854 mint operator - () const { return mint(0) - *this; } 855 mint inv() const { return assert(v), qpow(*this, getmod() - 2); } 856 int val() const { return v; } 857 mint &operator += (const mint &q) { if (v += q.v, v >= getmod()) v -= getmod(); return *this; } 858 mint &operator -= (const mint &q) { if (v -= q.v, v >= getmod()) v += getmod(); return *this; } 859 mint &operator *= (const mint &q) { v = 1ull * v * q.v % getmod(); return *this; } 860 mint &operator /= (const mint &q) { return *this *= q.inv(); } 861 friend mint operator + (mint p, const mint &q) { return p += q; } 862 friend mint operator - (mint p, const mint &q) { return p -= q; } 863 friend mint operator * (mint p, const mint &q) { return p *= q; } 864 friend mint operator / (mint p, const mint &q) { return p /= q; } 865 friend bool operator == (const mint &p, const mint &q) { return p.v == q.v; } 866 friend bool operator != (const mint &p, const mint &q) { return p.v != q.v; } 867 friend bool operator < (const mint &p, const mint &q) { return p.v < q.v; } 868 friend bool operator > (const mint &p, const mint &q) { return p.v > q.v; } 869 friend bool operator <= (const mint &p, const mint &q) { return p.v <= q.v; } 870 friend bool operator >= (const mint &p, const mint &q) { return p.v >= q.v; } 871 friend istream &operator >> (istream &is, mint &a) { LL x; is >> x, a = x; return is; } 872 friend ostream &operator << (ostream &os, const mint &a) { os << a.v; return os; } 873 }; 874 template <> unsigned mint<0>::mod = 998244353; 875 template <typename MI> 876 struct Comb { 877 #define P MI::getmod() 878 vector<MI> fc, ifc; 879 void init(int n) { 880 fc.resize(n + 1), ifc.resize(n + 1), fc[0] = 1; 881 REP(i, 1, n) fc[i] = fc[i - 1] * i; 882 ifc[n] = fc[n].inv(); 883 DEP(i, n, 1) ifc[i - 1] = ifc[i] * i; 884 } 885 MI operator () (LL n, LL m) { 886 if (m > n || m < 0 || n < 0) return 0; 887 if (n < P && m < P) { assert(n < SZ(fc)); return fc[n] * ifc[m] * ifc[n - m]; } 888 return (!n ? 1 : (*this)(n / P, m / P) * (*this)(n % P, m % P)); 889 } 890 #undef P 891 }; 892 namespace Z { 893 const int mod = 998244353; 894 using MI = mint<mod>; using math::qpow; Comb<MI> C; 895 MI fac(int x) { assert(x >= 0 && x < SZ(C.fc)); return C.fc[x]; } 896 MI ifc(int x) { assert(x >= 0 && x < SZ(C.ifc)); return C.ifc[x]; } 897 MI inv(int x) { assert(x && x < SZ(C.fc)); return C.ifc[x] * C.fc[x - 1]; } 898 MI sab(int x, int y) { return (!y ? !x : C(x + y - 1, y - 1)); } 899 } 900 } 901 namespace Milkcat { 902 using namespace math::Z; 903 typedef long long LL; 904 typedef pair<LL, LL> pii; 905 const int N = 1e7 + 5; 906 int n, m, t, v[N]; MI g[N]; 907 void sieve(int n, int k, MI* f) { 908 vector<int> p; fill_n(v + 1, n, 0), f[1] = 1; 909 REP(i, 2, n) { 910 if (!v[i]) p.pb(i), f[i] = qpow((MI)i, k); 911 for (int j : p) { 912 if (i * j <= n) f[i * j] = f[i] * f[j], v[i * j] = 1; 913 if (i * j > n || i % j == 0) break; 914 } 915 } 916 } 917 MI slv2(int n, int m) { 918 MI rs = 0; 919 REP(i, 0, n - m) 920 rs += g[n - i - 1] * C(n - m, i) * (i & 1 ? -1 : 1); 921 return rs * (n - 1); 922 } 923 int main() { 924 cin >> t, C.init(1e6); 925 while (t --) { 926 cin >> n >> m, sieve(n, n - 1, g); 927 cout << slv2(n, m) * C(n, m) << '\n'; 928 } 929 return 0; 930 } 931 } 932 int main() { 933 cin.tie(0)->sync_with_stdio(0); 934 int T = 1; 935 while (T --) Milkcat::main(); 936 return 0; 937 } 938 ``` 939 940 ### [Div1E. The end of this world,](https://codeforces.com/contest/2239/problem/E) 941 942 Author: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526") Preparation: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526") 943 944 **Hint 1** 945 946 Notice that the problem can be transformed as follows: the $i$-th edge appears during the time interval $[\mathrm{low}_i, w_i]$. For each vertex, compute the maximum value of the departure time plus the weight of the destination vertex. 947 948 **Hint 2** 949 950 Consider doing the transitions from back to front. 951 952 **Hint 3** 953 954 We only need to support the following operations: 955 956 * Add and delete edges; 957 * Query the maximum value in a connected component; 958 * Take the max of all weights in a connected component with a given number. 959 960 **Hint 4** 961 962 Consider modifying the dynamic graph connectivity approach. 963 964 **Solution** 965 966 Tutorial is loading... 967 968 **Code (by Gold14526)** 969 970 ``` 971 #include<bits/stdc++.h> 972 #define cint const int 973 #define uint unsigned int 974 #define cuint const unsigned int 975 #define ll long long 976 #define cll const long long 977 #define ull unsigned long long 978 #define cull const unsigned long long 979 using namespace std; 980 namespace FastIO 981 { 982 const int BUF_SIZE=1<<20; 983 char in_buf[BUF_SIZE],out_buf[BUF_SIZE]; 984 char* in_ptr=in_buf+BUF_SIZE; 985 char* out_ptr=out_buf; 986 char get_char() 987 { 988 if(in_ptr==in_buf+BUF_SIZE) 989 { 990 in_ptr=in_buf; 991 fread(in_buf,1,BUF_SIZE,stdin); 992 } 993 return *in_ptr++; 994 } 995 void put_char(char c) 996 { 997 if(out_ptr==out_buf+BUF_SIZE) 998 { 999 fwrite(out_buf,1,BUF_SIZE,stdout); 1000 out_ptr=out_buf; 1001 } 1002 *out_ptr++=c; 1003 } 1004 struct Flusher 1005 { 1006 ~Flusher() 1007 { 1008 if(out_ptr!=out_buf) 1009 { 1010 fwrite(out_buf,1,out_ptr-out_buf,stdout); 1011 } 1012 } 1013 } flusher; 1014 } 1015 #define getchar FastIO::get_char 1016 #define putchar FastIO::put_char 1017 inline int read() 1018 { 1019 int x=0; 1020 bool zf=1; 1021 char ch=getchar(); 1022 while(ch<'0'||ch>'9') 1023 { 1024 if(ch=='-') 1025 { 1026 zf=0; 1027 } 1028 ch=getchar(); 1029 } 1030 while(ch>='0'&&ch<='9') 1031 { 1032 x=(x<<1)+(x<<3)+(ch^48); 1033 ch=getchar(); 1034 } 1035 return zf?x:-x; 1036 } 1037 void print(cint x) 1038 { 1039 if(x==0) 1040 { 1041 putchar('0'); 1042 return; 1043 } 1044 char buf[12]; 1045 int len=0,y=x; 1046 if(y<0) 1047 { 1048 putchar('-'); 1049 y=-y; 1050 } 1051 while(y) 1052 { 1053 buf[len++]=(y%10)+'0'; 1054 y/=10; 1055 } 1056 while(len--) 1057 { 1058 putchar(buf[len]); 1059 } 1060 } 1061 inline void princh(cint x,const char ch) 1062 { 1063 print(x); 1064 putchar(ch); 1065 } 1066 cint N=5e5,M=5e5,H=20; 1067 int n,m; 1068 int val[N+1]; 1069 int eu[M+1],ev[M+1],low[M+1],lim[M+1]; 1070 int tl[M+1],tr[M+1]; 1071 struct dx{ 1072 int idx,val; 1073 }c[M<<1|1]; 1074 struct edge{ 1075 int u,v,l,r; 1076 }; 1077 vector<edge>E,EL[H+1],ER[H+1]; 1078 struct info{ 1079 int t,u; 1080 }mdf[M+1]; 1081 int tag[N+(M<<2|1)],mx[N+(M<<2|1)]; 1082 int fa[N+(M<<2|1)]; 1083 int tot; 1084 int top[N+(M<<2|1)]; 1085 int head[N+(M<<2|1)]; 1086 struct et{ 1087 int to,nxt; 1088 }ve[M<<2|1]; 1089 int ct; 1090 inline void add_edge(cint u,cint v) 1091 { 1092 ve[++ct]={v,head[u]}; 1093 head[u]=ct; 1094 ve[++ct]={u,head[v]}; 1095 head[v]=ct; 1096 } 1097 inline int newv() 1098 { 1099 ++tot; 1100 tag[tot]=-1; 1101 mx[tot]=fa[tot]=0; 1102 return tot; 1103 } 1104 struct stck{ 1105 int a[N+1],t; 1106 inline void clear(){t=0;} 1107 inline int top(){return a[t];} 1108 inline void pop(){--t;} 1109 inline void push(cint x){a[++t]=x;} 1110 inline bool empty(){return (t==0);} 1111 }st; 1112 void dfs(cint u) 1113 { 1114 top[u]=u; 1115 st.clear(); 1116 st.push(u); 1117 while(!st.empty()) 1118 { 1119 cint s=st.top(); 1120 st.pop(); 1121 for(int i=head[s];i;i=ve[i].nxt) 1122 { 1123 cint v=ve[i].to; 1124 if(top[v])continue; 1125 top[v]=u; 1126 st.push(v); 1127 } 1128 } 1129 } 1130 void update(cint h,cint l,cint r,vector<edge>&E,int m,cint vl,cint vr) 1131 { 1132 if(E.empty()) 1133 { 1134 for(int i=1;i<=m;++i) 1135 { 1136 tag[mdf[i].u]=max(tag[mdf[i].u],mx[mdf[i].u]+c[l].val); 1137 } 1138 return; 1139 } 1140 cint mid=l+r>>1; 1141 EL[h].clear(); 1142 ER[h].clear(); 1143 for(int i=vl;i<=vr;++i) 1144 { 1145 head[i]=top[i]=fa[i]=0; 1146 } 1147 ct=0; 1148 for(edge &e:E) 1149 { 1150 if(e.l<=l&&e.r>=r) 1151 { 1152 add_edge(e.u,e.v); 1153 } 1154 else 1155 { 1156 if(e.l<=mid)EL[h].push_back(e); 1157 if(e.r>mid)ER[h].push_back(e); 1158 } 1159 } 1160 for(int i=vl;i<=vr;++i) 1161 { 1162 if(!top[i])dfs(i); 1163 } 1164 if(l==r) 1165 { 1166 for(int i=vl;i<=vr;++i)mx[top[i]]=max(mx[top[i]],mx[i]); 1167 for(int i=1;i<=m;++i) 1168 { 1169 cint u=top[mdf[i].u]; 1170 tag[u]=max(tag[u],mx[u]+c[l].val); 1171 } 1172 for(int i=vl;i<=vr;++i) 1173 { 1174 tag[i]=max(tag[i],tag[top[i]]); 1175 mx[i]=max(mx[i],mx[top[i]]); 1176 } 1177 return; 1178 } 1179 cint tmp=tot; 1180 for(edge &e:ER[h]) 1181 { 1182 cint u=top[e.u],v=top[e.v]; 1183 if(!fa[u])fa[u]=newv(); 1184 if(!fa[v])fa[v]=newv(); 1185 e.u=fa[u]; 1186 e.v=fa[v]; 1187 } 1188 int pm=0; 1189 for(int i=1;i<=m;++i) 1190 { 1191 info &p=mdf[i]; 1192 if(p.t>mid) 1193 { 1194 cint u=top[p.u]; 1195 if(!fa[u])fa[u]=newv(); 1196 p.u=fa[u]; 1197 swap(p,mdf[++pm]); 1198 } 1199 } 1200 for(int i=vl;i<=vr;++i) 1201 { 1202 cint u=fa[top[i]]; 1203 if(u)mx[u]=max(mx[u],mx[i]); 1204 } 1205 update(h+1,mid+1,r,ER[h],pm,tmp+1,tot); 1206 for(int i=vl;i<=vr;++i) 1207 { 1208 cint u=fa[top[i]]; 1209 if(u)mx[i]=max(mx[i],mx[u]),tag[i]=max(tag[i],tag[u]); 1210 } 1211 tot=tmp; 1212 for(int i=vl;i<=vr;++i)fa[i]=0; 1213 for(edge &e:EL[h]) 1214 { 1215 cint u=top[e.u],v=top[e.v]; 1216 if(!fa[u])fa[u]=newv(); 1217 if(!fa[v])fa[v]=newv(); 1218 e.u=fa[u]; 1219 e.v=fa[v]; 1220 } 1221 for(int i=pm+1;i<=m;++i) 1222 { 1223 info &p=mdf[i]; 1224 cint u=top[p.u]; 1225 if(!fa[u])fa[u]=newv(); 1226 p.u=fa[u]; 1227 swap(p,mdf[i-pm]); 1228 } 1229 pm=m-pm; 1230 for(int i=vl;i<=vr;++i) 1231 { 1232 cint u=fa[top[i]]; 1233 if(u)mx[u]=max(mx[u],mx[i]); 1234 } 1235 update(h+1,l,mid,EL[h],pm,tmp+1,tot); 1236 for(int i=vl;i<=vr;++i) 1237 { 1238 cint u=fa[top[i]]; 1239 if(u)mx[i]=max(mx[i],mx[u]),tag[i]=max(tag[i],tag[u]); 1240 } 1241 tot=tmp; 1242 } 1243 void solve() 1244 { 1245 tag[0]=-1; 1246 tot=n=read(); 1247 m=read(); 1248 for(int i=1;i<=n;++i)val[i]=read(),tag[i]=-1,mx[i]=val[i]; 1249 for(int i=1;i<=m;++i) 1250 { 1251 eu[i]=read(),ev[i]=read(),lim[i]=read(),low[i]=read(); 1252 c[i]={i,lim[i]}; 1253 c[i+m]={i+m,low[i]}; 1254 } 1255 sort(c+1,c+(m<<1|1),[&](dx p,dx q){return (p.val==q.val?p.idx>q.idx:p.val<q.val);}); 1256 for(int i=1;i<=(m<<1);++i) 1257 { 1258 if(c[i].idx>m)tl[c[i].idx-m]=i; 1259 else tr[c[i].idx]=i; 1260 } 1261 E.clear(); 1262 for(int i=1;i<=m;++i) 1263 { 1264 E.push_back({eu[i],ev[i],tl[i],tr[i]}); 1265 mdf[i]={tr[i],eu[i]}; 1266 } 1267 if(m)update(0,1,m<<1,E,m,1,n); 1268 for(int i=1;i<=n;++i)princh(tag[i]," \n"[i==n]); 1269 } 1270 int main() 1271 { 1272 // freopen(".in","r",stdin); 1273 // freopen(".out","w",stdout); 1274 int T=read(); 1275 while(T--)solve(); 1276 return 0; 1277 } 1278 ``` 1279 1280 ### [Div1F. Colorful Works](https://codeforces.com/contest/2239/problem/F) 1281 1282 Author: [Milkcat2009](/profile/Milkcat2009 "Grandmaster Milkcat2009") Preparation: [Milkcat2009](/profile/Milkcat2009 "Grandmaster Milkcat2009") 1283 1284 **Hint 1** 1285 1286 Consider the case where $l_i=0$. 1287 1288 **Hint 2** 1289 1290 Just Consider the most straightforward DP approach, and then try to find some patterns. 1291 1292 **Hint 3** 1293 1294 Try transforming the modulo $2$ counting DP into a game and solve it. 1295 1296 **Hint 4** 1297 1298 You should already know the answer for $l_i=0$; try using the Principle of Inclusion-Exclusion to count. 1299 1300 **Hint 5** 1301 1302 Enumerate which element is strictly greater than half of the total sum. 1303 1304 **Hint 6** 1305 1306 You should already know the $O(nm/w)$ algorithm. Consider that, under modulo $2$, we have $(1+x^k)^2=1+x^{2k}$. 1307 1308 **Solution** 1309 1310 Tutorial is loading... 1311 1312 **Code (by Milkcat2009)** 1313 1314 ``` 1315 #include <bits/stdc++.h> 1316 #define REP(i, l, r) for (int i = (l); i <= (r); ++ i) 1317 #define DEP(i, r, l) for (int i = (r); i >= (l); -- i) 1318 #define CUP(i, l, r) for (int i = (l); i < (r); ++ i) 1319 #define fi first 1320 #define se second 1321 #define pb emplace_back 1322 #define mems(x, v) memset((x), (v), sizeof(x)) 1323 #define memc(x, y) memcpy((x), (y), sizeof(x)) 1324 #define SZ(x) (int)(x).size() 1325 #define ALL(x) (x).begin(), (x).end() 1326 #define ppc(x) __builtin_popcount(x) 1327 #define ctz(x) __builtin_ctz(x) 1328 #define clz(x) __builtin_clz(x) 1329 using namespace std; 1330 namespace Milkcat { 1331 typedef long long LL; 1332 typedef pair<LL, LL> pii; 1333 const int N = 2e6 + 5, M = 2e5 + 5; 1334 int n, m, rs, d, p, q, l[N], r[N], c[M]; 1335 bitset<M> f; 1336 int val(int x) { x -= d; return (x >= 0 && x <= m ? f[x] : 0); } 1337 int main() { 1338 cin >> n; 1339 REP(i, 1, n) 1340 cin >> l[i] >> r[i], m = max(m, r[i]); 1341 REP(i, 1, n) { 1342 if (!l[i]) d = min(d + r[i], (int)1e9); 1343 else d = min(d + l[i] - 1, (int)1e9), c[r[i] - l[i] + 1] ++; 1344 } 1345 f = 1; 1346 REP(i, 1, m) { 1347 if (i * 2 <= m) c[i * 2] += c[i] >> 1; 1348 if (c[i] & 1) f ^= f << i; 1349 } 1350 REP(i, 2, m) f[i] = f[i] ^ f[i - 2]; 1351 REP(i, 1, n) { 1352 if (!l[i]) rs ^= val(r[i] * 2 - 2), p ^= r[i] & 1; 1353 else rs ^= val(l[i] + r[i] - 1 - 2), q += ((l[i] & 1) == (r[i] & 1) ? 1 : 2); 1354 } 1355 cout << (rs ^ (!q ? !p : (q < 2))) << '\n'; 1356 REP(i, 1, m) c[i] = 0; 1357 m = rs = d = p = q = 0; 1358 return 0; 1359 } 1360 } 1361 int main() { 1362 cin.tie(0)->sync_with_stdio(0); 1363 int T = 1; cin >> T; 1364 while (T --) Milkcat::main(); 1365 return 0; 1366 } 1367 ```