JZOJ5894. 【NOIP2018模拟10.5】同餘方程

題解

很顯然，将詢問拆成四個形如（0-a，0-b）的形式，

針對詢問，類似數位dp的方式，

枚舉i，j，分别表示a在二進制下的前i位固定，b在二進制下的前j為固定，

剩下的位置就可以任意選。

可以使得，兩個數異或出來是連續的 2 m a x ( i , j ) 2^{max(i,j)} 2max(i,j)，而且每個數出現次數都是 2 m i n ( i , j ) 2^{min(i,j)} 2min(i,j)

然後連續一段數求m的倍數就可以用除法。

code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;

const int mo=998244353;
ll l1,l2,r1,r2,m,ans,z[80];

ll get(ll x,ll s)
{
	if(x==0)return (s-1)/m+1;else return (x+s-1)/m-(x-1)/m;
}

ll calc(ll a,ll b)
{
	ll aa=0,bb,p,len1,len2,sum=0;
	int mx,mi;
	for(len1=63;(a&z[len1])==0;len1--);
	for(len2=63;(b&z[len2])==0;len2--);
	for(int i=len1;i+1;i--)
	{
		aa=aa|(z[i]&a);
		if(z[i]&a) 
		{
			bb=0;
			for(int j=len2;j+1;j--)
			{
				bb=bb|(z[j]&b);
				if(z[j]&b)
				{
					mx=(i>j?i:j);mi=(i>j?j:i);
					p=((a^b^((i==j)?0:z[mx]))|(z[mx]-1))^(z[mx]-1);
					sum=(sum+get(p,z[mx])%mo*(z[mi]%mo)%mo)%mo;
				}
			}
		}
	}
	return sum;
}

int main()
{
	freopen("mod.in","r",stdin);
	freopen("mod.out","w",stdout);
	
	z[0]=1;
	for(int i=1;i<64;i++)z[i]=z[i-1]<<1;
	
	scanf("%lld%lld%lld%lld%lld",&l1,&r1,&l2,&r2,&m);
	
	ans=calc(r1+1,r2+1);
	ans=(ans-calc(r1+1,l2)-calc(l1,r2+1))%mo;
	ans=(ans+calc(l1,l2)+mo)%mo;
	
	printf("%lld\n",ans);
	return 0;
}