Asusetic
0%

小猪佩奇学数学

发表于 分类于 ， Valine：
本文字数： 1.2k 阅读时长 ≈ 1 分钟

单位根反演

虽然说纯数学题不好，但是划着舒服

∑(ni)pi⌊ik⌋\large\sum\binom{n}{i}p^i\lfloor\dfrac{i}{k}\rfloor

因为我们事先知道了这是单位根反演题所以拆成能搞的形式

考虑到 ⌊ik⌋=∑j≤i[k∣j]−1\lfloor\dfrac{i}{k}\rfloor=\sum\limits_{j\le i}[k|j]-1

又 [k∣j]=1k∑d≤k−1ωkdj[k|j]=\dfrac{1}{k}\sum\limits_{d \le k-1}\omega_k^{dj}

带入 ⌊ik⌋=∑j1k∑dωkdj−1\lfloor\dfrac{i}{k}\rfloor=\sum\limits_{j}\dfrac{1}{k}\sum\limits_{d}\omega^{dj}_k-1

然后大力推式子

1k∑i(ni)pi∑j∑dωkdj\large\dfrac{1}{k}\sum\limits_{i}\binom{n}{i}p^i\sum\limits_{j}\sum\limits_{d}\omega^{dj}_k

=1k∑d∑i(ni)piωkd(i+1)−1ωkd−1\large = \dfrac{1}{k}\sum\limits_d\sum\limits_i\binom{n}{i}p^i\dfrac{\omega_k^{d(i+1)-1}}{\omega^d_k-1}

=1k∑d∑i(ni)(pωkd)k−∑i(ni)piωkd−1\large =\dfrac{1}{k}\sum\limits_d\dfrac{\sum\limits_i\binom{n}{i}(p\omega^d_k)^k-\sum\limits_i\binom{n}{i}p^i}{\omega^d_k-1}

1k∑dωkd(pωkd+1)n−(p+1)nωkd−1\large\dfrac{1}{k}\sum\limits_d\dfrac{\omega_k^d(p\omega_k^d+1)^n-(p+1)^n}{\omega_k^d-1}

当然最后有一个 −(p+1)n-(p+1)^n

显然 ωk\omega_k 在  mod p\bmod p 意义下就是 gp−1kg^{\frac{p-1}{k}}

还得特判 $ d=0 $

Asusetic eru quionours