Description：

求方程 $x\text{ xor }y\equiv0\mod m$ 的解数。 $x\in[l_1,r_1],y\in[l_2,r_2]$

$1\leqslant l_1,r_1,l_2,r_2\leqslant10^{18},1\leqslant m\leqslant10^9$

Solution：

首先考虑 $x\in[0,2^k),y\in[0,2^k)$ ，那么 $x\text{ xor }y$ 的值 $[0,2^k)$ 每个数都出现了 $2^k$ 次，如果 $x\in[0,2^n),$ $y\in[0,2^m),$ $(n<m)$ ，那么 $x\text{ xor }y$ 的值 $[0,2^m)$ 每个数都出现了 $2^n$ 次，两个 $w$ 位二进制数 $a$ 和 $b$ ，如果 $a$ 第 $i$ 位为 $1$ ， $b$ 第 $j$ 位为 $1$ $(i<j)$ ，那么类似数位 $DP$ 就可以统计 $a[i,w][0,2^i)$ 和 $b[j,w][0,2^j)$ 对答案的贡献，那么这些所有的数能组合出 $\biggl[a[j,w]\text{ xor }b[j,w]\biggl][0,2^j)$ 的所有数，且每个数都出现了 $2^i$ 次，这样把二维区间和拆成四个二位前缀和统计即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

ll l1,r1,l2,r2,m;

#define MOD 998244353

ll query(ll l,ll r,ll m)

{

	return (r / m - l / m + (l % m == 0 ? 1 : 0)) % MOD;

}

ll calc(ll x,ll y)

{

	ll res = 0;

	for(ll i = 0;i <= 60;++i)

	{

		for(ll j = 0;j <= 60;++j)

		{

			if(((x >> i) & 1) && ((y >> j) & 1))

			{

				ll high = max(i,j),low = min(i,j);

				ll high_bits = ~((1ll << high) - 1);

				ll high_val = ((x - (1ll << i)) & high_bits) ^ ((y - (1ll << j)) & high_bits);

				res = (res + query(high_val,high_val | ((1ll << high) - 1),m) * ((1ll << min(i,j)) % MOD) % MOD) % MOD;

			}

		}

	}

	return res;

}

int main()

{

	freopen("A.in","r",stdin);

	freopen("A.out","w",stdout);

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

	ll res = calc(r1 + 1,r2 + 1) - calc(l1,r2 + 1) - calc(r1 + 1,l2) + calc(l1,l2);

	res = (res % MOD + MOD) % MOD;

	printf("%lld\n",res);

	fclose(stdin);

	fclose(stdout);

	return 0;

}