Thanks everybody for participating in the round!↵
↵
### [Div2A. Another Popcount Problem](https://codeforces.me/contest/2240/problem/A)↵
↵
Author: [user:wangmarui,2026-06-27] Preparation: [user:wangmarui,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
Consider each binary bit independently.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Think about a greedy approach.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2240A]↵
</spoiler>↵
↵
### [Div2B. AI Finds Nothing Here](https://codeforces.me/contest/2240/problem/B)↵
↵
Author: [user:Gold14526,2026-06-27] Preparation: [user:Gold14526,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
Try some special cases, such as $r=c=2$, $n=r$, or $m=c$, etc.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
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).↵
↵
Therefore, the answer is $2^{nm - (n-r+1)(m-c+1)}$.↵
</spoiler>↵
↵
### [Div1A. Nim Game Is XOR Game](https://codeforces.me/contest/2239/problem/A)↵
↵
Author: [user:Gold14526,2026-06-27] Preparation: [user:Gold14526,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239A]↵
</spoiler>↵
↵
### [Div1B. Decidophobia](https://codeforces.me/contest/2239/problem/B)↵
↵
Author: [user:Gold14526,2026-06-27] Preparation: [user:Gold14526,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
How does everyone’s contribution change when you give a gift to someone?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239B]↵
</spoiler>↵
↵
### [Div1C. Revival](https://codeforces.me/contest/2239/problem/C)↵
↵
Author: [user:Gold14526,2026-06-27] Preparation: [user:Gold14526,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
Consider determining all the numbers from back to front.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239C]↵
</spoiler>↵
↵
### [Div1D. Hunting the Beast](https://codeforces.me/contest/2239/problem/D)↵
↵
Author: [user:Milkcat2009,2026-06-27] Preparation: [user:Milkcat2009,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
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}$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
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.↵
↵
The answer is $1-n$, which you can try to prove.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Use the Binomial Theorem to simplify the sum.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239D]↵
</spoiler>↵
↵
### [Div1E. The end of this world,](https://codeforces.me/contest/2239/problem/E<spoiler summary="Code (by wangmarui)">↵
~~~~~↵
/*↵
author: Yuneko↵
↵
time: 2026/5/5↵
↵
contest:↵
↵
Tips:↵
↵
RE, MLE?↵
greedy, dp?↵
natural time?↵
map, umap?↵
giveup rating, get score.↵
brute force, right solution?↵
%mod? std/run/maker/checker?↵
add bruteforce?↵
clear?↵
double, long double?↵
O(n)? O(n^2)!↵
make data!↵
↵
last but not least.↵
↵
bruteforce -> SegTree?↵
Think more.↵
*/↵
//#pragma GCC optimize("Ofast")↵
//#pragma GCC optimize("unroll-loops")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")↵
#include<bits/stdc++.h>↵
using namespace std;↵
//#define map unordered_map↵
#define re register↵
#define ll long long↵
#define cll const ll↵
#define forl(i,a,b) for(re ll (i)=(a);i<=(b);(i)++)↵
#define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--)↵
#define forll(i,a,b,c) for(re ll (i)=(a);i<=(b);(i)+=(c))↵
#define forrr(i,a,b,c) for(re ll (i)=(a);i>=(b);(i)-=(c))↵
#define forL(i,a,b,c) for(re ll (i)=(a);((i)<=(b)) && (c);(i)++)↵
#define forR(i,a,b,c) for(re ll (i)=(a);((i)>=(b)) && (c);(i)--)↵
#define forLL(i,a,b,c,d) for(re ll (i)=(a);((i)<=(b)) && (d);(i)+=(c))↵
#define forRR(i,a,b,c,d) for(re ll (i)=(a);((i)>=(b)) && (d);(i)-=(c))↵
#define pii pair<ll,ll>↵
#define mid ((l+r)>>1)↵
#define lowbit(x) ((x)&-(x))↵
#define pb push_back↵
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);↵
#define endl '\n'↵
#define QwQ return 0;↵
#define db long double↵
#define ull unsigned long long↵
#define lcm(x,y) (1ll*(x)/__gcd(x,y)*(y))↵
#define Sum(x,y) (1ll*((x)+(y))*((y)-(x)+1)/2)↵
#define x first↵
#define y second↵
#define aty cout<<"Yes\n";↵
#define atn cout<<"No\n";↵
#define cfy cout<<"YES\n";↵
#define cfn cout<<"NO\n";↵
#define xxy cout<<"yes\n";↵
#define xxn cout<<"no\n";↵
#define printcf(x) x?cout<<"YES\n":cout<<"NO\n";↵
#define printat(x) x?cout<<"Yes\n":cout<<"No\n";↵
#define printxx(x) x?cout<<"yes\n":cout<<"no\n";↵
#define maxqueue priority_queue<ll>↵
#define minqueue priority_queue<ll,vector<ll>,greater<ll>>↵
#define bug1 cout<<"bug1,AWaDa?\n";↵
#define bug2 cout<<"bug2,AWaDa!\n";↵
#define bug3 cout<<"bug3,AKTang?\n";↵
#define bug4 cout<<"bug4,AKTang!\n";↵
#define IM (ll)1e9↵
#define LM (ll)1e18↵
#define MIM (ll)-1e9↵
#define MLM (ll)-1e18↵
#define sort stable_sort↵
ll rd(ll&x){cin>>x;return x;}ll rd(){ll x;cin>>x;return x;}↵
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;}↵
ll pw(ll x){return 1ll<<x;}↵
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;}↵
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;}↵
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;}↵
ll _t_;↵
struct BIT{↵
ll maxn;↵
ll tree[1000010];↵
void clear(ll l){↵
forl(i,0,l)↵
tree[i]=0;↵
}↵
void add(ll x,ll y){↵
for(;x<=maxn;x+=lowbit(x))↵
tree[x]+=y;↵
}↵
ll query(ll x){↵
ll S=0;↵
for(;x;x-=lowbit(x))↵
S+=tree[x];↵
return S;↵
}↵
ll query(ll l,ll r){↵
return query(r)-query(l-1);↵
}↵
};↵
ll lg[1000010];↵
void Init(){↵
forl(i,2,1e6+5)↵
lg[i]=lg[i>>1]+1;↵
}↵
//xw↵
ll n,m;↵
ll ans;↵
//st↵
void _clear(){}↵
void solve()↵
{↵
_clear();↵
cin>>n>>m;↵
forl(i,0,30)↵
{↵
ll num=min(n/pw(i),m);↵
ans+=num,n-=num*pw(i);↵
}↵
cout<<ans<<endl;↵
ans=0;↵
}↵
int main()↵
{↵
Init();↵
// freopen("tst.txt","r",stdin);↵
// freopen("sans.txt","w",stdout);↵
IOS;↵
_t_=1;↵
cin>>_t_;↵
while(_t_--)↵
solve();↵
QwQ;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
### [Div2B. AI Finds Nothing Here](https://codeforces.me/contest/2240/problem/B)↵
↵
Author: [user:Gold14526,2026-06-27] Preparation: [user:Gold14526,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
Try some special cases, such as $r=c=2$, $n=r$, or $m=c$, etc.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
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).↵
↵
Therefore, the answer is $2^{nm - (n-r+1)(m-c+1)}$.↵
</spoiler>↵
↵
<spoiler summary="Code (by Gold14526)">↵
~~~~~↵
#include<bits/stdc++.h>↵
#define cint const int↵
#define uint unsigned int↵
#define cuint const unsigned int↵
#define ll long long↵
#define cll const long long↵
#define ull unsigned long long↵
#define cull const unsigned long long↵
using namespace std;↵
namespace FastIO↵
{↵
const int BUF_SIZE=1<<20;↵
char in_buf[BUF_SIZE],out_buf[BUF_SIZE];↵
char* in_ptr=in_buf+BUF_SIZE;↵
char* out_ptr=out_buf;↵
char get_char()↵
{↵
if(in_ptr==in_buf+BUF_SIZE)↵
{↵
in_ptr=in_buf;↵
fread(in_buf,1,BUF_SIZE,stdin);↵
}↵
return *in_ptr++;↵
}↵
void put_char(char c)↵
{↵
if(out_ptr==out_buf+BUF_SIZE)↵
{↵
fwrite(out_buf,1,BUF_SIZE,stdout);↵
out_ptr=out_buf;↵
}↵
*out_ptr++=c;↵
}↵
struct Flusher↵
{↵
~Flusher()↵
{↵
if(out_ptr!=out_buf)↵
{↵
fwrite(out_buf,1,out_ptr-out_buf,stdout);↵
}↵
}↵
} flusher;↵
}↵
#define getchar FastIO::get_char↵
#define putchar FastIO::put_char↵
inline int read()↵
{↵
int x=0;↵
bool zf=1;↵
char ch=getchar();↵
while(ch<'0'||ch>'9')↵
{↵
if(ch=='-')↵
{↵
zf=0;↵
}↵
ch=getchar();↵
}↵
while(ch>='0'&&ch<='9')↵
{↵
x=(x<<1)+(x<<3)+(ch^48);↵
ch=getchar();↵
}↵
return zf?x:-x;↵
}↵
void print(cint x)↵
{↵
if(x==0)↵
{↵
putchar('0');↵
return;↵
}↵
char buf[12];↵
int len=0,y=x;↵
if(y<0)↵
{↵
putchar('-');↵
y=-y;↵
}↵
while(y)↵
{↵
buf[len++]=(y%10)+'0';↵
y/=10;↵
}↵
while(len--)↵
{↵
putchar(buf[len]);↵
}↵
}↵
inline void princh(cint x,const char ch)↵
{↵
print(x);↵
putchar(ch);↵
}↵
cint mod=998244353;↵
int n,m,r,c;↵
int qpow(int x,int y)↵
{↵
int res=1;↵
while(y)↵
{↵
if(y&1)res=1ll*res*x%mod;↵
x=1ll*x*x%mod;↵
y>>=1;↵
}↵
return res;↵
}↵
void solve()↵
{↵
n=read();↵
m=read();↵
r=read();↵
c=read();↵
princh(qpow(2,(1ll*n*(c-1)+1ll*m*(r-1)-1ll*(c-1)*(r-1))%(mod-1)),'\n');↵
}↵
int main()↵
{↵
// freopen(".in","r",stdin);↵
// freopen(".out","w",stdout);↵
int T=read();↵
while(T--)solve();↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
### [Div1A. Nim Game Is XOR Game](https://codeforces.me/contest/2239/problem/A)↵
↵
Author: [user:Gold14526,2026-06-27] Preparation: [user:Gold14526,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239A]↵
</spoiler>↵
↵
<spoiler summary="Code (by Gold14526)">↵
~~~~~↵
#include<bits/stdc++.h>↵
#define cint const int↵
#define uint unsigned int↵
#define cuint const unsigned int↵
#define ll long long↵
#define cll const long long↵
#define ull unsigned long long↵
#define cull const unsigned long long↵
using namespace std;↵
namespace FastIO↵
{↵
const int BUF_SIZE=1<<20;↵
char in_buf[BUF_SIZE],out_buf[BUF_SIZE];↵
char* in_ptr=in_buf+BUF_SIZE;↵
char* out_ptr=out_buf;↵
char get_char()↵
{↵
if(in_ptr==in_buf+BUF_SIZE)↵
{↵
in_ptr=in_buf;↵
fread(in_buf,1,BUF_SIZE,stdin);↵
}↵
return *in_ptr++;↵
}↵
void put_char(char c)↵
{↵
if(out_ptr==out_buf+BUF_SIZE)↵
{↵
fwrite(out_buf,1,BUF_SIZE,stdout);↵
out_ptr=out_buf;↵
}↵
*out_ptr++=c;↵
}↵
struct Flusher↵
{↵
~Flusher()↵
{↵
if(out_ptr!=out_buf)↵
{↵
fwrite(out_buf,1,out_ptr-out_buf,stdout);↵
}↵
}↵
} flusher;↵
}↵
#define getchar FastIO::get_char↵
#define putchar FastIO::put_char↵
inline int read()↵
{↵
int x=0;↵
bool zf=1;↵
char ch=getchar();↵
while(ch<'0'||ch>'9')↵
{↵
if(ch=='-')↵
{↵
zf=0;↵
}↵
ch=getchar();↵
}↵
while(ch>='0'&&ch<='9')↵
{↵
x=(x<<1)+(x<<3)+(ch^48);↵
ch=getchar();↵
}↵
return zf?x:-x;↵
}↵
void print(cint x)↵
{↵
if(x==0)↵
{↵
putchar('0');↵
return;↵
}↵
char buf[12];↵
int len=0,y=x;↵
if(y<0)↵
{↵
putchar('-');↵
y=-y;↵
}↵
while(y)↵
{↵
buf[len++]=(y%10)+'0';↵
y/=10;↵
}↵
while(len--)↵
{↵
putchar(buf[len]);↵
}↵
}↵
inline void princh(cint x,const char ch)↵
{↵
print(x);↵
putchar(ch);↵
}↵
cint N=1e6;↵
int n,a[N+1],s,ans;↵
void solve()↵
{↵
n=read();↵
s=0;↵
ans=0;↵
for(int i=1;i<=n;++i)s^=(a[i]=read());↵
if(n==1)↵
{↵
princh(0,'\n');↵
return;↵
}↵
if(!s)↵
{↵
princh(1,'\n');↵
return;↵
}↵
for(int i=1;i<=n;++i)↵
{↵
if((s^a[i])<a[i])++ans;↵
}↵
princh(ans,'\n');↵
}↵
int main()↵
{↵
// freopen(".in","r",stdin);↵
// freopen(".out","w",stdout);↵
int T=read();↵
while(T--)solve();↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
### [Div1B. Decidophobia](https://codeforces.me/contest/2239/problem/B)↵
↵
Author: [user:Gold14526,2026-06-27] Preparation: [user:Gold14526,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
How does everyone’s contribution change when you give a gift to someone?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239B]↵
</spoiler>↵
↵
<spoiler summary="Code (by Gold14526)">↵
~~~~~↵
#include<bits/stdc++.h>↵
#define cint const int↵
#define uint unsigned int↵
#define cuint const unsigned int↵
#define ll long long↵
#define cll const long long↵
#define ull unsigned long long↵
#define cull const unsigned long long↵
#define sh short↵
#define csh const short↵
#define ush unsigned short↵
#define cush const unsigned short↵
using namespace std;↵
namespace FastIO↵
{↵
const int BUF_SIZE=1<<20;↵
char in_buf[BUF_SIZE],out_buf[BUF_SIZE];↵
char* in_ptr=in_buf+BUF_SIZE;↵
char* out_ptr=out_buf;↵
char get_char()↵
{↵
if(in_ptr==in_buf+BUF_SIZE)↵
{↵
in_ptr=in_buf;↵
fread(in_buf,1,BUF_SIZE,stdin);↵
}↵
return *in_ptr++;↵
}↵
void put_char(char c)↵
{↵
if(out_ptr==out_buf+BUF_SIZE)↵
{↵
fwrite(out_buf,1,BUF_SIZE,stdout);↵
out_ptr=out_buf;↵
}↵
*out_ptr++=c;↵
}↵
struct Flusher↵
{↵
~Flusher()↵
{↵
if(out_ptr!=out_buf)↵
{↵
fwrite(out_buf,1,out_ptr-out_buf,stdout);↵
}↵
}↵
} flusher;↵
}↵
#define getchar FastIO::get_char↵
#define putchar FastIO::put_char↵
inline int read()↵
{↵
int x=0;↵
bool zf=1;↵
char ch=getchar();↵
while(ch<'0'||ch>'9')↵
{↵
if(ch=='-')↵
{↵
zf=0;↵
}↵
ch=getchar();↵
}↵
while(ch>='0'&&ch<='9')↵
{↵
x=(x<<1)+(x<<3)+(ch^48);↵
ch=getchar();↵
}↵
return zf?x:-x;↵
}↵
void print(cll x)↵
{↵
if(x==0)↵
{↵
putchar('0');↵
return;↵
}↵
char buf[20];↵
int len=0;↵
ll y=x;↵
if(y<0)↵
{↵
putchar('-');↵
y=-y;↵
}↵
while(y)↵
{↵
buf[len++]=(y%10)+'0';↵
y/=10;↵
}↵
while(len--)↵
{↵
putchar(buf[len]);↵
}↵
}↵
inline void princh(cll x,const char ch)↵
{↵
print(x);↵
putchar(ch);↵
}↵
cint N=6e5;↵
int n,d;↵
int a[N+1];↵
ll s[N+1],val[N+1];↵
ll ans;↵
void solve()↵
{↵
n=read();↵
d=read();↵
for(int i=1;i<=n;++i)↵
{↵
a[i]=a[i+n]=a[i+(n<<1)]=read();↵
}↵
for(int i=1;i<=n*3;++i)s[i]=s[i-1]+a[i];↵
for(int i=n+1;i<=(n<<1);++i)↵
{↵
val[i-n]=1ll*(d<<1|1)*a[i]-(s[i+d]-s[i-d-1]);↵
}↵
ans=0;↵
for(int i=1;i<=n;++i)ans+=max(0ll,val[i]);↵
princh(ans,'\n');↵
}↵
int main()↵
{↵
//freopen(".in","r",stdin);↵
//freopen(".out","w",stdout);↵
int T=read();↵
while(T--)solve();↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
### [Div1C. Revival](https://codeforces.me/contest/2239/problem/C)↵
↵
Author: [user:Gold14526,2026-06-27] Preparation: [user:Gold14526,2026-06-27]↵
↵
↵
<spoiler summary="Hint 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Consider doing the transitions from back to front.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
We only need to support the following operations:↵
↵
- Add and delete edges;↵
- Query the maximum value in a connected component;↵
- Take the max of all weights in a connected component with a given number.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Consider modifying the dynamic graph connectivity approach.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239E]↵
</spoiler>↵
↵
### [Div1F. Colorful Works](https://codeforces.me/contest/2239/problem/F)↵
↵
Author: [user:Milkcat2009,2026-06-27] Preparation: [user:Milkcat2009,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
Consider the case where $l_i=0$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Just Consider the most straightforward DP approach, and then try to find some patterns.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Try transforming the modulo $2$ counting DP into a game and solve it.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
You should already know the answer for $l_i=0$; try using the Principle of Inclusion-Exclusion to count.↵
</spoiler>↵
↵
<spoiler summary="Hint 5">↵
Enumerate which element is strictly greater than half of the total sum.↵
</spoiler>↵
↵
<spoiler summary="Hint 6">↵
You should already know the $O(nm/w)$ algorithm. Consider that, under modulo $2$, we have $(1+x^k)^2=1+x^{2k}$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239F]Consider determining all the numbers from back to front.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239C]↵
</spoiler>↵
↵
<spoiler summary="Code (by Gold14526)">↵
~~~~~↵
#include<bits/stdc++.h>↵
#define cint const int↵
#define uint unsigned int↵
#define cuint const unsigned int↵
#define ll long long↵
#define cll const long long↵
#define ull unsigned long long↵
#define cull const unsigned long long↵
#define sh short↵
#define csh const short↵
#define ush unsigned short↵
#define cush const unsigned short↵
using namespace std;↵
namespace FastIO↵
{↵
const int BUF_SIZE=1<<20;↵
char in_buf[BUF_SIZE],out_buf[BUF_SIZE];↵
char* in_ptr=in_buf+BUF_SIZE;↵
char* out_ptr=out_buf;↵
char get_char()↵
{↵
if(in_ptr==in_buf+BUF_SIZE)↵
{↵
in_ptr=in_buf;↵
fread(in_buf,1,BUF_SIZE,stdin);↵
}↵
return *in_ptr++;↵
}↵
void put_char(char c)↵
{↵
if(out_ptr==out_buf+BUF_SIZE)↵
{↵
fwrite(out_buf,1,BUF_SIZE,stdout);↵
out_ptr=out_buf;↵
}↵
*out_ptr++=c;↵
}↵
struct Flusher↵
{↵
~Flusher()↵
{↵
if(out_ptr!=out_buf)↵
{↵
fwrite(out_buf,1,out_ptr-out_buf,stdout);↵
}↵
}↵
} flusher;↵
}↵
#define getchar FastIO::get_char↵
#define putchar FastIO::put_char↵
inline ll read()↵
{↵
ll x=0;↵
bool zf=1;↵
char ch=getchar();↵
while(ch<'0'||ch>'9')↵
{↵
if(ch=='-')↵
{↵
zf=0;↵
}↵
ch=getchar();↵
}↵
while(ch>='0'&&ch<='9')↵
{↵
x=(x<<1)+(x<<3)+(ch^48);↵
ch=getchar();↵
}↵
return zf?x:-x;↵
}↵
void print(cint x)↵
{↵
if(x==0)↵
{↵
putchar('0');↵
return;↵
}↵
char buf[12];↵
int len=0,y=x;↵
if(y<0)↵
{↵
putchar('-');↵
y=-y;↵
}↵
while(y)↵
{↵
buf[len++]=(y%10)+'0';↵
y/=10;↵
}↵
while(len--)↵
{↵
putchar(buf[len]);↵
}↵
}↵
inline void princh(cint x,const char ch)↵
{↵
print(x);↵
putchar(ch);↵
}↵
cint N=1e6;↵
int n;↵
ll val[N+1];↵
char type[N+1];↵
int ans[N+1];↵
struct Binary_Index_Tree{↵
int a[N+1];↵
void clear()↵
{↵
for(int i=1;i<=n;++i)a[i]=0;↵
}↵
inline void add(cint x,cint y)↵
{↵
for(int i=x;i<=n;i+=(i&-i))a[i]+=y;↵
}↵
inline int ask(cint x)↵
{↵
int s=0;↵
for(int i=x;i;i-=(i&-i))s+=a[i];↵
return s;↵
}↵
inline int find(int x)↵
{↵
int res=0;↵
for(int len=1<<__lg(n);len;len>>=1)↵
{↵
if(res+len>n)continue;↵
if(a[res+len]<=x)↵
{↵
res+=len;↵
x-=a[res];↵
}↵
}↵
return res+1;↵
}↵
}T;↵
int lst[N+1];↵
void solve()↵
{↵
n=read();↵
T.clear();↵
for(int i=1;i<=n;++i)↵
{↵
char ch=getchar();↵
while(ch!='p'&&ch!='s')ch=getchar();↵
type[i]=ch;↵
val[i]=read();↵
if(type[i]=='p')ans[i]=val[i];↵
else val[i]=1ll*i*(i-1)/2-val[i];↵
}↵
for(int i=1;i<=n;++i)lst[i]=(type[i]=='s'?i:lst[i-1]);↵
for(int i=1;i<=n;++i)T.add(i,1);↵
for(int i=lst[n]+1;i<=n;++i)T.add(ans[i],-1);↵
for(int i=lst[n];i;i=lst[i-1])↵
{↵
cint p=lst[i-1];↵
ll d=val[i]-val[p];↵
for(int j=i-1;j>p;--j)↵
{↵
d-=T.ask(ans[j]-1);↵
T.add(ans[j],-1);↵
}↵
d+=i-p-1;↵
for(int j=i-1;j>p;--j)T.add(ans[j],2);↵
ans[i]=T.find(d);↵
for(int j=i-1;j>p;--j)T.add(ans[j],-2);↵
T.add(ans[i],-1);↵
}↵
for(int i=1;i<=n;++i)↵
{↵
princh(ans[i]," \n"[i==n]);↵
}↵
}↵
int main()↵
{↵
//freopen(".in","r",stdin);↵
//freopen(".out","w",stdout);↵
int T=read();↵
while(T--)solve();↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
### [Div1D. Hunting the Beast](https://codeforces.me/contest/2239/problem/D)↵
↵
Author: [user:Milkcat2009,2026-06-27] Preparation: [user:Milkcat2009,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
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}$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
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.↵
↵
The answer is $1-n$, which you can try to prove.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Use the Binomial Theorem to simplify the sum.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239D]↵
</spoiler>↵
↵
<spoiler summary="Code (by Milkcat2009)">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)↵
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)↵
#define CUP(i, l, r) for (int i = (l); i < (r); ++ i)↵
#define fi first↵
#define se second↵
#define pb emplace_back↵
#define mems(x, v) memset((x), (v), sizeof(x))↵
#define memc(x, y) memcpy((x), (y), sizeof(x))↵
#define SZ(x) (int)(x).size()↵
#define ALL(x) (x).begin(), (x).end()↵
#define ppc(x) __builtin_popcount(x)↵
#define ctz(x) __builtin_ctz(x)↵
#define clz(x) __builtin_clz(x)↵
using namespace std;↵
namespace math {↵
typedef long long LL;↵
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; }↵
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; }↵
template <unsigned P = 0> struct mint {↵
unsigned v; static unsigned mod; mint() = default;↵
template <class T> mint(T x) { x %= (int)getmod(), v = x < 0 ? x + getmod() : x; }↵
constexpr static unsigned getmod() { if (P > 0) return P; else return mod; }↵
static void setmod(unsigned m) { mod = m; }↵
mint operator + () const { return *this; }↵
mint operator - () const { return mint(0) - *this; }↵
mint inv() const { return assert(v), qpow(*this, getmod() - 2); }↵
int val() const { return v; }↵
mint &operator += (const mint &q) { if (v += q.v, v >= getmod()) v -= getmod(); return *this; }↵
mint &operator -= (const mint &q) { if (v -= q.v, v >= getmod()) v += getmod(); return *this; }↵
mint &operator *= (const mint &q) { v = 1ull * v * q.v % getmod(); return *this; }↵
mint &operator /= (const mint &q) { return *this *= q.inv(); }↵
friend mint operator + (mint p, const mint &q) { return p += q; }↵
friend mint operator - (mint p, const mint &q) { return p -= q; }↵
friend mint operator * (mint p, const mint &q) { return p *= q; }↵
friend mint operator / (mint p, const mint &q) { return p /= q; }↵
friend bool operator == (const mint &p, const mint &q) { return p.v == q.v; }↵
friend bool operator != (const mint &p, const mint &q) { return p.v != q.v; }↵
friend bool operator < (const mint &p, const mint &q) { return p.v < q.v; }↵
friend bool operator > (const mint &p, const mint &q) { return p.v > q.v; }↵
friend bool operator <= (const mint &p, const mint &q) { return p.v <= q.v; }↵
friend bool operator >= (const mint &p, const mint &q) { return p.v >= q.v; }↵
friend istream &operator >> (istream &is, mint &a) { LL x; is >> x, a = x; return is; }↵
friend ostream &operator << (ostream &os, const mint &a) { os << a.v; return os; }↵
};↵
template <> unsigned mint<0>::mod = 998244353;↵
template <typename MI>↵
struct Comb {↵
#define P MI::getmod()↵
vector<MI> fc, ifc;↵
void init(int n) {↵
fc.resize(n + 1), ifc.resize(n + 1), fc[0] = 1;↵
REP(i, 1, n) fc[i] = fc[i - 1] * i;↵
ifc[n] = fc[n].inv();↵
DEP(i, n, 1) ifc[i - 1] = ifc[i] * i;↵
}↵
MI operator () (LL n, LL m) {↵
if (m > n || m < 0 || n < 0) return 0;↵
if (n < P && m < P) { assert(n < SZ(fc)); return fc[n] * ifc[m] * ifc[n - m]; }↵
return (!n ? 1 : (*this)(n / P, m / P) * (*this)(n % P, m % P));↵
}↵
#undef P↵
};↵
namespace Z {↵
const int mod = 998244353;↵
using MI = mint<mod>; using math::qpow; Comb<MI> C;↵
MI fac(int x) { assert(x >= 0 && x < SZ(C.fc)); return C.fc[x]; }↵
MI ifc(int x) { assert(x >= 0 && x < SZ(C.ifc)); return C.ifc[x]; }↵
MI inv(int x) { assert(x && x < SZ(C.fc)); return C.ifc[x] * C.fc[x - 1]; }↵
MI sab(int x, int y) { return (!y ? !x : C(x + y - 1, y - 1)); }↵
}↵
}↵
namespace Milkcat {↵
using namespace math::Z;↵
typedef long long LL;↵
typedef pair<LL, LL> pii;↵
const int N = 1e7 + 5;↵
int n, m, t, v[N]; MI g[N];↵
void sieve(int n, int k, MI* f) {↵
vector<int> p; fill_n(v + 1, n, 0), f[1] = 1;↵
REP(i, 2, n) {↵
if (!v[i]) p.pb(i), f[i] = qpow((MI)i, k);↵
for (int j : p) {↵
if (i * j <= n) f[i * j] = f[i] * f[j], v[i * j] = 1;↵
if (i * j > n || i % j == 0) break;↵
}↵
}↵
}↵
MI slv2(int n, int m) {↵
MI rs = 0;↵
REP(i, 0, n - m)↵
rs += g[n - i - 1] * C(n - m, i) * (i & 1 ? -1 : 1);↵
return rs * (n - 1);↵
}↵
int main() {↵
cin >> t, C.init(1e6);↵
while (t --) {↵
cin >> n >> m, sieve(n, n - 1, g);↵
cout << slv2(n, m) * C(n, m) << '\n';↵
}↵
return 0;↵
}↵
}↵
int main() {↵
cin.tie(0)->sync_with_stdio(0);↵
int T = 1;↵
while (T --) Milkcat::main();↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
### [Div1E. The end of this world,](https://codeforces.me/contest/2239/problem/E)↵
↵
Author: [user:Gold14526,2026-06-27] Preparation: [user:Gold14526,2026-06-27]↵
↵
↵
<spoiler summary="Hint 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Consider doing the transitions from back to front.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
We only need to support the following operations:↵
↵
- Add and delete edges;↵
- Query the maximum value in a connected component;↵
- Take the max of all weights in a connected component with a given number.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Consider modifying the dynamic graph connectivity approach.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239E]↵
</spoiler>↵
↵
<spoiler summary="Code (by Gold14526)">↵
~~~~~↵
#include<bits/stdc++.h>↵
#define cint const int↵
#define uint unsigned int↵
#define cuint const unsigned int↵
#define ll long long↵
#define cll const long long↵
#define ull unsigned long long↵
#define cull const unsigned long long↵
using namespace std;↵
namespace FastIO↵
{↵
const int BUF_SIZE=1<<20;↵
char in_buf[BUF_SIZE],out_buf[BUF_SIZE];↵
char* in_ptr=in_buf+BUF_SIZE;↵
char* out_ptr=out_buf;↵
char get_char()↵
{↵
if(in_ptr==in_buf+BUF_SIZE)↵
{↵
in_ptr=in_buf;↵
fread(in_buf,1,BUF_SIZE,stdin);↵
}↵
return *in_ptr++;↵
}↵
void put_char(char c)↵
{↵
if(out_ptr==out_buf+BUF_SIZE)↵
{↵
fwrite(out_buf,1,BUF_SIZE,stdout);↵
out_ptr=out_buf;↵
}↵
*out_ptr++=c;↵
}↵
struct Flusher↵
{↵
~Flusher()↵
{↵
if(out_ptr!=out_buf)↵
{↵
fwrite(out_buf,1,out_ptr-out_buf,stdout);↵
}↵
}↵
} flusher;↵
}↵
#define getchar FastIO::get_char↵
#define putchar FastIO::put_char↵
inline int read()↵
{↵
int x=0;↵
bool zf=1;↵
char ch=getchar();↵
while(ch<'0'||ch>'9')↵
{↵
if(ch=='-')↵
{↵
zf=0;↵
}↵
ch=getchar();↵
}↵
while(ch>='0'&&ch<='9')↵
{↵
x=(x<<1)+(x<<3)+(ch^48);↵
ch=getchar();↵
}↵
return zf?x:-x;↵
}↵
void print(cint x)↵
{↵
if(x==0)↵
{↵
putchar('0');↵
return;↵
}↵
char buf[12];↵
int len=0,y=x;↵
if(y<0)↵
{↵
putchar('-');↵
y=-y;↵
}↵
while(y)↵
{↵
buf[len++]=(y%10)+'0';↵
y/=10;↵
}↵
while(len--)↵
{↵
putchar(buf[len]);↵
}↵
}↵
inline void princh(cint x,const char ch)↵
{↵
print(x);↵
putchar(ch);↵
}↵
cint N=5e5,M=5e5,H=20;↵
int n,m;↵
int val[N+1];↵
int eu[M+1],ev[M+1],low[M+1],lim[M+1];↵
int tl[M+1],tr[M+1];↵
struct dx{↵
int idx,val;↵
}c[M<<1|1];↵
struct edge{↵
int u,v,l,r;↵
};↵
vector<edge>E,EL[H+1],ER[H+1];↵
struct info{↵
int t,u;↵
}mdf[M+1];↵
int tag[N+(M<<2|1)],mx[N+(M<<2|1)];↵
int fa[N+(M<<2|1)];↵
int tot;↵
int top[N+(M<<2|1)];↵
int head[N+(M<<2|1)];↵
struct et{↵
int to,nxt;↵
}ve[M<<2|1];↵
int ct;↵
inline void add_edge(cint u,cint v)↵
{↵
ve[++ct]={v,head[u]};↵
head[u]=ct;↵
ve[++ct]={u,head[v]};↵
head[v]=ct;↵
}↵
inline int newv()↵
{↵
++tot;↵
tag[tot]=-1;↵
mx[tot]=fa[tot]=0;↵
return tot;↵
}↵
struct stck{↵
int a[N+1],t;↵
inline void clear(){t=0;}↵
inline int top(){return a[t];}↵
inline void pop(){--t;}↵
inline void push(cint x){a[++t]=x;}↵
inline bool empty(){return (t==0);}↵
}st;↵
void dfs(cint u)↵
{↵
top[u]=u;↵
st.clear();↵
st.push(u);↵
while(!st.empty())↵
{↵
cint s=st.top();↵
st.pop();↵
for(int i=head[s];i;i=ve[i].nxt)↵
{↵
cint v=ve[i].to;↵
if(top[v])continue;↵
top[v]=u;↵
st.push(v);↵
}↵
}↵
}↵
void update(cint h,cint l,cint r,vector<edge>&E,int m,cint vl,cint vr)↵
{↵
if(E.empty())↵
{↵
for(int i=1;i<=m;++i)↵
{↵
tag[mdf[i].u]=max(tag[mdf[i].u],mx[mdf[i].u]+c[l].val);↵
}↵
return;↵
}↵
cint mid=l+r>>1;↵
EL[h].clear();↵
ER[h].clear();↵
for(int i=vl;i<=vr;++i)↵
{↵
head[i]=top[i]=fa[i]=0;↵
}↵
ct=0;↵
for(edge &e:E)↵
{↵
if(e.l<=l&&e.r>=r)↵
{↵
add_edge(e.u,e.v);↵
}↵
else↵
{↵
if(e.l<=mid)EL[h].push_back(e);↵
if(e.r>mid)ER[h].push_back(e);↵
}↵
}↵
for(int i=vl;i<=vr;++i)↵
{↵
if(!top[i])dfs(i);↵
}↵
if(l==r)↵
{↵
for(int i=vl;i<=vr;++i)mx[top[i]]=max(mx[top[i]],mx[i]);↵
for(int i=1;i<=m;++i)↵
{↵
cint u=top[mdf[i].u];↵
tag[u]=max(tag[u],mx[u]+c[l].val);↵
}↵
for(int i=vl;i<=vr;++i)↵
{↵
tag[i]=max(tag[i],tag[top[i]]);↵
mx[i]=max(mx[i],mx[top[i]]);↵
}↵
return;↵
}↵
cint tmp=tot;↵
for(edge &e:ER[h])↵
{↵
cint u=top[e.u],v=top[e.v];↵
if(!fa[u])fa[u]=newv();↵
if(!fa[v])fa[v]=newv();↵
e.u=fa[u];↵
e.v=fa[v];↵
}↵
int pm=0;↵
for(int i=1;i<=m;++i)↵
{↵
info &p=mdf[i];↵
if(p.t>mid)↵
{↵
cint u=top[p.u];↵
if(!fa[u])fa[u]=newv();↵
p.u=fa[u];↵
swap(p,mdf[++pm]);↵
}↵
}↵
for(int i=vl;i<=vr;++i)↵
{↵
cint u=fa[top[i]];↵
if(u)mx[u]=max(mx[u],mx[i]);↵
}↵
update(h+1,mid+1,r,ER[h],pm,tmp+1,tot);↵
for(int i=vl;i<=vr;++i)↵
{↵
cint u=fa[top[i]];↵
if(u)mx[i]=max(mx[i],mx[u]),tag[i]=max(tag[i],tag[u]);↵
}↵
tot=tmp;↵
for(int i=vl;i<=vr;++i)fa[i]=0;↵
for(edge &e:EL[h])↵
{↵
cint u=top[e.u],v=top[e.v];↵
if(!fa[u])fa[u]=newv();↵
if(!fa[v])fa[v]=newv();↵
e.u=fa[u];↵
e.v=fa[v];↵
}↵
for(int i=pm+1;i<=m;++i)↵
{↵
info &p=mdf[i];↵
cint u=top[p.u];↵
if(!fa[u])fa[u]=newv();↵
p.u=fa[u];↵
swap(p,mdf[i-pm]);↵
}↵
pm=m-pm;↵
for(int i=vl;i<=vr;++i)↵
{↵
cint u=fa[top[i]];↵
if(u)mx[u]=max(mx[u],mx[i]);↵
}↵
update(h+1,l,mid,EL[h],pm,tmp+1,tot);↵
for(int i=vl;i<=vr;++i)↵
{↵
cint u=fa[top[i]];↵
if(u)mx[i]=max(mx[i],mx[u]),tag[i]=max(tag[i],tag[u]);↵
}↵
tot=tmp;↵
}↵
void solve()↵
{↵
tag[0]=-1;↵
tot=n=read();↵
m=read();↵
for(int i=1;i<=n;++i)val[i]=read(),tag[i]=-1,mx[i]=val[i];↵
for(int i=1;i<=m;++i)↵
{↵
eu[i]=read(),ev[i]=read(),lim[i]=read(),low[i]=read();↵
c[i]={i,lim[i]};↵
c[i+m]={i+m,low[i]};↵
}↵
sort(c+1,c+(m<<1|1),[&](dx p,dx q){return (p.val==q.val?p.idx>q.idx:p.val<q.val);});↵
for(int i=1;i<=(m<<1);++i)↵
{↵
if(c[i].idx>m)tl[c[i].idx-m]=i;↵
else tr[c[i].idx]=i;↵
}↵
E.clear();↵
for(int i=1;i<=m;++i)↵
{↵
E.push_back({eu[i],ev[i],tl[i],tr[i]});↵
mdf[i]={tr[i],eu[i]};↵
}↵
if(m)update(0,1,m<<1,E,m,1,n);↵
for(int i=1;i<=n;++i)princh(tag[i]," \n"[i==n]);↵
}↵
int main()↵
{↵
// freopen(".in","r",stdin);↵
// freopen(".out","w",stdout);↵
int T=read();↵
while(T--)solve();↵
return 0;↵
}↵
↵
↵
~~~~~↵
↵
</spoiler>↵
↵
### [Div1F. Colorful Works](https://codeforces.me/contest/2239/problem/F)↵
↵
Author: [user:Milkcat2009,2026-06-27] Preparation: [user:Milkcat2009,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
Consider the case where $l_i=0$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Just Consider the most straightforward DP approach, and then try to find some patterns.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Try transforming the modulo $2$ counting DP into a game and solve it.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
You should already know the answer for $l_i=0$; try using the Principle of Inclusion-Exclusion to count.↵
</spoiler>↵
↵
<spoiler summary="Hint 5">↵
Enumerate which element is strictly greater than half of the total sum.↵
</spoiler>↵
↵
<spoiler summary="Hint 6">↵
You should already know the $O(nm/w)$ algorithm. Consider that, under modulo $2$, we have $(1+x^k)^2=1+x^{2k}$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239F]↵
</spoiler>↵
↵
<spoiler summary="Code (by Milkcat2009)">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)↵
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)↵
#define CUP(i, l, r) for (int i = (l); i < (r); ++ i)↵
#define fi first↵
#define se second↵
#define pb emplace_back↵
#define mems(x, v) memset((x), (v), sizeof(x))↵
#define memc(x, y) memcpy((x), (y), sizeof(x))↵
#define SZ(x) (int)(x).size()↵
#define ALL(x) (x).begin(), (x).end()↵
#define ppc(x) __builtin_popcount(x)↵
#define ctz(x) __builtin_ctz(x)↵
#define clz(x) __builtin_clz(x)↵
using namespace std;↵
namespace Milkcat {↵
typedef long long LL;↵
typedef pair<LL, LL> pii;↵
const int N = 2e6 + 5, M = 2e5 + 5;↵
int n, m, rs, d, p, q, l[N], r[N], c[M];↵
bitset<M> f;↵
int val(int x) { x -= d; return (x >= 0 && x <= m ? f[x] : 0); }↵
int main() {↵
cin >> n;↵
REP(i, 1, n)↵
cin >> l[i] >> r[i], m = max(m, r[i]);↵
REP(i, 1, n) {↵
if (!l[i]) d = min(d + r[i], (int)1e9);↵
else d = min(d + l[i] - 1, (int)1e9), c[r[i] - l[i] + 1] ++;↵
}↵
f = 1;↵
REP(i, 1, m) {↵
if (i * 2 <= m) c[i * 2] += c[i] >> 1;↵
if (c[i] & 1) f ^= f << i;↵
}↵
REP(i, 2, m) f[i] = f[i] ^ f[i - 2];↵
REP(i, 1, n) {↵
if (!l[i]) rs ^= val(r[i] * 2 - 2), p ^= r[i] & 1;↵
else rs ^= val(l[i] + r[i] - 1 - 2), q += ((l[i] & 1) == (r[i] & 1) ? 1 : 2);↵
}↵
cout << (rs ^ (!q ? !p : (q < 2))) << '\n';↵
REP(i, 1, m) c[i] = 0;↵
m = rs = d = p = q = 0;↵
return 0;↵
}↵
}↵
int main() {↵
cin.tie(0)->sync_with_stdio(0);↵
int T = 1; cin >> T;↵
while (T --) Milkcat::main();↵
return 0;↵
}↵
↵
↵
~~~~~↵
↵
</spoiler>↵
↵
↵
### [Div2A. Another Popcount Problem](https://codeforces.me/contest/2240/problem/A)↵
↵
Author: [user:wangmarui,2026-06-27] Preparation: [user:wangmarui,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
Consider each binary bit independently.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Think about a greedy approach.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2240A]↵
</spoiler>↵
↵
↵
Author: [user:Gold14526,2026-06-27] Preparation: [user:Gold14526,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
Try some special cases, such as $r=c=2$, $n=r$, or $m=c$, etc.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
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).↵
↵
Therefore, the answer is $2^{nm - (n-r+1)(m-c+1)}$.↵
</spoiler>↵
↵
### [Div1A. Nim Game Is XOR Game](https://codeforces.me/contest/2239/problem/A)↵
↵
Author: [user:Gold14526,2026-06-27] Preparation: [user:Gold14526,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239A]↵
</spoiler>↵
↵
### [Div1B. Decidophobia](https://codeforces.me/contest/2239/problem/B)↵
↵
Author: [user:Gold14526,2026-06-27] Preparation: [user:Gold14526,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
How does everyone’s contribution change when you give a gift to someone?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239B]↵
</spoiler>↵
↵
### [Div1C. Revival](https://codeforces.me/contest/2239/problem/C)↵
↵
Author: [user:Gold14526,2026-06-27] Preparation: [user:Gold14526,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
Consider determining all the numbers from back to front.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239C]↵
</spoiler>↵
↵
### [Div1D. Hunting the Beast](https://codeforces.me/contest/2239/problem/D)↵
↵
Author: [user:Milkcat2009,2026-06-27] Preparation: [user:Milkcat2009,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
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}$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
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.↵
↵
The answer is $1-n$, which you can try to prove.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Use the Binomial Theorem to simplify the sum.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239D]↵
</spoiler>↵
↵
### [Div1E. The end of this world,](https://codeforces.me/contest/2239/problem/E
~~~~~↵
/*↵
author: Yuneko↵
↵
time: 2026/5/5↵
↵
contest:↵
↵
Tips:↵
↵
RE, MLE?↵
greedy, dp?↵
natural time?↵
map, umap?↵
giveup rating, get score.↵
brute force, right solution?↵
%mod? std/run/maker/checker?↵
add bruteforce?↵
clear?↵
double, long double?↵
O(n)? O(n^2)!↵
make data!↵
↵
last but not least.↵
↵
bruteforce -> SegTree?↵
Think more.↵
*/↵
//#pragma GCC optimize("Ofast")↵
//#pragma GCC optimize("unroll-loops")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")↵
#include<bits/stdc++.h>↵
using namespace std;↵
//#define map unordered_map↵
#define re register↵
#define ll long long↵
#define cll const ll↵
#define forl(i,a,b) for(re ll (i)=(a);i<=(b);(i)++)↵
#define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--)↵
#define forll(i,a,b,c) for(re ll (i)=(a);i<=(b);(i)+=(c))↵
#define forrr(i,a,b,c) for(re ll (i)=(a);i>=(b);(i)-=(c))↵
#define forL(i,a,b,c) for(re ll (i)=(a);((i)<=(b)) && (c);(i)++)↵
#define forR(i,a,b,c) for(re ll (i)=(a);((i)>=(b)) && (c);(i)--)↵
#define forLL(i,a,b,c,d) for(re ll (i)=(a);((i)<=(b)) && (d);(i)+=(c))↵
#define forRR(i,a,b,c,d) for(re ll (i)=(a);((i)>=(b)) && (d);(i)-=(c))↵
#define pii pair<ll,ll>↵
#define mid ((l+r)>>1)↵
#define lowbit(x) ((x)&-(x))↵
#define pb push_back↵
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);↵
#define endl '\n'↵
#define QwQ return 0;↵
#define db long double↵
#define ull unsigned long long↵
#define lcm(x,y) (1ll*(x)/__gcd(x,y)*(y))↵
#define Sum(x,y) (1ll*((x)+(y))*((y)-(x)+1)/2)↵
#define x first↵
#define y second↵
#define aty cout<<"Yes\n";↵
#define atn cout<<"No\n";↵
#define cfy cout<<"YES\n";↵
#define cfn cout<<"NO\n";↵
#define xxy cout<<"yes\n";↵
#define xxn cout<<"no\n";↵
#define printcf(x) x?cout<<"YES\n":cout<<"NO\n";↵
#define printat(x) x?cout<<"Yes\n":cout<<"No\n";↵
#define printxx(x) x?cout<<"yes\n":cout<<"no\n";↵
#define maxqueue priority_queue<ll>↵
#define minqueue priority_queue<ll,vector<ll>,greater<ll>>↵
#define bug1 cout<<"bug1,AWaDa?\n";↵
#define bug2 cout<<"bug2,AWaDa!\n";↵
#define bug3 cout<<"bug3,AKTang?\n";↵
#define bug4 cout<<"bug4,AKTang!\n";↵
#define IM (ll)1e9↵
#define LM (ll)1e18↵
#define MIM (ll)-1e9↵
#define MLM (ll)-1e18↵
#define sort stable_sort↵
ll rd(ll&x){cin>>x;return x;}ll rd(){ll x;cin>>x;return x;}↵
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;}↵
ll pw(ll x){return 1ll<<x;}↵
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;}↵
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;}↵
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;}↵
ll _t_;↵
struct BIT{↵
ll maxn;↵
ll tree[1000010];↵
void clear(ll l){↵
forl(i,0,l)↵
tree[i]=0;↵
}↵
void add(ll x,ll y){↵
for(;x<=maxn;x+=lowbit(x))↵
tree[x]+=y;↵
}↵
ll query(ll x){↵
ll S=0;↵
for(;x;x-=lowbit(x))↵
S+=tree[x];↵
return S;↵
}↵
ll query(ll l,ll r){↵
return query(r)-query(l-1);↵
}↵
};↵
ll lg[1000010];↵
void Init(){↵
forl(i,2,1e6+5)↵
lg[i]=lg[i>>1]+1;↵
}↵
//xw↵
ll n,m;↵
ll ans;↵
//st↵
void _clear(){}↵
void solve()↵
{↵
_clear();↵
cin>>n>>m;↵
forl(i,0,30)↵
{↵
ll num=min(n/pw(i),m);↵
ans+=num,n-=num*pw(i);↵
}↵
cout<<ans<<endl;↵
ans=0;↵
}↵
int main()↵
{↵
Init();↵
// freopen("tst.txt","r",stdin);↵
// freopen("sans.txt","w",stdout);↵
IOS;↵
_t_=1;↵
cin>>_t_;↵
while(_t_--)↵
solve();↵
QwQ;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
### [Div2B. AI Finds Nothing Here](https://codeforces.me/contest/2240/problem/B)↵
↵
Author: [user:Gold14526,2026-06-27] Preparation: [user:Gold14526,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
Try some special cases, such as $r=c=2$, $n=r$, or $m=c$, etc.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
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).↵
↵
Therefore, the answer is $2^{nm - (n-r+1)(m-c+1)}$.↵
</spoiler>↵
↵
<spoiler summary="Code (by Gold14526)">↵
~~~~~↵
#include<bits/stdc++.h>↵
#define cint const int↵
#define uint unsigned int↵
#define cuint const unsigned int↵
#define ll long long↵
#define cll const long long↵
#define ull unsigned long long↵
#define cull const unsigned long long↵
using namespace std;↵
namespace FastIO↵
{↵
const int BUF_SIZE=1<<20;↵
char in_buf[BUF_SIZE],out_buf[BUF_SIZE];↵
char* in_ptr=in_buf+BUF_SIZE;↵
char* out_ptr=out_buf;↵
char get_char()↵
{↵
if(in_ptr==in_buf+BUF_SIZE)↵
{↵
in_ptr=in_buf;↵
fread(in_buf,1,BUF_SIZE,stdin);↵
}↵
return *in_ptr++;↵
}↵
void put_char(char c)↵
{↵
if(out_ptr==out_buf+BUF_SIZE)↵
{↵
fwrite(out_buf,1,BUF_SIZE,stdout);↵
out_ptr=out_buf;↵
}↵
*out_ptr++=c;↵
}↵
struct Flusher↵
{↵
~Flusher()↵
{↵
if(out_ptr!=out_buf)↵
{↵
fwrite(out_buf,1,out_ptr-out_buf,stdout);↵
}↵
}↵
} flusher;↵
}↵
#define getchar FastIO::get_char↵
#define putchar FastIO::put_char↵
inline int read()↵
{↵
int x=0;↵
bool zf=1;↵
char ch=getchar();↵
while(ch<'0'||ch>'9')↵
{↵
if(ch=='-')↵
{↵
zf=0;↵
}↵
ch=getchar();↵
}↵
while(ch>='0'&&ch<='9')↵
{↵
x=(x<<1)+(x<<3)+(ch^48);↵
ch=getchar();↵
}↵
return zf?x:-x;↵
}↵
void print(cint x)↵
{↵
if(x==0)↵
{↵
putchar('0');↵
return;↵
}↵
char buf[12];↵
int len=0,y=x;↵
if(y<0)↵
{↵
putchar('-');↵
y=-y;↵
}↵
while(y)↵
{↵
buf[len++]=(y%10)+'0';↵
y/=10;↵
}↵
while(len--)↵
{↵
putchar(buf[len]);↵
}↵
}↵
inline void princh(cint x,const char ch)↵
{↵
print(x);↵
putchar(ch);↵
}↵
cint mod=998244353;↵
int n,m,r,c;↵
int qpow(int x,int y)↵
{↵
int res=1;↵
while(y)↵
{↵
if(y&1)res=1ll*res*x%mod;↵
x=1ll*x*x%mod;↵
y>>=1;↵
}↵
return res;↵
}↵
void solve()↵
{↵
n=read();↵
m=read();↵
r=read();↵
c=read();↵
princh(qpow(2,(1ll*n*(c-1)+1ll*m*(r-1)-1ll*(c-1)*(r-1))%(mod-1)),'\n');↵
}↵
int main()↵
{↵
// freopen(".in","r",stdin);↵
// freopen(".out","w",stdout);↵
int T=read();↵
while(T--)solve();↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
### [Div1A. Nim Game Is XOR Game](https://codeforces.me/contest/2239/problem/A)↵
↵
Author: [user:Gold14526,2026-06-27] Preparation: [user:Gold14526,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239A]↵
</spoiler>↵
↵
<spoiler summary="Code (by Gold14526)">↵
~~~~~↵
#include<bits/stdc++.h>↵
#define cint const int↵
#define uint unsigned int↵
#define cuint const unsigned int↵
#define ll long long↵
#define cll const long long↵
#define ull unsigned long long↵
#define cull const unsigned long long↵
using namespace std;↵
namespace FastIO↵
{↵
const int BUF_SIZE=1<<20;↵
char in_buf[BUF_SIZE],out_buf[BUF_SIZE];↵
char* in_ptr=in_buf+BUF_SIZE;↵
char* out_ptr=out_buf;↵
char get_char()↵
{↵
if(in_ptr==in_buf+BUF_SIZE)↵
{↵
in_ptr=in_buf;↵
fread(in_buf,1,BUF_SIZE,stdin);↵
}↵
return *in_ptr++;↵
}↵
void put_char(char c)↵
{↵
if(out_ptr==out_buf+BUF_SIZE)↵
{↵
fwrite(out_buf,1,BUF_SIZE,stdout);↵
out_ptr=out_buf;↵
}↵
*out_ptr++=c;↵
}↵
struct Flusher↵
{↵
~Flusher()↵
{↵
if(out_ptr!=out_buf)↵
{↵
fwrite(out_buf,1,out_ptr-out_buf,stdout);↵
}↵
}↵
} flusher;↵
}↵
#define getchar FastIO::get_char↵
#define putchar FastIO::put_char↵
inline int read()↵
{↵
int x=0;↵
bool zf=1;↵
char ch=getchar();↵
while(ch<'0'||ch>'9')↵
{↵
if(ch=='-')↵
{↵
zf=0;↵
}↵
ch=getchar();↵
}↵
while(ch>='0'&&ch<='9')↵
{↵
x=(x<<1)+(x<<3)+(ch^48);↵
ch=getchar();↵
}↵
return zf?x:-x;↵
}↵
void print(cint x)↵
{↵
if(x==0)↵
{↵
putchar('0');↵
return;↵
}↵
char buf[12];↵
int len=0,y=x;↵
if(y<0)↵
{↵
putchar('-');↵
y=-y;↵
}↵
while(y)↵
{↵
buf[len++]=(y%10)+'0';↵
y/=10;↵
}↵
while(len--)↵
{↵
putchar(buf[len]);↵
}↵
}↵
inline void princh(cint x,const char ch)↵
{↵
print(x);↵
putchar(ch);↵
}↵
cint N=1e6;↵
int n,a[N+1],s,ans;↵
void solve()↵
{↵
n=read();↵
s=0;↵
ans=0;↵
for(int i=1;i<=n;++i)s^=(a[i]=read());↵
if(n==1)↵
{↵
princh(0,'\n');↵
return;↵
}↵
if(!s)↵
{↵
princh(1,'\n');↵
return;↵
}↵
for(int i=1;i<=n;++i)↵
{↵
if((s^a[i])<a[i])++ans;↵
}↵
princh(ans,'\n');↵
}↵
int main()↵
{↵
// freopen(".in","r",stdin);↵
// freopen(".out","w",stdout);↵
int T=read();↵
while(T--)solve();↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
### [Div1B. Decidophobia](https://codeforces.me/contest/2239/problem/B)↵
↵
Author: [user:Gold14526,2026-06-27] Preparation: [user:Gold14526,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
How does everyone’s contribution change when you give a gift to someone?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239B]↵
</spoiler>↵
↵
<spoiler summary="Code (by Gold14526)">↵
~~~~~↵
#include<bits/stdc++.h>↵
#define cint const int↵
#define uint unsigned int↵
#define cuint const unsigned int↵
#define ll long long↵
#define cll const long long↵
#define ull unsigned long long↵
#define cull const unsigned long long↵
#define sh short↵
#define csh const short↵
#define ush unsigned short↵
#define cush const unsigned short↵
using namespace std;↵
namespace FastIO↵
{↵
const int BUF_SIZE=1<<20;↵
char in_buf[BUF_SIZE],out_buf[BUF_SIZE];↵
char* in_ptr=in_buf+BUF_SIZE;↵
char* out_ptr=out_buf;↵
char get_char()↵
{↵
if(in_ptr==in_buf+BUF_SIZE)↵
{↵
in_ptr=in_buf;↵
fread(in_buf,1,BUF_SIZE,stdin);↵
}↵
return *in_ptr++;↵
}↵
void put_char(char c)↵
{↵
if(out_ptr==out_buf+BUF_SIZE)↵
{↵
fwrite(out_buf,1,BUF_SIZE,stdout);↵
out_ptr=out_buf;↵
}↵
*out_ptr++=c;↵
}↵
struct Flusher↵
{↵
~Flusher()↵
{↵
if(out_ptr!=out_buf)↵
{↵
fwrite(out_buf,1,out_ptr-out_buf,stdout);↵
}↵
}↵
} flusher;↵
}↵
#define getchar FastIO::get_char↵
#define putchar FastIO::put_char↵
inline int read()↵
{↵
int x=0;↵
bool zf=1;↵
char ch=getchar();↵
while(ch<'0'||ch>'9')↵
{↵
if(ch=='-')↵
{↵
zf=0;↵
}↵
ch=getchar();↵
}↵
while(ch>='0'&&ch<='9')↵
{↵
x=(x<<1)+(x<<3)+(ch^48);↵
ch=getchar();↵
}↵
return zf?x:-x;↵
}↵
void print(cll x)↵
{↵
if(x==0)↵
{↵
putchar('0');↵
return;↵
}↵
char buf[20];↵
int len=0;↵
ll y=x;↵
if(y<0)↵
{↵
putchar('-');↵
y=-y;↵
}↵
while(y)↵
{↵
buf[len++]=(y%10)+'0';↵
y/=10;↵
}↵
while(len--)↵
{↵
putchar(buf[len]);↵
}↵
}↵
inline void princh(cll x,const char ch)↵
{↵
print(x);↵
putchar(ch);↵
}↵
cint N=6e5;↵
int n,d;↵
int a[N+1];↵
ll s[N+1],val[N+1];↵
ll ans;↵
void solve()↵
{↵
n=read();↵
d=read();↵
for(int i=1;i<=n;++i)↵
{↵
a[i]=a[i+n]=a[i+(n<<1)]=read();↵
}↵
for(int i=1;i<=n*3;++i)s[i]=s[i-1]+a[i];↵
for(int i=n+1;i<=(n<<1);++i)↵
{↵
val[i-n]=1ll*(d<<1|1)*a[i]-(s[i+d]-s[i-d-1]);↵
}↵
ans=0;↵
for(int i=1;i<=n;++i)ans+=max(0ll,val[i]);↵
princh(ans,'\n');↵
}↵
int main()↵
{↵
//freopen(".in","r",stdin);↵
//freopen(".out","w",stdout);↵
int T=read();↵
while(T--)solve();↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
### [Div1C. Revival](https://codeforces.me/contest/2239/problem/C)↵
↵
Author: [user:Gold14526,2026-06-27] Preparation: [user:Gold14526,2026-06-27]↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Consider doing the transitions from back to front.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
We only need to support the following operations:↵
↵
- Add and delete edges;↵
- Query the maximum value in a connected component;↵
- Take the max of all weights in a connected component with a given number.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Consider modifying the dynamic graph connectivity approach.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239E]↵
</spoiler>↵
↵
### [Div1F. Colorful Works](https://codeforces.me/contest/2239/problem/F)↵
↵
Author: [user:Milkcat2009,2026-06-27] Preparation: [user:Milkcat2009,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
Consider the case where $l_i=0$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Just Consider the most straightforward DP approach, and then try to find some patterns.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Try transforming the modulo $2$ counting DP into a game and solve it.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
You should already know the answer for $l_i=0$; try using the Principle of Inclusion-Exclusion to count.↵
</spoiler>↵
↵
<spoiler summary="Hint 5">↵
Enumerate which element is strictly greater than half of the total sum.↵
</spoiler>↵
↵
<spoiler summary="Hint 6">↵
You should already know the $O(nm/w)$ algorithm. Consider that, under modulo $2$, we have $(1+x^k)^2=1+x^{2k}$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239F]
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239C]↵
</spoiler>↵
↵
<spoiler summary="Code (by Gold14526)">↵
~~~~~↵
#include<bits/stdc++.h>↵
#define cint const int↵
#define uint unsigned int↵
#define cuint const unsigned int↵
#define ll long long↵
#define cll const long long↵
#define ull unsigned long long↵
#define cull const unsigned long long↵
#define sh short↵
#define csh const short↵
#define ush unsigned short↵
#define cush const unsigned short↵
using namespace std;↵
namespace FastIO↵
{↵
const int BUF_SIZE=1<<20;↵
char in_buf[BUF_SIZE],out_buf[BUF_SIZE];↵
char* in_ptr=in_buf+BUF_SIZE;↵
char* out_ptr=out_buf;↵
char get_char()↵
{↵
if(in_ptr==in_buf+BUF_SIZE)↵
{↵
in_ptr=in_buf;↵
fread(in_buf,1,BUF_SIZE,stdin);↵
}↵
return *in_ptr++;↵
}↵
void put_char(char c)↵
{↵
if(out_ptr==out_buf+BUF_SIZE)↵
{↵
fwrite(out_buf,1,BUF_SIZE,stdout);↵
out_ptr=out_buf;↵
}↵
*out_ptr++=c;↵
}↵
struct Flusher↵
{↵
~Flusher()↵
{↵
if(out_ptr!=out_buf)↵
{↵
fwrite(out_buf,1,out_ptr-out_buf,stdout);↵
}↵
}↵
} flusher;↵
}↵
#define getchar FastIO::get_char↵
#define putchar FastIO::put_char↵
inline ll read()↵
{↵
ll x=0;↵
bool zf=1;↵
char ch=getchar();↵
while(ch<'0'||ch>'9')↵
{↵
if(ch=='-')↵
{↵
zf=0;↵
}↵
ch=getchar();↵
}↵
while(ch>='0'&&ch<='9')↵
{↵
x=(x<<1)+(x<<3)+(ch^48);↵
ch=getchar();↵
}↵
return zf?x:-x;↵
}↵
void print(cint x)↵
{↵
if(x==0)↵
{↵
putchar('0');↵
return;↵
}↵
char buf[12];↵
int len=0,y=x;↵
if(y<0)↵
{↵
putchar('-');↵
y=-y;↵
}↵
while(y)↵
{↵
buf[len++]=(y%10)+'0';↵
y/=10;↵
}↵
while(len--)↵
{↵
putchar(buf[len]);↵
}↵
}↵
inline void princh(cint x,const char ch)↵
{↵
print(x);↵
putchar(ch);↵
}↵
cint N=1e6;↵
int n;↵
ll val[N+1];↵
char type[N+1];↵
int ans[N+1];↵
struct Binary_Index_Tree{↵
int a[N+1];↵
void clear()↵
{↵
for(int i=1;i<=n;++i)a[i]=0;↵
}↵
inline void add(cint x,cint y)↵
{↵
for(int i=x;i<=n;i+=(i&-i))a[i]+=y;↵
}↵
inline int ask(cint x)↵
{↵
int s=0;↵
for(int i=x;i;i-=(i&-i))s+=a[i];↵
return s;↵
}↵
inline int find(int x)↵
{↵
int res=0;↵
for(int len=1<<__lg(n);len;len>>=1)↵
{↵
if(res+len>n)continue;↵
if(a[res+len]<=x)↵
{↵
res+=len;↵
x-=a[res];↵
}↵
}↵
return res+1;↵
}↵
}T;↵
int lst[N+1];↵
void solve()↵
{↵
n=read();↵
T.clear();↵
for(int i=1;i<=n;++i)↵
{↵
char ch=getchar();↵
while(ch!='p'&&ch!='s')ch=getchar();↵
type[i]=ch;↵
val[i]=read();↵
if(type[i]=='p')ans[i]=val[i];↵
else val[i]=1ll*i*(i-1)/2-val[i];↵
}↵
for(int i=1;i<=n;++i)lst[i]=(type[i]=='s'?i:lst[i-1]);↵
for(int i=1;i<=n;++i)T.add(i,1);↵
for(int i=lst[n]+1;i<=n;++i)T.add(ans[i],-1);↵
for(int i=lst[n];i;i=lst[i-1])↵
{↵
cint p=lst[i-1];↵
ll d=val[i]-val[p];↵
for(int j=i-1;j>p;--j)↵
{↵
d-=T.ask(ans[j]-1);↵
T.add(ans[j],-1);↵
}↵
d+=i-p-1;↵
for(int j=i-1;j>p;--j)T.add(ans[j],2);↵
ans[i]=T.find(d);↵
for(int j=i-1;j>p;--j)T.add(ans[j],-2);↵
T.add(ans[i],-1);↵
}↵
for(int i=1;i<=n;++i)↵
{↵
princh(ans[i]," \n"[i==n]);↵
}↵
}↵
int main()↵
{↵
//freopen(".in","r",stdin);↵
//freopen(".out","w",stdout);↵
int T=read();↵
while(T--)solve();↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
### [Div1D. Hunting the Beast](https://codeforces.me/contest/2239/problem/D)↵
↵
Author: [user:Milkcat2009,2026-06-27] Preparation: [user:Milkcat2009,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
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}$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
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.↵
↵
The answer is $1-n$, which you can try to prove.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Use the Binomial Theorem to simplify the sum.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239D]↵
</spoiler>↵
↵
<spoiler summary="Code (by Milkcat2009)">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)↵
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)↵
#define CUP(i, l, r) for (int i = (l); i < (r); ++ i)↵
#define fi first↵
#define se second↵
#define pb emplace_back↵
#define mems(x, v) memset((x), (v), sizeof(x))↵
#define memc(x, y) memcpy((x), (y), sizeof(x))↵
#define SZ(x) (int)(x).size()↵
#define ALL(x) (x).begin(), (x).end()↵
#define ppc(x) __builtin_popcount(x)↵
#define ctz(x) __builtin_ctz(x)↵
#define clz(x) __builtin_clz(x)↵
using namespace std;↵
namespace math {↵
typedef long long LL;↵
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; }↵
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; }↵
template <unsigned P = 0> struct mint {↵
unsigned v; static unsigned mod; mint() = default;↵
template <class T> mint(T x) { x %= (int)getmod(), v = x < 0 ? x + getmod() : x; }↵
constexpr static unsigned getmod() { if (P > 0) return P; else return mod; }↵
static void setmod(unsigned m) { mod = m; }↵
mint operator + () const { return *this; }↵
mint operator - () const { return mint(0) - *this; }↵
mint inv() const { return assert(v), qpow(*this, getmod() - 2); }↵
int val() const { return v; }↵
mint &operator += (const mint &q) { if (v += q.v, v >= getmod()) v -= getmod(); return *this; }↵
mint &operator -= (const mint &q) { if (v -= q.v, v >= getmod()) v += getmod(); return *this; }↵
mint &operator *= (const mint &q) { v = 1ull * v * q.v % getmod(); return *this; }↵
mint &operator /= (const mint &q) { return *this *= q.inv(); }↵
friend mint operator + (mint p, const mint &q) { return p += q; }↵
friend mint operator - (mint p, const mint &q) { return p -= q; }↵
friend mint operator * (mint p, const mint &q) { return p *= q; }↵
friend mint operator / (mint p, const mint &q) { return p /= q; }↵
friend bool operator == (const mint &p, const mint &q) { return p.v == q.v; }↵
friend bool operator != (const mint &p, const mint &q) { return p.v != q.v; }↵
friend bool operator < (const mint &p, const mint &q) { return p.v < q.v; }↵
friend bool operator > (const mint &p, const mint &q) { return p.v > q.v; }↵
friend bool operator <= (const mint &p, const mint &q) { return p.v <= q.v; }↵
friend bool operator >= (const mint &p, const mint &q) { return p.v >= q.v; }↵
friend istream &operator >> (istream &is, mint &a) { LL x; is >> x, a = x; return is; }↵
friend ostream &operator << (ostream &os, const mint &a) { os << a.v; return os; }↵
};↵
template <> unsigned mint<0>::mod = 998244353;↵
template <typename MI>↵
struct Comb {↵
#define P MI::getmod()↵
vector<MI> fc, ifc;↵
void init(int n) {↵
fc.resize(n + 1), ifc.resize(n + 1), fc[0] = 1;↵
REP(i, 1, n) fc[i] = fc[i - 1] * i;↵
ifc[n] = fc[n].inv();↵
DEP(i, n, 1) ifc[i - 1] = ifc[i] * i;↵
}↵
MI operator () (LL n, LL m) {↵
if (m > n || m < 0 || n < 0) return 0;↵
if (n < P && m < P) { assert(n < SZ(fc)); return fc[n] * ifc[m] * ifc[n - m]; }↵
return (!n ? 1 : (*this)(n / P, m / P) * (*this)(n % P, m % P));↵
}↵
#undef P↵
};↵
namespace Z {↵
const int mod = 998244353;↵
using MI = mint<mod>; using math::qpow; Comb<MI> C;↵
MI fac(int x) { assert(x >= 0 && x < SZ(C.fc)); return C.fc[x]; }↵
MI ifc(int x) { assert(x >= 0 && x < SZ(C.ifc)); return C.ifc[x]; }↵
MI inv(int x) { assert(x && x < SZ(C.fc)); return C.ifc[x] * C.fc[x - 1]; }↵
MI sab(int x, int y) { return (!y ? !x : C(x + y - 1, y - 1)); }↵
}↵
}↵
namespace Milkcat {↵
using namespace math::Z;↵
typedef long long LL;↵
typedef pair<LL, LL> pii;↵
const int N = 1e7 + 5;↵
int n, m, t, v[N]; MI g[N];↵
void sieve(int n, int k, MI* f) {↵
vector<int> p; fill_n(v + 1, n, 0), f[1] = 1;↵
REP(i, 2, n) {↵
if (!v[i]) p.pb(i), f[i] = qpow((MI)i, k);↵
for (int j : p) {↵
if (i * j <= n) f[i * j] = f[i] * f[j], v[i * j] = 1;↵
if (i * j > n || i % j == 0) break;↵
}↵
}↵
}↵
MI slv2(int n, int m) {↵
MI rs = 0;↵
REP(i, 0, n - m)↵
rs += g[n - i - 1] * C(n - m, i) * (i & 1 ? -1 : 1);↵
return rs * (n - 1);↵
}↵
int main() {↵
cin >> t, C.init(1e6);↵
while (t --) {↵
cin >> n >> m, sieve(n, n - 1, g);↵
cout << slv2(n, m) * C(n, m) << '\n';↵
}↵
return 0;↵
}↵
}↵
int main() {↵
cin.tie(0)->sync_with_stdio(0);↵
int T = 1;↵
while (T --) Milkcat::main();↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
### [Div1E. The end of this world,](https://codeforces.me/contest/2239/problem/E)↵
↵
Author: [user:Gold14526,2026-06-27] Preparation: [user:Gold14526,2026-06-27]↵
↵
↵
<spoiler summary="Hint 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Consider doing the transitions from back to front.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
We only need to support the following operations:↵
↵
- Add and delete edges;↵
- Query the maximum value in a connected component;↵
- Take the max of all weights in a connected component with a given number.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Consider modifying the dynamic graph connectivity approach.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239E]↵
</spoiler>↵
↵
<spoiler summary="Code (by Gold14526)">↵
~~~~~↵
#include<bits/stdc++.h>↵
#define cint const int↵
#define uint unsigned int↵
#define cuint const unsigned int↵
#define ll long long↵
#define cll const long long↵
#define ull unsigned long long↵
#define cull const unsigned long long↵
using namespace std;↵
namespace FastIO↵
{↵
const int BUF_SIZE=1<<20;↵
char in_buf[BUF_SIZE],out_buf[BUF_SIZE];↵
char* in_ptr=in_buf+BUF_SIZE;↵
char* out_ptr=out_buf;↵
char get_char()↵
{↵
if(in_ptr==in_buf+BUF_SIZE)↵
{↵
in_ptr=in_buf;↵
fread(in_buf,1,BUF_SIZE,stdin);↵
}↵
return *in_ptr++;↵
}↵
void put_char(char c)↵
{↵
if(out_ptr==out_buf+BUF_SIZE)↵
{↵
fwrite(out_buf,1,BUF_SIZE,stdout);↵
out_ptr=out_buf;↵
}↵
*out_ptr++=c;↵
}↵
struct Flusher↵
{↵
~Flusher()↵
{↵
if(out_ptr!=out_buf)↵
{↵
fwrite(out_buf,1,out_ptr-out_buf,stdout);↵
}↵
}↵
} flusher;↵
}↵
#define getchar FastIO::get_char↵
#define putchar FastIO::put_char↵
inline int read()↵
{↵
int x=0;↵
bool zf=1;↵
char ch=getchar();↵
while(ch<'0'||ch>'9')↵
{↵
if(ch=='-')↵
{↵
zf=0;↵
}↵
ch=getchar();↵
}↵
while(ch>='0'&&ch<='9')↵
{↵
x=(x<<1)+(x<<3)+(ch^48);↵
ch=getchar();↵
}↵
return zf?x:-x;↵
}↵
void print(cint x)↵
{↵
if(x==0)↵
{↵
putchar('0');↵
return;↵
}↵
char buf[12];↵
int len=0,y=x;↵
if(y<0)↵
{↵
putchar('-');↵
y=-y;↵
}↵
while(y)↵
{↵
buf[len++]=(y%10)+'0';↵
y/=10;↵
}↵
while(len--)↵
{↵
putchar(buf[len]);↵
}↵
}↵
inline void princh(cint x,const char ch)↵
{↵
print(x);↵
putchar(ch);↵
}↵
cint N=5e5,M=5e5,H=20;↵
int n,m;↵
int val[N+1];↵
int eu[M+1],ev[M+1],low[M+1],lim[M+1];↵
int tl[M+1],tr[M+1];↵
struct dx{↵
int idx,val;↵
}c[M<<1|1];↵
struct edge{↵
int u,v,l,r;↵
};↵
vector<edge>E,EL[H+1],ER[H+1];↵
struct info{↵
int t,u;↵
}mdf[M+1];↵
int tag[N+(M<<2|1)],mx[N+(M<<2|1)];↵
int fa[N+(M<<2|1)];↵
int tot;↵
int top[N+(M<<2|1)];↵
int head[N+(M<<2|1)];↵
struct et{↵
int to,nxt;↵
}ve[M<<2|1];↵
int ct;↵
inline void add_edge(cint u,cint v)↵
{↵
ve[++ct]={v,head[u]};↵
head[u]=ct;↵
ve[++ct]={u,head[v]};↵
head[v]=ct;↵
}↵
inline int newv()↵
{↵
++tot;↵
tag[tot]=-1;↵
mx[tot]=fa[tot]=0;↵
return tot;↵
}↵
struct stck{↵
int a[N+1],t;↵
inline void clear(){t=0;}↵
inline int top(){return a[t];}↵
inline void pop(){--t;}↵
inline void push(cint x){a[++t]=x;}↵
inline bool empty(){return (t==0);}↵
}st;↵
void dfs(cint u)↵
{↵
top[u]=u;↵
st.clear();↵
st.push(u);↵
while(!st.empty())↵
{↵
cint s=st.top();↵
st.pop();↵
for(int i=head[s];i;i=ve[i].nxt)↵
{↵
cint v=ve[i].to;↵
if(top[v])continue;↵
top[v]=u;↵
st.push(v);↵
}↵
}↵
}↵
void update(cint h,cint l,cint r,vector<edge>&E,int m,cint vl,cint vr)↵
{↵
if(E.empty())↵
{↵
for(int i=1;i<=m;++i)↵
{↵
tag[mdf[i].u]=max(tag[mdf[i].u],mx[mdf[i].u]+c[l].val);↵
}↵
return;↵
}↵
cint mid=l+r>>1;↵
EL[h].clear();↵
ER[h].clear();↵
for(int i=vl;i<=vr;++i)↵
{↵
head[i]=top[i]=fa[i]=0;↵
}↵
ct=0;↵
for(edge &e:E)↵
{↵
if(e.l<=l&&e.r>=r)↵
{↵
add_edge(e.u,e.v);↵
}↵
else↵
{↵
if(e.l<=mid)EL[h].push_back(e);↵
if(e.r>mid)ER[h].push_back(e);↵
}↵
}↵
for(int i=vl;i<=vr;++i)↵
{↵
if(!top[i])dfs(i);↵
}↵
if(l==r)↵
{↵
for(int i=vl;i<=vr;++i)mx[top[i]]=max(mx[top[i]],mx[i]);↵
for(int i=1;i<=m;++i)↵
{↵
cint u=top[mdf[i].u];↵
tag[u]=max(tag[u],mx[u]+c[l].val);↵
}↵
for(int i=vl;i<=vr;++i)↵
{↵
tag[i]=max(tag[i],tag[top[i]]);↵
mx[i]=max(mx[i],mx[top[i]]);↵
}↵
return;↵
}↵
cint tmp=tot;↵
for(edge &e:ER[h])↵
{↵
cint u=top[e.u],v=top[e.v];↵
if(!fa[u])fa[u]=newv();↵
if(!fa[v])fa[v]=newv();↵
e.u=fa[u];↵
e.v=fa[v];↵
}↵
int pm=0;↵
for(int i=1;i<=m;++i)↵
{↵
info &p=mdf[i];↵
if(p.t>mid)↵
{↵
cint u=top[p.u];↵
if(!fa[u])fa[u]=newv();↵
p.u=fa[u];↵
swap(p,mdf[++pm]);↵
}↵
}↵
for(int i=vl;i<=vr;++i)↵
{↵
cint u=fa[top[i]];↵
if(u)mx[u]=max(mx[u],mx[i]);↵
}↵
update(h+1,mid+1,r,ER[h],pm,tmp+1,tot);↵
for(int i=vl;i<=vr;++i)↵
{↵
cint u=fa[top[i]];↵
if(u)mx[i]=max(mx[i],mx[u]),tag[i]=max(tag[i],tag[u]);↵
}↵
tot=tmp;↵
for(int i=vl;i<=vr;++i)fa[i]=0;↵
for(edge &e:EL[h])↵
{↵
cint u=top[e.u],v=top[e.v];↵
if(!fa[u])fa[u]=newv();↵
if(!fa[v])fa[v]=newv();↵
e.u=fa[u];↵
e.v=fa[v];↵
}↵
for(int i=pm+1;i<=m;++i)↵
{↵
info &p=mdf[i];↵
cint u=top[p.u];↵
if(!fa[u])fa[u]=newv();↵
p.u=fa[u];↵
swap(p,mdf[i-pm]);↵
}↵
pm=m-pm;↵
for(int i=vl;i<=vr;++i)↵
{↵
cint u=fa[top[i]];↵
if(u)mx[u]=max(mx[u],mx[i]);↵
}↵
update(h+1,l,mid,EL[h],pm,tmp+1,tot);↵
for(int i=vl;i<=vr;++i)↵
{↵
cint u=fa[top[i]];↵
if(u)mx[i]=max(mx[i],mx[u]),tag[i]=max(tag[i],tag[u]);↵
}↵
tot=tmp;↵
}↵
void solve()↵
{↵
tag[0]=-1;↵
tot=n=read();↵
m=read();↵
for(int i=1;i<=n;++i)val[i]=read(),tag[i]=-1,mx[i]=val[i];↵
for(int i=1;i<=m;++i)↵
{↵
eu[i]=read(),ev[i]=read(),lim[i]=read(),low[i]=read();↵
c[i]={i,lim[i]};↵
c[i+m]={i+m,low[i]};↵
}↵
sort(c+1,c+(m<<1|1),[&](dx p,dx q){return (p.val==q.val?p.idx>q.idx:p.val<q.val);});↵
for(int i=1;i<=(m<<1);++i)↵
{↵
if(c[i].idx>m)tl[c[i].idx-m]=i;↵
else tr[c[i].idx]=i;↵
}↵
E.clear();↵
for(int i=1;i<=m;++i)↵
{↵
E.push_back({eu[i],ev[i],tl[i],tr[i]});↵
mdf[i]={tr[i],eu[i]};↵
}↵
if(m)update(0,1,m<<1,E,m,1,n);↵
for(int i=1;i<=n;++i)princh(tag[i]," \n"[i==n]);↵
}↵
int main()↵
{↵
// freopen(".in","r",stdin);↵
// freopen(".out","w",stdout);↵
int T=read();↵
while(T--)solve();↵
return 0;↵
}↵
↵
↵
~~~~~↵
↵
</spoiler>↵
↵
### [Div1F. Colorful Works](https://codeforces.me/contest/2239/problem/F)↵
↵
Author: [user:Milkcat2009,2026-06-27] Preparation: [user:Milkcat2009,2026-06-27]↵
↵
<spoiler summary="Hint 1">↵
Consider the case where $l_i=0$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Just Consider the most straightforward DP approach, and then try to find some patterns.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Try transforming the modulo $2$ counting DP into a game and solve it.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
You should already know the answer for $l_i=0$; try using the Principle of Inclusion-Exclusion to count.↵
</spoiler>↵
↵
<spoiler summary="Hint 5">↵
Enumerate which element is strictly greater than half of the total sum.↵
</spoiler>↵
↵
<spoiler summary="Hint 6">↵
You should already know the $O(nm/w)$ algorithm. Consider that, under modulo $2$, we have $(1+x^k)^2=1+x^{2k}$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2239F]↵
</spoiler>↵
↵
<spoiler summary="Code (by Milkcat2009)">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)↵
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)↵
#define CUP(i, l, r) for (int i = (l); i < (r); ++ i)↵
#define fi first↵
#define se second↵
#define pb emplace_back↵
#define mems(x, v) memset((x), (v), sizeof(x))↵
#define memc(x, y) memcpy((x), (y), sizeof(x))↵
#define SZ(x) (int)(x).size()↵
#define ALL(x) (x).begin(), (x).end()↵
#define ppc(x) __builtin_popcount(x)↵
#define ctz(x) __builtin_ctz(x)↵
#define clz(x) __builtin_clz(x)↵
using namespace std;↵
namespace Milkcat {↵
typedef long long LL;↵
typedef pair<LL, LL> pii;↵
const int N = 2e6 + 5, M = 2e5 + 5;↵
int n, m, rs, d, p, q, l[N], r[N], c[M];↵
bitset<M> f;↵
int val(int x) { x -= d; return (x >= 0 && x <= m ? f[x] : 0); }↵
int main() {↵
cin >> n;↵
REP(i, 1, n)↵
cin >> l[i] >> r[i], m = max(m, r[i]);↵
REP(i, 1, n) {↵
if (!l[i]) d = min(d + r[i], (int)1e9);↵
else d = min(d + l[i] - 1, (int)1e9), c[r[i] - l[i] + 1] ++;↵
}↵
f = 1;↵
REP(i, 1, m) {↵
if (i * 2 <= m) c[i * 2] += c[i] >> 1;↵
if (c[i] & 1) f ^= f << i;↵
}↵
REP(i, 2, m) f[i] = f[i] ^ f[i - 2];↵
REP(i, 1, n) {↵
if (!l[i]) rs ^= val(r[i] * 2 - 2), p ^= r[i] & 1;↵
else rs ^= val(l[i] + r[i] - 1 - 2), q += ((l[i] & 1) == (r[i] & 1) ? 1 : 2);↵
}↵
cout << (rs ^ (!q ? !p : (q < 2))) << '\n';↵
REP(i, 1, m) c[i] = 0;↵
m = rs = d = p = q = 0;↵
return 0;↵
}↵
}↵
int main() {↵
cin.tie(0)->sync_with_stdio(0);↵
int T = 1; cin >> T;↵
while (T --) Milkcat::main();↵
return 0;↵
}↵
↵
↵
~~~~~↵
↵
</spoiler>↵
↵
