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

ExFish · 2025-11-26 15:49:49 · 题解

嗯其实是因为一个性质：一个数的前缀和要是有两位 \bmod 3 相同，或者有一位 \bmod 3=0 就一定是你干的。然后根据这个定理显然容斥得三位数一定可以。然后就结束了。和一位我赛时没有过？？

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