+++ date = "2021-07-24T20:30:00+08:00" draft = false tags = [] title = "2021 牛客多校第 3 场" authors = ["xry111"] +++

F. 24dian

题意

输入 $n$ 和 $m$，输出所有从扑克牌堆抽 $n$ 张牌 ($13^n$ 种情况) 后， 获得的牌能且仅能通过中间过程有分数的四则运算得到数 $m$ 的情况。 $1 \leq n \leq 4$，$1 \leq m \leq 10^9$。

做法 (非标准)

对于 $n \leq 2$，显然没有这样的情况。

对于 $n = 3$，如果先用两张牌除出个分数， 那么必然要再做一次乘法才能得到整数 $m$。那么只要先乘再除就没有分数了， 所以也没有这样的情况。

对于 $n = 4$，暴力枚举 $\binom{13}{4}$ 种情况，然后暴力枚举 $4!$ 种顺序， 再暴力枚举 Catalan 数种加括号的方案，再暴力枚举 $4^3$ 种加运算符的方案， 结果本地一跑发现 $1$ 秒跑不完。大概试了一下发现 $m \geq 300$ 无解， 就直接打表过了。最后发现全场好像就两个队打表， 人家别人写的搜索交上去都随便过。

我们的表还被出题人讲题的时候不小心放到屏幕上了， 然后出题人一看心想“woc 这什么傻逼”，赶紧切走了。

I. Kuriyama Mirai and Exclusive Or

题意

给你一个数列 $\{a_i\}$，两种操作，一种对于 $i \in [l, r]$ 把 $a_i$ 都异或 $x$，另一种对于 $i \in [l, r]$ 把 $a_i$ 都异或 $(i - l + x)$。求所有操作结束后的数列。

做法 (非标准)

第一种操作就跟没有一样，放到校赛都能过 $114$ 人。

对于第二种操作，我们按位讨论。操作对于第 $i (0 \leq i)$ 位的影响是以 $2^{i+1}$ 为周期的，其中前半周期没影响，后半周期对这一位异或 $1$ (就是个方波)。如果 $i$ 较大，则操作相当于对 $n / 2^{i+1}$ 个区间做第一种操作，剩下就是 $i$ 较小的情况。

对于 $i$ 较小的情况，我们把操作拆成左操作和右操作，然后对操作按位置排序。 从左往右扫描序列，维护当前位置左边所有操作的总影响。这个影响一定是以 $2^{i+1}$ 为周期的，可以存到一个 $2^{i+1}$ 位的二进制数里面。 在计入新的操作时，这个操作的影响可以通过循环移 $x \bmod 2^{i+1}$ 位 (相当于方波的移相) 确定，然后异或到当前总影响上就行了。当位置向右移动时， 需要将总影响循环移 $1$ 位。因为 $2^{i+1}$ 会超过计算机的字长 $w$， 需要使用 bitset 存这个二进制数。

考虑两种情况的阈值 $t$，对于 $i > t$ 按第一种情况做，其他按第二种情况做。 时间代价大概可以写成

$$\sum_{i = t + 1}^{\log_2 \max a_i} \frac{nq}{2^{i+1}} + \sum_{i = 0}^{t} \frac{2^{i+1}(n+q)}{w} \approx \frac{nq}{2^{t+1}} + \frac{2^{t+2}(n+q)}{w}$$

经过一通操作会发现这个东西是 $\mathcal{O}(\sqrt{\frac{nq(n+q)}{w}})$ 的， 能过。然而现场把最优的 $t$ 算错了，本地随机数据都过不了， 赛后才想到可以胡乱试一些 $t$ 值的 qwq。

注意为了达到这个复杂度，不能每次都用 bitset<len> (len 是 $2^{t+1}$)， 不然根号里面应该会多出一个 $\log_2 \max a_i$。 但是 C++ template 的语义又要求尖括号里面的那个数必须在编译期确定， 所以这里通过 fuck<t> 调用 fuck<t-1> 这样的模板元编程 (TMP) 技巧实现对 $i \leq t$ 的情况的处理。为了毒瘤人展示这种写法， 把代码贴出来康康：

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

static int a[600000];

struct Q
{
	int tp, l, r, x;
};

static Q q[400000];
static int f[600000];

enum { t = 10 };

struct Q1
{
	int l, x;
	bool operator<(const Q1 &rhs) const
	{
		return l < rhs.l;
	}
};

static Q1 q1[800000];

template <int k>
void fuck(int m, int n)
{
	bitset<(1 << k)> stat = 0;
	bitset<(1 << k)> val = 0;

	int b = 1 << (k - 1);
	int period = b + b;
	int mask = period - 1;

	for (int i = b; i < period; i++)
		val[i] = 1;

	for (int i = 0, j = 0; i < n; i++) {
		for (; j < m && q1[j].l <= i; j++) {
			int x = q1[j].x & mask;
			stat = stat ^ (val >> x) ^ (val << (period - x));
		}
		if (stat[0])
			a[i] ^= b;
		int xx = stat[0];
		stat >>= 1;
		stat[period - 1] = xx;
	}

	fuck<k - 1>(m, n);
}

template<> void fuck<0>(int, int) {}

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	for (int i = 0; i < m; i++)
		scanf("%d%d%d%d", &q[i].tp, &q[i].l, &q[i].r, &q[i].x);
	for (int i = 0; i < m; i++)
		if (q[i].tp == 0) {
			f[q[i].l - 1] ^= q[i].x;
			f[q[i].r] ^= q[i].x;
		} else {
			for (int k = t + 1; k < 30; k++) {
				int b = 1 << k;
				int period = b + b;
				int mask = period - 1;
				int x = q[i].x & mask;
				int xx = max(x, b);
				int l = q[i].l + xx - x;
				int r = l + mask - xx;
				if (l <= q[i].r) {
					f[l - 1] ^= b;
					f[min(r, q[i].r)] ^= b;
				}
				for (l = r + b + 1; l <= q[i].r; l += period) {
					f[l - 1] ^= b;
					f[min(l + b - 1, q[i].r)] ^= b;
				}
			}
		}
	int acc = 0;
	for (int i = 0; i < n; i++)
		a[i] ^= (acc ^= f[i]);
	int mm = 0;
	for (int i = 0; i < m; i++)
		if (q[i].tp == 1) {
			q1[mm++] = {q[i].l - 1, q[i].x};
			q1[mm++] = {q[i].r, q[i].x + (q[i].r - q[i].l + 1)};
		}
	sort(q1, q1 + mm);
	fuck<t + 1>(mm, n);
	for (int i = 0; i < n; i++)
		printf("%d%c", a[i], " \n"[i + 1 == n]);
	return 0;
}

这个题主要教训一个是这种分类讨论题如果阈值定不下来可以直接试 (反正本来算得也不准，因为没考虑常数)， 另一个是不要混用闭区间和左闭右开区间，否则会很难受。