526互联

AtCoder Regular Contest 145

发布时间 2023-06-04 19:16:19作者: Scintilla06

A

答案为 Yes 当且仅当 $s[1] \ne $ A 或 $s[n] \ne $ B。

注意判 \(n = 2\)。

B

Alice 可胜利当且仅当 \(n \ge a \wedge n \bmod a < b\)。

C

显然我们应该凑 \((2i - 1, 2i)\)。

那么我们用一个括号序列描述 \(2i - 1\) 和 \(2i\)，不难发现答案为

\[\frac{\binom{2n}{n}}{n + 1} \cdot n! \cdot 2^n \]

D

想到一半才想起来之前见过。

考虑三进制，发现我们把所有三进制下只有 \(0\) 和 \(1\) 的数拿出来即可，数量足够。

随便取 \(n - 2\) 个，剩下两个合理选取可以使得 \(n \mid m - s\)，其中 \(s\) 表示选出的数的和，然后平移即可。

E

注意到操作是可逆的，即我们可以每次令 \(b_i \leftarrow \oplus_{j = 1} ^ i b_j \ (1 \le i \le k)\)，目标是把 \(b\) 变为 \(a\)。

考虑从后往前构造。如果我们能在 \(\mathcal{O}(\omega) + \mathcal{O}(1)\) 的操作次数内把 \(b_n\) 变为为 \(a_n\)，我们就能解决原问题了，其中 \(\omega = 60\) 表示值域。

注意到要使 \(b_n\) 变化肯定最后要操作一次 \(n\)，于是我们需要使得 \(b\) 序列的异或和为 \(a_n\)。

我们考虑按位操作。设 \(p_d\) 表示从前往后 \(2^d\) 这一位为 \(1\) 的第一个位置。若操作 \(p_d + 1\)，则只有 \(b_{p_d + 1}\) 的 \(2^d\) 这一位会发生变化，即异或和的 \(2^d\) 这一位翻转。我们按照 \(p_d\) 从大往小的顺序操作，每次若当前异或和与 \(a_n\) 的 \(2^d\) 这一位不同则操作 \(p_d + 1\)。

看起来很对且必然有解，但我们忽略了一种情况：\(p\) 中可能存在相等的位置。

事实上稍微想一下就知道肯定不是必然有解：若 \(a_n \oplus b_n\) 不在 \(b_1, b_2, \cdots, b_{n - 1}\) 的线性基的张成中，则无解。

同时我们注意到，只要记录每个数是由线性基中的哪些数表出的，并以其代替 \(b\) 操作，就不会存在 \(p\) 相等的情况了。

时间复杂度 \(\mathcal{O}(n^2 \omega)\)。

F

首先令 \(a_i \leftarrow a_i + i - 1\)，则值域变为 \([0, n + m)\)，我们需要求

\[[x^j y^n] \prod_{i = 0} ^ {n + m - 1} (1 + x^i y) \]

其中 \(x\) 这一维是模 \(p\) 意义下的循环卷积。

首先我们令 \(n + m = kp + b\)，上式可变为

\[[x^j y^n] \prod_{i = 0} ^ {p - 1} (1 + x^i y) ^ k \prod_{i = 1} ^ b (1 + x^{n + m - i} y) \]

后面的边角料可以最后暴力背包求出，我们关注如何求出

\[f(x) = [y^n] \prod_{i = 0} ^ {p - 1} (1 + x^i y) ^ k \]

由循环卷积可以想到单位根。我们考虑求

\[g_j = [y^n] \prod_{i = 0} ^ {p - 1} (1 + \omega_p^{ij} y) ^ k \]

令 \(d = \gcd(j, p), q = \frac{p}{d}\)，可以得到

\[g_j = [y^n] \prod_{i = 0} ^ {q - 1} (1 + \omega_q^i y) ^ {dk} \]

因为 \(-\omega_q^i\) 是 \(1 - (-x)^q = 0\) 的 \(n\) 个根，所以

\[\prod_{i = 0} ^ {n - 1} (1 + \omega_n^i x) = 1 - (-x) ^ n \]

代入上式，可以得到

\[g_j = [y^n] (1 - (-x) ^ q) ^ {dk} \]

可以 \(\mathcal{O}(1)\) 求出。

考虑如何由 \(g\) 还原出 \(f\) 的系数。这就是一个 idft 的过程，我们有

\[f_i = \frac1p \sum_{j = 0} ^ {p - 1} g_j \omega_p^{-ij} \]

但是因为没有保证 \(p\) 是质数，我们不能直接进行复数操作。我们必须要把单位根消去，注意到 \(\gcd(j, p)\) 相同的 \(j\) 的 \(g_j\) 也相同，不难想到单位根反演：

\[ \begin{aligned} f_i & = \frac1p \sum_{j = 0} ^ {p - 1} g_j \omega_p^{-ij} \\ & = \frac1p \sum_{d \mid p} g_d \sum_{j = 0} ^ {p - 1} [\gcd(j, p) = d] \omega_p^{-ij} \\ & = \frac1p \sum_{d \mid p} g_d \sum_{j = 0} ^ {\frac{p}{d} - 1} \omega_p^{-idj} \sum_{t \mid \gcd(j, p)} \mu(t) \\ & = \frac1p \sum_{d \mid p} g_d \sum_{t \mid \frac{p}{d}} \mu(t) \sum_{j = 0} ^ {\frac{p}{dt} - 1} \omega_p^{-idtj} \\ & = \frac1p \sum_{d \mid p} g_d \sum_{t \mid \frac{p}{d}} \mu(t) \cdot [p \mid idt] \frac{p}{dt} \\ \end{aligned} \]

因为我们要对 \(n, n - 1, \cdots, n - p + 1\) 求出对应的 \(f\)，而后面的系数可以预处理，所以最终的时间复杂度是 \(\mathcal{O}(n + m + p^3)\)。

感受一下：循环卷积、单位根、单位根反演、莫反这几个东西之间是有连边的，以后看到这种还是先往这些方面想。