位运算相关

牛客NOIP模拟第五场T1

Description

给定\(l_1,r_1,l_2,r_2,m\) 求\(）\sum \limits _{x=l_1}^{r_1}\sum \limits _{y=l_2}^{r_2} (x*y\%m=0）\)

• \(l_1\le r_1 \le 10^{18},l_2\le r_2\le 10^{18},m\le 10^9\)

Solution

约定 \(num(a,t)\) 为01串\(a\)长度为\(t\)的前缀

• 性质1：对于01串 \(a\),\(b\) 取二者的前缀长度为\(t_1\),\(t_2\) , 前缀后的位置01随意构造，对于每个能异或出的数，方案数为 \(2^{min(t_1,t_2)}\)

• 性质2：对于01串 \(a\),\(b\) 取二者的前缀长度为\(t_1\),\(t_2\) ,

  \(Dim：\)

  • $s=num(a,min(t_1,t_2)) \wedge num(b,min(t_1,t_2)) $
  • \(x\in [a<<min(t_1,t_2),a<<min(t_1,t_2)+2^{min(t_1,t_2)}-1]\)
  • \(y\in [b<<min(t_1,t_2),b<<min(t_1,t_2)+2^{min(t_1,t_2)}-1]\)

  则$ x\wedge y \in [s<<min(t_1,t_2),s<<min(t_1,t_2)+2^{min(t_1,t_2)}-1]$

• 根据性质2，可以算出可以取到多少种m的倍数，记为c，然后再根据性质1，方案数就为 \(c\times 2^{min(t_1,t_2)}\)

• 利用上述性质可以在\(O(count(10^{18})^2)\)的时间复杂度下求出 \(x\in [0,a] ,y\in[0,b]\) 的答案

• 方法是枚举 \(a\),\(b\) 为1的二进制位，把它变为0，那么后面的位置01就可以随便放，并且可以证明这样枚举出来的方案数是补充不漏的

Code

#include<cstdio>
#define FOR(i,x,y) for(int i=(x),i##_END=(y);i<=i##_END;i++)

const int P=998244353;
typedef long long LL;

int m;

LL calc(LL x){
    if(x<0)return -1;
    return x/m;
}

LL Solve(LL X,LL Y){
    LL res=0,x,y;
    FOR(i,0,60)if(X&(1ll<<i)){
        FOR(j,0,60)if(Y&(1ll<<j)){
            int mi=i<j?i:j,mx=i>j?i:j;
            if(i>j)x=X,y=Y;
            else x=Y,y=X;
            
            x>>=mx,y>>=mx;
            x^=1;
            if(i==j)y^=1;
            x^=y;
            x<<=mx;
            
            LL l,r;
            l=calc(x-1);
            r=calc(x+(1ll<<mx)-1);
            
            res=(res+(LL)(r-l)%P*((1ll<<mi)%P))%P;
        }
    }
    return res%P;
}


int main(){
    LL l1,r1,l2,r2;
    scanf("%lld%lld%lld%lld%d",&l1,&r1,&l2,&r2,&m);
    printf("%lld\n",((Solve(r1+1,r2+1)-Solve(r1+1,l2)-Solve(l1,r2+1)+Solve(l1,l2))%P+P)%P);
    return 0;
}

位运算相关

原文：https://www.cnblogs.com/Zerokei/p/9791899.html