【0】做题心得 - 2025 NOIP #69 - T2【容斥原理】

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
ull seed; ll mod,l,r;
ull shift(){
    seed^=seed<<13;
    seed^=seed>>7;
    seed^=seed<<17;
    return seed;
}
void read(){
    l=shift()%mod+1,r=shift()%mod+1;
    if(l>r) swap(l,r);
}
ll t,T,n,ans[105];
ll solve(ll lm){
    ll res=max(0ll,lm-99);
    lm=min(lm,99ll);
	return res+ans[lm];
}
int main(){
    freopen("you.in","r",stdin);
    freopen("you.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	cin>>t>>T>>seed>>mod;
    for(int i=1;i<=100;i++){
        int c0=0,c1=0,c2=0,su=0;
        string ti=to_string(i);
        for(auto j:ti){
            su+=j-'0';
            if(su%3==0) c0++;
            else if(su%3==1) c1++;
            else if(su%3==2) c2++;
        }
        if(c0||c1==2||c2==2) ans[i]++;
    }
    for(int i=1;i<=100;i++) ans[i]+=ans[i-1];
	while(t--){
		cin>>l>>r;
		cout<<(solve(r)-solve(l-1))<<"\n";
	}
	ull ans=0;
	while(T--){
		read();
		ans^=(solve(r)-solve(l-1));
	}
	cout<<ans;
    return 0;
}