Minibuses on Venus (hard version)

· · 题解

题目链接

CF1808E3 Minibuses on Venus (hard version)

题解

看到 n \le 10 ^ {18}, k \le 2000 的数据范围，我们容易想到数位 \text{dp} 和矩阵乘法没有前途，所以可以考虑组合数学。

我们首先枚举最后的总和 s，并且找到对应的 x，使得 2x \equiv s \pmod k，明显地，如果我们保证序列的总和为 s，并且序列中出现过 x，那么这个序列就是合法的。

情况 1：k \equiv 1 \pmod 2

这种情况下，对于每个 s \in [0, k)，只有一个 x 与之对应。

考虑设 f_i 表示至少填 i 个 x 的方案数，g_i 表示恰好填 i 个 x 的方案数。

对于 f_i 的计算，我们考虑先把 i 个 x 给填好，方案数为 \dbinom{n}{i}，然后剩下的 n - i 个位置中，我们考虑前 n - i - 1 个可以随意填，方案数为 k ^ {n - i - 1}，为了使得整个序列的总和为 s，所以最后那个数是唯一的。

所以 \forall i \in [1, n), f_i = \dbinom{n}{i} \times k ^ {n - i - 1}，而 f_n 则需特判是否有 xn \equiv s \pmod k。

然后我们考虑如何通过 f 来计算 g。

对于一个恰好填 m 个 x 的方案，在这 m 个 x 中，可以任选 i 个 x 作为 f 中最先填的 i 个数，所以 g_m 中的一个方案在 f_i 中会被重复计算 \dbinom{m}{i} 次。

所以有：

f_i = \sum_{j = i} ^ n \dbinom{j}{i} \times g_j

根据二项式反演：

g_i = \sum_{j = i} ^ n (-1) ^ {j - i} \times \dbinom{j}{i} \times f_j

这样我们就得到了一个 \Theta(n ^ 2 k) 的做法。

然后直接考虑推式子，最终答案为：

\sum_{i = 1} ^ n \sum_{j = i} ^ n (-1) ^ {j - i} \times \dbinom{j}{i} \times f_j

由于 f_n 的计算方法不太一样，所以将其拎出，单独处理，我们首先计算：

\sum_{i = 1} ^ {n - 1} \sum_{j = i} ^ {n - 1} (-1) ^ {j - i} \times \dbinom{j}{i} \times f_j = \sum_{i = 1} ^ {n - 1} \sum_{j = i} ^ {n - 1} (-1) ^ {j - i} \times \dbinom{j}{i} \times \dbinom{n}{j} \times k ^ {n - j - 1} = \sum_{j = 1} ^ {n - 1} \dbinom{n}{j} \times k ^ {n - j - 1} \times \sum_{i = 1} ^ {j} (-1) ^ {j - i} \times \dbinom{j}{i}

而后面的求和式可以用二项式定理：

= \sum_{j = 1} ^ {n - 1} \dbinom{n}{j} \times k ^ {n - j - 1} \times (-1) ^ {j + 1}

然后再次使用二项式定理：

= -\dfrac1k \times \sum_{j = 1} ^ {n - 1} \dbinom{n}{j} \times k ^ {n - j} \times (-1) ^ j = -\dfrac1k \times \left[ (k - 1) ^ n - k ^ n - (-1) ^ n \right]

接着考虑 f_n 的贡献：

\sum_{i = 1} ^ n \dbinom{n}{i} \times (-1) ^ {n - i} \times f_n = f_n \times \sum_{i = 1} ^ n \dbinom{n}{i} \times (-1) ^ {n - i}

使用二项式定理可得：

= f_n \times (-1) ^ {n + 1}

至此，我们得到了一个 \Theta(k \log n) 的做法，预处理 (k - 1) ^ n 和 k ^ n 可以做到 \Theta(k + \log n)。

情况 2：k \equiv 0 \pmod 2

和情况 1 相似，只是对于每个偶数 s，有两个 x_1, x_2 与之对应。

我们仍然考虑设 f_i 表示至少选 i 个 x_1 或 x_2，设 g_i 表示恰好选 i 个。

类似地，\forall i \in [1, n), f_i = \dbinom{n}{i} \times k ^ {n - 1 - i} \times 2 ^ {i}，其余推式子的部分与情况 1 类似。

然后考虑 f_n 如何计算，首先容易想到一个 \Theta(n) 做法：

枚举 i 表示选择 i 个 x_1，n - i 个 x_2，然后判断是否合法，若合法，则将 f_n 加上 \dbinom{n}{i}。

然后我们考虑合法的条件：

i \times x _1 + (n - i) \times x_2 \equiv s \pmod k i \times (x_1 - x_2) \equiv s - n \times x_2 \pmod k

而 s - n \times x_2 为一个常量，这里记作 c。

由于 x_1 = \dfrac{s}{2}, x_2 = \dfrac{s}{2} + \dfrac{k}{2}，所以 x_1 - x_2 \equiv \dfrac{k}{2} \pmod k。

也就是说：

\dfrac{k}{2} \times i \equiv c \pmod k

当 i 为偶数时，左式恒为 0；当 i 为奇数时，左式恒为 \dfrac{k}{2}。

所以可得：

f_n = \begin{cases} \sum_{i \equiv 0 \pmod 2} \binom{n}{i} \quad c = 0 \\ \sum_{i \equiv 1 \pmod 2} \binom{n}{i} \quad c = \frac{k}{2} \\ 0 \quad \text{otherwise} \end{cases}

而对于形如：

\sum_{i \equiv b \pmod 2} \dbinom{n}{i}

这样的式子，可以考虑将其放到杨辉三角上的第 n 行，然后将所有组合数都拆成 n - 1 行的组合数，可以发现无论 b = 0 / 1，答案都是第 n - 1 行组合数的和，等于 2 ^ {n - 1}。

所以问题就解决了，时间复杂度 \Theta(k + \log n)。

我这里的实现复杂度是 \Theta(k \log n) 的。

代码链接

https://codeforces.com/contest/1808/submission/200386783