2022-04-13-HNOI2012 题解集合

蔬菜越来越多。

与非

$\mathcal{Link}$

link

$\mathcal{Sol}$

记录一个常见（？）技巧。
当题目给定一个位运算操作时，先从每个数位入手，只考虑四种情况。
再看这个位运算操作是否可以推广。

---

拿这道题举例。

$$ not (A) = A \ nand \ A \\ A \ or \ B = not(not(A) \ nand \ not(B)) \\ A \ and \ B = not(A \ nand \ B) \\ A \ xor \ B = not(not(A) \ and \ not(B) \ or \ (A \ and \ B)) $$

就是说，只要有 nand 操作，你就可以把所有的操作全部表示出来。

$\mathcal{Code}$

nand.cpp

#include <cstdio>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
const int MAXN = 1e7 + 5;

LL n, k;
LL l, r, a[MAXN], b[MAXN], num[MAXN], ans;

LL query(LL x) {
	LL res = 0;
	if (x >= ((1ll << k) - 1)) return 1ll << num[k - 1];
	for (int i = k - 1; i >= 0 && x >= 0; i--) {
		if ((x >> i) & 1) {
			if (b[i]) {
				res = (res + (1ll << num[i] - 1));
				x -= b[i];
				// printf("--%lld %lld %lld\n", res, 1ll << num[i] - 1, b[i]);
			} else {
				res = (res + (1ll << num[i]));
				break;
			}
		}
	}
	res += (x == 0);
	return res;
}

int main() {

	// freopen("nand.in", "r", stdin);
	// freopen("nand.out", "w", stdout);

	scanf("%lld %lld %lld %lld", &n, &k, &l, &r);
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);

	LL statment = 0;
	for (int i = k - 1; i >= 0; i--) if (!((statment >> i) & 1)) {
		LL tmp = (1ll << k) - 1;
		for (int j = 1; j <= n; j++) if ((a[j] >> i) & 1) {
			tmp &= a[j];
		} else tmp &= (~a[j]);
		b[i] = tmp;
		num[i] = 1;
		statment |= tmp;
	}
	for (int i = 1; i < k; i++) num[i] += num[i - 1];

	printf("%lld\n", query(r) - query(l - 1));

	return 0;
}

集合选数

$\mathcal{Sol}$

属于神仙构造了。
考试时想到了要把建树，但是没把树拍扁。

首先一个 树形DP 的感觉不难得到。
然后构造如下的矩阵。

$$ 1 \ 2 \ 4 \ 8 \ 16 \ 32 \ 64 \dots \\ 3 \ 6 \ 12 \ 24 \ 48 \ 96 \ 192 \ 384 \dots \\ 9 \ 18 \ 36 \ 72 \ 144 \ 288 \ 576 \ 1152 \dots \\ $$

形式化一点就是

$a_{i, j}=\left\{\begin{matrix} a_{i - 1, j} \times 3, j = 1 \\ a_{i, j - 1} \times 2, j \not= 1 \end{matrix}\right.$

矩阵很小，可以状压。

$\mathcal{Code}$

set.cpp

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
const int MAXN = 15;
const int MAXM = 20;
const int Mod = 1e9 + 1;

int n, r, c[MAXM], mat[MAXN][MAXM];
bool vis[(1 << MAXM) + 5], used[(1 << MAXM) + 5];
LL dp[MAXN][(1 << MAXM) + 5], ans;

LL cal(int s) {

	mat[1][1] = s;
	used[s] = 1;
	for (int i = 2; i <= 12; i++) {
		mat[i][1] = mat[i - 1][1] * 3;
		if (mat[i][1] > n) { r = i - 1; break; }
		used[mat[i][1]] = 1;
	}
	for (int i = 1; i <= r; i++) {
		for (int j = 2; j <= 18; j++) {
			mat[i][j] = mat[i][j - 1] * 2;
			if (mat[i][j] > n) { c[i] = j - 1; break; }
			used[mat[i][j]] = 1;
		}
	}
	
	for (int i = 0; i < (1 << c[1]); i++) dp[1][i] = vis[i];
	for (int i = 2; i <= r; i++) {
		for (int j = 0; j < (1 << c[i]); j++) if (vis[j]) {
			dp[i][j] = 0;
			for (int k = 0; k < (1 << c[i - 1]); k++) if (vis[k] && (k & j) == 0) {
				dp[i][j] = (dp[i - 1][k] + dp[i][j]) % Mod;
			}
		}
	}

	LL sum = 0;
	for (int i = 0; i < (1 << c[r]); i++) sum = (sum + dp[r][i]) % Mod;
	return sum;

}

int main() {

	// freopen("set.in", "r", stdin);
	// freopen("set.out", "w", stdout);

	scanf("%d", &n);

	for (int i = 0; i < (1 << MAXM - 2); i++) if (!((i << 1) & i)) vis[i] = 1;

	ans = 1;
	for (int i = 1; i <= n; i++) if (!used[i]) ans = (ans * cal(i)) % Mod;
	printf("%lld\n", ans);

	return 0;
}