Consider each binary bit independently.

Think about a greedy approach.

/*
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;
}

Try some special cases, such as $$$r=c=2$$$, $$$n=r$$$, or $$$m=c$$$, etc.

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)}$$$.

#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;
}

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.

#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;
}

How does everyone’s contribution change when you give a gift to someone?

#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;
}

Consider determining all the numbers from back to front.

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.

#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;
}

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}$$$.

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.

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.

Use the Binomial Theorem to simplify the sum.

#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;
}

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.

Consider doing the transitions from back to front.

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.

Consider modifying the dynamic graph connectivity approach.

#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;
}

Consider the case where $$$l_i=0$$$.

Just Consider the most straightforward DP approach, and then try to find some patterns.

Try transforming the modulo $$$2$$$ counting DP into a game and solve it.

You should already know the answer for $$$l_i=0$$$; try using the Principle of Inclusion-Exclusion to count.

Enumerate which element is strictly greater than half of the total sum.

You should already know the $$$O(nm/w)$$$ algorithm. Consider that, under modulo $$$2$$$, we have $$$(1+x^k)^2=1+x^{2k}$$$.

#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;
}