ARC Round#148

靠着 D 猜到结论好不容易上分了，第三次上黄（

赛后改题：All Accepted。

A

题意：给定 $n$ 个数，要你选择一个模数 $M$，问每个数 $\bmod M$ 过后不同的数最少都多少个，$M$ 不能选择 1。

容易发现当 $M = 2$ 的时候答案不超过 2。这是一个关键入口。

判断答案能不能为 1 是好判断的，差分数组的 $\gcd$ 不为 1 的话就存在。

否则答案一定为 2。

B

题意：给定一个长度为 $n$ 的只包含 dp 的字符串，你可以选择一个区间 $[l, r]$ 将该子串翻转。翻转的定义是 d 变 p，p 变 d，然后 std::reverse。问翻转后字典序最小是哪个串。$n\leq 5000$。

容易发现我们的翻转起始点就是第一个 p 的位置，我们将他变为 d，这样肯定比不变化该位置更优。另外我们把起始点设在该 p 前面的话，那么翻转区间的最后一定是一堆 p，否则不优。如果是一堆 p 的话，两端相当于没有交换，其实还是从 p 开始的。

这样可能的串就只有 $O(n)$ 个了，找到最小的即可，时间复杂度 $O(n ^ 2)$。

C

题意：给定一棵 $n$ 个点的无边权有根树，根为 1，每个点有一个正反面的硬币，翻转一个硬币会导致子树内的硬币都会翻转，代价为 1。$q$ 次询问，每次给定一个大小为 $m$ 的点集，求将集合内的硬币都翻转而不改变其他点状态的最小代价。$n, q, \sum m\leq 2\times 10 ^ 5$。

据说数据很水，最坏 $O(nq)$ 的直接过了（

容易发现一个点最多只会产生 1 的代价（注意这个点可能不在给定点集里）。

假设先不考虑上面的结论，我们直接翻转，假设集合只有 1 个点的话，我们需要对他本身和他的所有儿子都翻转一次，答案为 $1 + son(x)$。而多个点相较于 1 个点的差别在于如果一个集合内的点的父亲也在集合内的话，那么这个点原来应该翻转 2 次，现在不再需要翻转了，就可以减 2。

于是题目转化成了一个给定点集求父子关系对数。枚举儿子查父亲即可。时间复杂度 $O(n + \sum m)$ 或 $O(n + \sum m\log m)$。

D

题意：给定 $2n$ 个数，Alice 和 Bob 分别任取其中的一个数，如果最后 Alice 取的数的和和 Bob 的和在 $\bmod m$ 意义下相同的话，Bob 胜，否则 Alice 胜。问最优情况下谁会胜利。$n\leq 2\times 10 ^ 5$。

先不考虑模意义，如果是和相同怎么做。容易发现每个数出现的次数必须是偶数，这样 Bob 才能获胜，否则 Alice 获胜。考虑证明，由于 Alice 取的时候，至少有两个数没有配对，Alice 取走一个过后，剩下的就和 Bob 取配对游戏，最后 Bob 一定会取到另外一个没有配对的数。这样两人的和并不同，Alice 胜。

现在我们需要考虑增加了模意义有什么变化。如果每个数出现次数是偶数的话，仍然还是 Bob 胜，但剩下的情况不太对劲。我们先给出一个 Hack：

1 2	2 6 1 4 2 5

手玩一下，容易发现这个时候一定会是 Bob 胜利。

为什么呢？因为在 $\bmod m$ 意义下，$m$ 如果是偶数的话，并且 $\geq \dfrac m2$ 的数是偶数个的话，两个人最后拿到 $\geq \dfrac m2$ 的个数的奇偶性一定是相同的，而这就代表着只考虑 $\dfrac M2$ 的话两个人 $\bmod m$ 是相同的。这样我们就不能 $\bmod m$ 意义下了，而应该在$\bmod \dfrac m2$ 意义下做上面的结论了。

剩下的没有其他的情况需要特判了，简单的证一下。

$m$ 是奇数：容易发现这时 Alice 最后一次选择的时候一定剩 2 个不同的数，选择一个数后会产生一个差值 $d$，而反过来选择差值就是 $m - d$。$d$ 和 $m - d$ 不相同，那么不可能两个数都是满足加上后变成 0 的，于是此时 Alice 胜。
$\geq \dfrac m2$ 有奇数个：让所有 $\geq \dfrac m2$ 的数都减去 $\dfrac m2$，我们只需要让 Alice 和 Bob 在 $\bmod m$ 意义下差值 $< \dfrac m2$ 即可。这显然是容易办到的，而两个人选择的 $\geq \dfrac m2$ 的数的奇偶性不同，所以 Alice 一定胜利。

E

咕咕咕。

F

题意：提交答案题。给定一个计算器，有 26 个 unsigned long long 的存储功能，标号为 A 到 Z。满足的功能有 $a + b\to c$，$a\times b\to c$，$a\bmod 998244353\to c$。注意这里面的 $a, b$ 可以为给定常数。现在有两个数分别存储在 A 和 B，要求给定命令使得最后 C 存储的是 $a\times b\bmod 10 ^ 9 + 7$。

复述题解。

这个是完全不懂了，先给出一个 AT 的官方链接 Montgomery multiplication (Wikipedia)。

令 $P_1 = 998244353, P_2 = 10 ^ 9 + 7$。

直接使用这个算法，我们相当于是可以在 $\bmod 2 ^ {64}$ 和 $\bmod P_1$ 下做乘法运算，现在需要求 $\bmod P_2$ 下的乘法。

直接给出代码：

using ULL = unsigned long long;

const int P1 = 998244353, P2 = 1e9 + 7;
const int _MP = P1 - qpow(P2, P1 - 2, P1), M2 = (ULL) P1 * P1 % P2;

ULL reduce(ULL x)
{
	ULL ret = (x + (x % P1 * _MP % P1) * N) / P1;
	if (x >= P2) x -= P2;
	return x;
}

ULL mul(ULL a, ULL b)
{
	a = reduce(a * M2), b = reduce(b * M2);
	ULL c = a * b;
	return reduce(reduce(c));
}

_MP 记为 $P_m$，满足 $P_mP_2\equiv -1\pmod {P_1}$，M2 满足 $M_2 = P_1 ^ 2\bmod P_2$。

原理不清楚，目前所知就是 reduce(x) 会返回 $xP_1 ^ {-1}\bmod P_2$，反正是这样了呢。现在考虑如何使用这段代码。

难点主要有两个：一是如何实现 $x / P_1$，二是如何实现 if 语句。

实现 $x / P_1$

假设我们把 x + (x % P1 * _MP % P1) * P2 在 $\bmod P_1$ 意义下，我们容易发现这个 $\bmod P_1$ 余 0 的。那么相当于就是直接除，而直接除可以使用乘 $P_1$ 在 $2 ^ {64}$ 的逆元完成。

实现 `if` 语句

这个是难实现的，但是我们发现（？）执行该语句的次数很少，而且肯定不超过 $2N$。这样的话可以证明不超过 2 次执行 reduce 就可以代替该 if 语句了。

于是整个的就可以写作：

1
2
3

a = reduce(a * M2), b = reduce(b * M2);
c = reduce(reduce(c));
c *= M2, c = reduce(reduce(c));

改成给的语言即可。代码附调试功能。

#include <iostream>
#include <cstdio>

using ULL = unsigned long long;
using s128 = __int128_t;

const int Mod1 = 998244353, Mod2 = 1e9 + 7, _MP = 4915446, M2 = 320946142;
const ULL Mul = 996491785301655553ULL;
ULL a[26];

void ExGcd(s128 a, s128 b, s128 &x, s128 &y)
{
	if (!b) return x = 1, y = 0, void();
	ExGcd(b, a % b, y, x), y -= a / b * x;
}

void reduce(char t) {
	/*ULL ret = (t + (t % Mod1 * _MP % Mod1) * Mod2) / Mod1;
	// if (ret >= Mod2) ret -= Mod2;
	t = ret;*/
	std::cout << "rem Z " << t << '\n';
	a[25] = a[t - 'A'] % Mod1;
	std::cout << "mul Z Z " << _MP << '\n';
	a[25] = a[25] * _MP % Mod1;
	std::cout << "rem Z Z\n";
	std::cout << "mul Z Z " << Mod2 << '\n';
	a[25] = a[25] * Mod2;
	std::cout << "add Z Z " << t << '\n';
	a[25] += a[t - 'A'];
	std::cout << "mul " << t << " Z " << Mul << '\n';
	a[t - 'A'] = a[25] * Mul;
}

int main()
{
	std::cin >> a[0] >> a[1];
	std::cout << "40\nmul A A " << M2 << '\n' << "mul B B " << M2 << '\n';
	a[0] *= M2, a[1] *= M2;
	reduce('A'), reduce('B');
	std::cout << "mul C A B\n";
	a[2] = a[0] * a[1];
	reduce('C'), reduce('C');
	std::cout << "mul C C " << M2 << '\n';
	a[2] *= M2;
	reduce('C'), reduce('C');
	std::cout << a[2] << '\n';
	return 0;
}

A

B

C

D

E

F

实现 $x / P_1$

实现 if 语句

实现 `if` 语句