CF1808E3 题解

· · 题解

仍然考虑反面，即 $2a_i\not\equiv S\pmod k$。 先枚举 $S$，根据 $k$ 的奇偶性分类讨论： ① $k\equiv 1 \pmod 2$。 此时，不满足上述那个同余方程的数只有一个并且可以解出来，记为 $t$。显然可以容斥了。设 $f(i)$ 表示**钦定** $i$ 个位置的值为 $t$ 的方案数，$g(i)$ 表示**恰好** $i$ 个位置的值为 $t$ 的方案数。则 $f(i)=\sum\limits_{j=i}^nC_j^ig(j)$。我们要求 $g(0)$。 直接二项式反演得到 $g(i)=\sum\limits_{j=i}^n(-1)^{j-i}C_j^if(j)$。带入 $i=0$ 即得 $g(0)=\sum\limits_{i=0}^n(-1)^if(i)$。 再考虑直接计算 $f(i)$。当 $i=n$ 时 $f(i)=[nt\equiv S \pmod k]$，否则容易发现，剩余的 $n-i$ 个位置中的 $n-i-1$ 个位置可以随便选，而由于和一定因此最后一个位置可以自动确定。因此，$f(i)=C_n^ik^{n-1-i}$。 由于 $i=n$ 的情况略有不同，因此将其分离出来。带入： $g(0)=\sum\limits_{i=0}^{n-1}(-1)^iC_n^ik^{n-1-i}+(-1)^nf(n)$。 左边那个式子是个类似二项式定理的形式。将其分离一下略作调整即可化简为如下形式： $g(0)=\frac{(k-1)^n-(-1)^n}{k}+(-1)^nf(n)$。 注意到这个是建立在枚举 $S$ 的基础上的，所以将 $f(n)$ 写为 $f_{S}(n)$。将其对 $0\le S\le k-1$ 累加求和即可得到这部分的答案为 $(k-1)^n-(-1)^n+(-1)^n\sum\limits_{i=0}^{k-1}f_i(n)$。再利用 $t$ 的定义即可得到 $f_i(n)=[(n-2)i\equiv 0 \pmod k]$。这样的 $i$ 显然有 $\gcd(n-2,k)$ 个。 带入，并注意这是反面情况，即可得到这部分的答案为 $k^n-(k-1)^n+(-1)^n-(-1)^n\gcd(n-2,k)$。 ② $k\equiv 0\pmod 2

此时发现，当 S 为奇数时显然无解。考虑统计 S 为偶数且不包含满足 2a_i\equiv 0\pmod k 的 a_i 的方案。

和上一种情况不同的是，此时不满足条件的数有两个，记为 t_1,t_2。且可以解出这两个值，分别为 \frac{S}{2},\frac{S+k}{2}。

仍然容斥。设 f(i) 表示钦定 i 个值为 t_1 或 t_2 的方案数。g(i) 表示恰好 i 个值为 t_1 或 t_2。所求即为 g(0)。

显然 f(i)=\sum\limits_{j=i}^nC_j^ig(j)。二项式反演得到 g(i)=\sum\limits_{j=i}^nC_j^i(-1)^{j-i}f(j)。带入得到 g(0)=\sum\limits_{i=0}^n(-1)^if(i)。

考虑计算 f(i)。当 i\ne n 时，可得 f(i)=C_n^i2^ik^{n-1-i}。否则记为 f_S(n)，稍后处理。

类似于上面的情况，对偶数 S 累加求和即得

\frac{(k-2)^n-(-2)^n}{2}+(-1)^n\sum\limits_{S=2t,0\le 2t<k}f_S(n)

考虑计算 f_S(n)。枚举其中有 j 个 t_1，n-j 个 t_2。则 f_S(n)=\sum\limits_{j=0}^nC_n^j[jt_1+(n-j)t_2\equiv0\pmod k]

代入 t_1,t_2 表达式，化简为：

f_S(n)=\sum\limits_{j=0}^nC_n^j[\frac{k}{2}j\equiv \frac{S+k}{2}n-S\pmod k]

注意到，\frac{k}{2}j 模 k 的值只可能为 0 或 \frac{k}{2}，而右边是定值。发现无论是哪种情况，都是组合数上指标的交换求和，其值均为 2^{n-1}。

而 \frac{S+k}{2}n-S\equiv 0\pmod \frac{k}{2}。因此有 \frac{S}{2}(n-2)\equiv 0\pmod \frac{k}{2}。这种式子再熟悉不过了，满足条件的 S 有 \gcd(n-2,\frac{k}{2}) 个。

综上，我们得到：\sum\limits_{S=2t,0\le 2t<k}f_S(n)=2^{n-1}\gcd(n-2,\frac{k}{2})。

同样注意这是反面情况。整理可得这部分的答案为

\frac{k^n-(k-2)^n+(-2)^n}{2}-(-1)^n2^{n-1}\gcd(n-2,\frac{k}{2})

时间复杂度为 O(\log n+\log k)。注意 2 关于模数的逆元有可能不存在，需要通过微操避免除法。（具体的，就是把一个 k 拆开除以 2）。代码。