题目链接：
题目：
题解：（部分内容来自0）
首先我们容斥一下，设calc(l,r)为i∈[1,l],j∈[q,r]的方程的解的个数，显然答案等于calc(r2,r1)-calc(l1-1,r2)-calc(r1,l2-1)+calc(l1-1,l2-1)
考虑如何计算calc(l,r)
对于l和r，从低位向高位枚举每一个二进制位1，强制把这个1改成0，这样可以保证得到的数小于原来的数并且没有算重。假设l改变第i位，r改变第j位
（假设l不同的位比r后）
那么用红框表示已知部分，蓝框表示未知部分
所以异或之后就会变成这样
中间的紫色部分表示一半已知，一半未知，后面的蓝色部分表示完全未知
显然未知部分可以取到任何可能
考虑中间的紫色部分，由于$a$紫色部分确定，$b$紫色部分不确定，那么对于每一个$b$的紫色部分都对应一个$c$的紫色部分
也就是说，每一个$b$确定$2^{蓝色部分长度}$个$c$，且我们一共有$2^{max(i,j)}-1$个$b$。由于未知部分可以取到任何可能，所以我们一共有$2^{max(i,j)}-1$个$c$
考虑到每个c肯定是平等的，那么每个c就被计算了$\frac{2^{蓝色部分长度} \times (2^{max(i,j)}-1)}{2^{max(i,j)}-1}=2^{蓝色部分长度}$次
$mx=max(i,j)$,发现c的取值就是[((S/p[mx])*mx)^p[mx],((S/p[mx])*mx)^p[mx]+p[mx]-1],p[mx]=1<<mx
注意到第mx位是需要和原来相反的，所以要^p[mx]
还有三种情况
1.i==j
这个其实差不多，只是第mx位不需要取反，也就是不需要^p[mx]
2.a或b不改任何一位
这个也是一样的，注意一下变的那一个枚举的任何一位都需要取反
3.a和b都不变
这个直接异或一下直接判断就是了
#include#include #include #include 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;//b不变 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;//a不变 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