摘记: 为了处理 \sum_i\binom{n}{ik} 类的, 询问下标为给定常数k倍数的求和问题。

公式

\frac 1 k \sum_{i=0}^{k-1} \omega_k^{i\cdot n} = [k | n]

Proof

分情况考虑

  • \text{ case 1: } n\equiv 0 \bmod k

    相当于k个1相加

  • \text{case 2: otherwise} 等比数列求和

T1: Bzoj 3328

求:

\sum_{i≥0}\binom{n}{ik} \text{fib}_{ik}

  • 其中, \text{fib}_i 为斐波那契数列第i

sol

考虑没有k限制咋做

\begin{aligned} &\sum_{i≥0}\binom{n}{i} \text{fib}_{i} \\ &= (I+A) ^ n \end{aligned}

其中I为单位矩阵, A为斐波那契转移矩阵

答案就是[a_{(0, 0)}] (I+A)^n

这么做的正确性在于单位矩阵是满足交换律的, 故可以这么做…

那么我们希望消去非k倍数的项

直接单位根反演:

ans = \frac{1}{k} \sum _i ^k [a_{(0,0)}] (I+\omega^i A)^n

T1

  • [0,n-1]中选出k个不同的数使得它们的和是n的倍数的方案数

  • k\le 1000, n\le 10^9

sol

引入二元生成函数 来帮助我们解题

f(x,y)=\prod_{i=0}^{n-1}(1+x^iy)

答案就是 y^k 项中, 指数是n倍数x项的系数之和

看见n倍数, 联想到单位根反演

暴力做法: 考虑带入所有的\omega_n^i, 但是带不得

考虑这里的\omega_n ^i 可以转换成d(d | n) 次本原单位根.

f(\omega, y) = \Big(\prod _{i=0} ^{d – 1} (1+\omega^iy) \Big) ^ {\frac{n}{d}}

而且很快发现, \omega_d^i\omega_d^j带来的结果是一样的

故, 这里仅考虑\omega_d

引理:

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

证明的话, 考虑代数基本定理好了

那么进一步的, 有:

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

然后考虑\prod _{i=0} ^{d – 1} (1+\omega^iy) = (-1)^d(y^d-1)

那么[x^n]\Big( (-1)^d(y^d-1) \Big) ^ {\frac{n}{d}}就很好计算了.

到此, 就做完了, 分析一下复杂度:

枚举n所有的因数d, 计算贡献并乘上\phi(d) 即可

大概是O(\sqrt n)的…吧…