C++(g++ 7.5.0) 解法, 执行用时: 293ms, 内存消耗: 808K, 提交时间: 2023-05-09 23:14:17

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

int K;
int len1, bit1l[32], bit1r[32], len2, bit2l[32], bit2r[32];
int A, B, C, D, fact[32];
int f[32][2][2][2][2][2][32][2];
// pos a b c d le sum-block last

int dfs(int pos, bool la, bool lb, bool lc, bool ld, bool le, int t, bool last) {
	if (pos < 0)	return fact[t];
	if (f[pos][la][lb][lc][ld][le][t][last] != -1)	return	f[pos][la][lb][lc][ld][le][t][last];
	int a = la ? (A >> pos & 1) : 0;
	int b = lb ? (B >> pos & 1) : 0;
	int c = lc ? (C >> pos & 1) : 1;
	int d = ld ? (D >> pos & 1): 1;
	
	long long res = 0;
	for (int x = a; x <= c; x ++)
		for (int y = b; y <= d; y ++) {
			int u = x ^ y, v = K >> pos & 1;
			int w = x | y;
			if (u < v) {
				res += dfs(pos - 1, la && x == a, lb && y == b, lc && x == c, ld && y == d, true, t + (w == 1 and last == 1), w);
			} else if (u == v) {
				res += dfs(pos - 1, la && x == a, lb && y == b, lc && x == c, ld && y == d, le, t + (w == 1 and last == 1), w);
			} else {  // u > v
				if (le == false)	continue;
				res += dfs(pos - 1, la && x == a, lb && y == b, lc && x == c, ld && y == d, le, t + (w == 1 and last == 1), w);
			}
			res %= MOD;
		}
	return f[pos][la][lb][lc][ld][le][t][last] = res;
}

int main() {
	int T; cin >> T;
	fact[0] = 1;
	for (int i = 1; i < 32; i ++)	fact[i] = 1ll * i * fact[i - 1] % MOD;
	while (T --) {
		memset(f, -1, sizeof f);
		cin >> A >> C >> B >> D >> K;
		
		cout << dfs(30, 1, 1, 1, 1, 0, 0, 0) << '\n';
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 458ms, 内存消耗: 640K, 提交时间: 2022-11-09 19:37:19

#include<bits/stdc++.h>
using namespace std;
const int N=39,mod=998244353;
int T,l1,r1,l2,r2,k,ans;
int fac[N],f[N][N][2][2][2][2];
int dfs(int x,int y,int ltx,int lty,int ltk,int b,int cnt,int pre)
{
	if(b==-1) return fac[cnt];
	int &res=f[b][cnt][pre][ltx][lty][ltk];
	if(res) return res;
	int tx=(ltx?(x>>b&1):1),ty=(lty?(y>>b&1):1);
	for(int i=0,t;i<=tx;i++)
		for(int j=0;j<=ty;j++)
		{
			if(ltk&&(i^j)>(k>>b&1)) continue;
			if(pre&&(i|j)) t=1;
			else t=0;
			(res+=dfs(x,y,ltx&(i==tx),lty&(j==ty),ltk&((i^j)==(k>>b&1)),b-1,cnt+t,i|j))%=mod;
		}
	return res;
}
void solve()
{
	cin>>l1>>r1>>l2>>r2>>k;
	ans=0;
	memset(f,0,sizeof(f));
	ans+=dfs(r1,r2,1,1,1,30,0,0); ans%=mod;
	memset(f,0,sizeof(f));
	ans-=dfs(l1-1,r2,1,1,1,30,0,0); (ans+=mod)%=mod;
	memset(f,0,sizeof(f));
	ans-=dfs(r1,l2-1,1,1,1,30,0,0); (ans+=mod)%=mod;
	memset(f,0,sizeof(f));
	ans+=dfs(l1-1,l2-1,1,1,1,30,0,0); ans%=mod;
	cout<<ans<<"\n";
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	fac[0]=1;
	for(int i=1;i<=33;i++)
		fac[i]=1ll*fac[i-1]*i%mod;
	cin>>T;
	while(T--) solve();
	return 0;
}