[JZOJ 5894] [NOIP2018模拟10.5] 同余方程 解题报告（容斥）

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

const int N=60;
const int mod=998244353;
ll m;
ll bin[N],p[N];
int a[N],b[N];
ll get(ll l,ll r)
{
    if (l>r) return 0;
    if (l) return (r/m-(l-1)/m)%mod;
    else return (r/m+1)%mod;//要考虑0
}
ll calc(ll l,ll r)
{
    int A=-1,B=-1;
    ll res=0,S=l^r;
    while (l)
    {
        a[++A]=l&1;
        l>>=1;
    }
    while (r)
    {
        b[++B]=r&1;
        r>>=1;
    }
    for (int i=0;i<=A;i++) 
    if (a[i]) res=(res+get(((S/p[i])*p[i])^p[i],((S/p[i])*p[i])^p[i]+p[i]-1))%mod;//j==r
    for (int i=0;i<=B;i++)
    if (b[i]) res=(res+get(((S/p[i])*p[i])^p[i],((S/p[i])*p[i])^p[i]+p[i]-1))%mod;//i==l
    for (int i=0;i<=A;i++)
        if (a[i])
            for (int j=0;j<=B;j++)
                if (b[j])
                {
                    int mx=max(i,j);//特判i==j
                    if (i!=j) res=(res+get(((S/p[mx])*p[mx])^p[mx],((S/p[mx])*p[mx])^p[mx]+p[mx]-1)*bin[min(i,j)])%mod;
                    else res=(res+get(((S/p[mx])*p[mx]),((S/p[mx])*p[mx])+p[mx]-1)*bin[min(i,j)])%mod;
                }
    return res+((S%m)==0);//i==l&&j==r
}
int main()
{
    freopen("mod.in","r",stdin);
    freopen("mod.out","w",stdout);
    p[0]=1;bin[0]=1;
    for (int i=1;i<N;i++) 
    {
        p[i]=p[i-1]<<1;
        bin[i]=p[i]%mod;
    }
    ll l1,r1,l2,r2;
    scanf("%lld%lld%lld%lld%lld",&l1,&r1,&l2,&r2,&m);
    printf("%lld\n",((calc(r1,r2)-calc(l1-1,r2)-calc(r1,l2-1)+calc(l1-1,l2-1))%mod+mod)%mod);
    return 0;
}