【牛客提高训练营5A】同余方程

吉老师的题做不动啊

首先\([l_1,r_1],[l_2,r_2]\)并不是非常好做，我们考虑将其拆成前缀信息

设\(solve(n,m)=\sum_{i=0}^n\sum_{j=0}^m[m|(i\bigoplus j)]\)

于是我们的答案就变成了\(solve(r_1,r_2)-solve(l_1-1,r_2)-solve(r_1,l_2-1)+solve(l_1-1,l_2-1)\)

考虑\(solve(r_1,r_2)\)怎么求

一个非常特殊的情况是\(r_1=2^n-1,r_2=2^m-1\)，不妨假设\(n<m\)，则\([0,2^n)\)和\([0,2^m)\)各选择一个数异或起来，能取遍\([0,2^m)\)，且每一个数出现的次数都是\(2^n\)

正确性显然

考虑推广到更一般的情况，我们把\([0,r_1)\)拆分一下，拆分成\(\log\)段\([v,v+2^k)\)的区间，比如说对于\(101010\)，可以拆成\([0,2^5),[2^5,2^5+2^3),[2^5+2^3,2^5+2^3+2^1)\)

这样的拆分有一个特点，如果有\(v\neq 0\)，那么一定会存在\(v>2^k\)，这个性质接下来非常重要

将\([0,r_1),[0,r_2)\)各拆成\(\log\)段区间后，我们暴力从两边各选一段区间出来，假设为\([x,x+2^a)\)和\([y,y+2^b)\)，还是不妨假设\(a<b\)

于是在忽略\(x,y\)的情况下两个区间变成了\([0,2^a),[0,2^b)\)，于是各选一个异或起来能取遍\([0,2^b)\)且每个值能被异或出来\(2^a\)次

现在考虑把\(x,y\)引入，不难发现因为\(x>2^a\)，所以从\([0,2^a)\)拿出一个数，加上\(x\)和异或\(x\)是等价的；\(y\)那边同理

于是\([0,2^b)\)中的每一个数拿出来和\(x\bigoplus y\)异或一下，就是真实的从\([x,x+2^a)\)和\([y,y+2^b)\)各拿一个数出来异或的结果。

所以现在只需要求出\([0,2^b)\)内有多少个满足异或\(x\bigoplus y\)后\(\rm mod\ m=0\)，这样的数的个数乘上\(2^a\)就是答案了。

做到这里就不会了，接下来都是祖特教我的。

我们不难发现\(x\bigoplus y\)如果不是\(0\)，则必然大于\(2^b\)，于是\(x\bigoplus y\)和\([0,2^b)\)内的数异或，必然不会改变必\(2^b\)更高的二进制位。

所以想要使得异或出来的数是\(m\)的倍数，只需要让\(x\bigoplus y\)小于\(2^b\)的位数从全\(0\)取到全\(1\)，从中选出\(m\)的倍数即可。

代码

#include<bits/stdc++.h>

#define re register

#define LL long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read() {

	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

const int mod=998244353;

inline int dqm(int x) {return x<0?x+mod:x;}

inline int qm(int x) {return x>=mod?x-mod:x;}

LL l1,l2,r1,r2;int m,top[2];

struct Seg{LL v,k;}a[2][65];

inline LL getid(LL a,LL b) {return a%b==0?a/b:a/b+1;}

inline LL solve(LL n,LL k)

{

    LL t=0,tot=0;

    for(re LL i=63;i>=0;i--)

    {

        t|=(1ll<<i);

        if(!(n&(1LL<<i))) continue;

        LL l=k&t,r=l+(1ll<<i)-1;

        LL L=getid(l,m),R=r/m;

        tot=qm(tot+(R-L+1)%mod);

    }

    return tot;

}

inline int calc(LL n,LL m) {

	++n,++m;int ans=0;

	top[0]=top[1]=0;

	LL now=0;

	for(re LL i=63;i>=0;--i)

	if(n>>i&1ll) {

		a[0][++top[0]].v=now,a[0][top[0]].k=i;

		now|=(1ll<<i);

	}

	now=0;

	for(re LL i=63;i>=0;--i)

	if(m>>i&1ll) {

		a[1][++top[1]].v=now,a[1][top[1]].k=i;

		now|=(1ll<<i);

	}

	for(re int i=1;i<=top[0];++i)

		for(re int j=1;j<=top[1];++j) {

			now=a[0][i].v^a[1][j].v;

			LL mx=max(a[0][i].k,a[1][j].k),mn=min(a[0][i].k,a[1][j].k);

			mn=(1ll<<mn);mn%=mod;

			ans=qm(ans+1ll*solve(1ll<<mx,now)%mod*mn%mod);

		}

	return ans;

}

int main() {

	scanf("%lld%lld%lld%lld%d",&l1,&r1,&l2,&r2,&m);

	printf("%d\n",dqm(qm(calc(r1,r2)+calc(l1-1,l2-1))-qm(calc(l1-1,r2)+calc(r1,l2-1))));

	return 0;

}

巴特西

【牛客提高训练营5A】同余方程

最新文章

热门文章