Minibuses on Venus (hard version)

· · 题解

一个数竞神仙的做法，很厉害，详细解释一下。

题意即求存在 i 使得 x_1+\cdots+x_n\equiv2x_i\pmod k 的序列数量，亦即 x_i\equiv\dfrac{x_1+\cdots+x_n}{2}\pmod k。对于一个序列，取其最小的符合条件的 i 作为代表。记 A_i 为满足 2x_i\equiv S\pmod k 且 \forall j<i,2x_j\not\equiv S\pmod k 的序列数量，则我们只需求 A_1+\cdots+A_n。

下面以 2\nmid k 为例介绍该做法。

对于 i<n 的 A_i，x_i 有 k 种取值；由于我们钦定 j<i 的 x_j 皆不满足条件，故 x_1 到 x_{i-1} 这些数各个都有 k-1 种取值；x_{i+1} 到 x_{n-1} 可任取，x_n 总有唯一的数使得整个序列符合条件。因此若 i<n，则 A_i=(k-1)^{i-1}k^{n-i}。

着重讨论 A_n。此时由于 x_n 被占位，故不同于前述 i<n 时的情形。此时我们须求 x_1+\cdots+x_{n-1}=x_n\pmod k 的序列数量，其中 x_i\neq x_n\;(i\neq n)。设 x_n=t，考察每一个 t\in[0,k)。

经典地，同余式左侧的生成函数为：

F(z)=\left(\sum_{0\leqslant i<k,i\neq t}z^{i}\right)^{n-1}

我们只须求同余 t 次项的系数。进一步转化：

\begin{aligned} A_{n,t}=\sum_{k\mid(d-t)}\left[z^d\right]\!F(z)=\sum_{k\mid d}\left[z^d\right]\!z^{k-t}F(z) \end{aligned}

设 \omega_n 为 n 次单位根，我们知道：

\sum_{k=0}^{n-1}\omega_n^{kl}=\begin{cases} n,&n\mid l\\0,&n\nmid l \end{cases}

故令 G(z)=z^{k-t}F(z)，将 k 次单位根代入 G(z)，算得：

\begin{aligned} A_{n,t}&=\frac{1}{k}\sum_{i}G\!\left(\omega^{i}\right)\\ &=\frac{1}{k}\sum_i\omega^{i(k-t)}\left(\sum_{j\neq t}\omega^{ij}\right)^{n-1}\\ &=\frac{1}{k}\sum_i\omega^{-it}(-\omega^{t})^{n-1}\\ &=\frac{(-1)^{n-1}}{k}\sum_i\omega^{it(n-2)} \end{aligned}

据此便可求出 A_n：

\begin{aligned} A_n&=\sum_{t}\frac{(-1)^{n-1}}{k}\sum_i\omega^{it(n-2)}\\ &=(-1)^{n-1}\frac{1}{k}\sum_{i=1}^{k-1}\sum_{t=0}^{k-1}\omega_k^{it(n-2)}\\ &=(-1)^{n-1}\sum_{i=1}^{k-1}\big[k\mid i(n-2)\big]\\ &=(-1)^{n-1}(\gcd(k,n-2)-1) \end{aligned}

从而最终答案为：

\begin{aligned} \sum_{i=1}^nA_{i}&=A_n+\sum_{i=1}^n(k-1)^{i-1}k^{n-i}\\ &=A_n+k^{n-1}\sum_{i=0}^{n-1}\left(\frac{k-1}{k}\right)^i\\ &=A_n+k^n-(k-1)^n\\ &=k^n-k^{n-1}+(-1)^{n-1}(\gcd(k,n-2)-1) \end{aligned} $$ F(z)=\left(\sum_{0\leqslant i<k}[i\neq t]\left[i \neq t{+}\tfrac{k}{2}\right]z^{i}\right)^{n-1} $$ 此后的步骤与 $2\mid k$ 相同。可得最终答案为： $$ \frac{k^n}{2}-2^{n-1}\left(\left(\frac{k}{2}-1\right)^n-(-1)^{n-1}\left(\gcd\left(\frac{k}{2},n-2\right)-1\right)\right) $$