[SDOI2016]储能表

题意

link
给出 \(T, n, m, k, p, (n, m, k \leq 10^{18}, p \leq 10^9)\), 有 \(T\) 组询问。
求 $$\sum_{i = 0}^{n - 1}\sum_{j = 0}^{m - 1} \max((i \oplus j) - k, 0)$$

数位dp

状态

实际上能求出所有 \(i \oplus j > k\) 的和 \(f\)，和个数 \(g\)，那么答案就是 \(f - g \times k\)。

由于是异或，可以分开考虑二进制下每一位。

考虑求出 \(g\), 设 \(g(n, 1/0, 1/0, 1/0)\) 表示现在是第 \(n\) 位 (低到高),是否到 \(n\) 的上界，是否到 \(m\) 的上界，是否到 \(k\) 的下界的个数。

\(f\) 同理，只不过记得是和。

初始和最终状态

这里我是从高位到低位递归，对于最低位 \(g_{0, x, y, z}\)，由于要满足 \(< n, < m, > k\) 的限制，

只有 \(g(0, 0, 0, 0) = 1\)。

最后要求的是 \(g(64, 1, 1, 1)\)。

转移

到了上界就有 \(n, m\) 在这一位的限制，否则就没有限制, \(k\) 同理。

枚举两个数在这一位的取值，就能转移了。

转移就懒得写了太多了，看代码。

对于 \(f(i, x, y, z)\), 求出 \(g\) 转移到这一位的方案数 乘上位权即可。

分析

状态很少 \(O(62 * 2 * 2 * 2)\), 转移也是 \(O(1)\) 级别的。

用一下记忆化搜索就很快了。

时间复杂度大概是 \(O(T \log n)\)。

代码

记得取模，求答案时对k也要。

#include

using namespace std;

using ll = long long;
const int MAXN = 65;
const int INF = 0x7fffffff;
//const int mod = 1000000007;
int mod; 
const double eps = 1e-9; 

template 
void Read(T &x) {
	x = 0; T f = 1; char a = getchar();
	for(; a < '0' || '9' < a; a = getchar()) if (a == '-') f = -f;
	for(; '0' <= a && a <= '9'; a = getchar()) x = (x * 10) + (a ^ 48);
	x *= f;
}

inline int add(const int &a, const int &b) { 
	static int c;
	c = a + b;
	if (c >= mod) c -= mod;
	if (c < 0) c += mod;
	return c;   
} 
inline int mul(const int &a, const int &b) {
	return 1ll * a * b % mod; 
}
int qpow(int a, int b) {
	int sum(1);
	while(b) {
		if (b & 1) sum = mul(sum, a);
		a = mul(a, a);
		b >>= 1;
	}
	return sum; 
}

ll n, m, k;
int f[MAXN][2][2][2]; 
int F(int N, int a, int b, int c) {
	if (N == -1) return !a && !b && !c; 
	int nn = (n >> N) & 1, mm = (m >> N) & 1, kk = (k >> N) & 1, sum = 0;
	
	if (~f[N][a][b][c]) return f[N][a][b][c]; 
	for (int x = 0; x <= 1; x ++) 
		for (int y = 0; y <= 1; y ++) {
			int z = x ^ y;
			if ((a && x > nn) || (b && y > mm) || (c && (z < kk)))
				continue; 
			int A = a & (x == nn), B = b & (y == mm), C = c & (z == kk);
			sum = add(sum, F(N - 1, A, B, C));  
		}
	return f[N][a][b][c] = sum; 
}

int g[MAXN][2][2][2]; 
int G(int N, int a, int b, int c) {	
	if (N == -1) return 0; 
	int nn = (n >> N) & 1, mm = (m >> N) & 1, kk = (k >> N) & 1, sum = 0;
	if (~g[N][a][b][c]) return g[N][a][b][c]; 
	for (int x = 0; x <= 1; x ++) 
		for (int y = 0; y <= 1; y ++) {
			int z = x ^ y;
			if ((a && x > nn) || (b && y > mm) || (c && (z < kk)))
				continue; 
			int A = a & (x == nn), B = b & (y == mm), C = c & (z == kk);
			sum = add(sum, G(N - 1, A, B, C));
			sum = add(sum, mul(F(N - 1, A, B, C), (z ? qpow(2, N) : 0)));  
		}
	return g[N][a][b][c] = sum; 
}
int main() {
	int T;
	cin >> T;
	while(T --) {
		cin >> n >> m >> k >> mod;
		memset(f, -1, sizeof(f));
		memset(g, -1, sizeof(g));
		cout << add(G(62, 1, 1, 1), -mul(F(62, 1, 1, 1), k % mod)) << endl;
	}
	return 0;
}