「单位根反演」学习笔记

\(\mathcal{Preface}\)

单位根反演,顾名思义就是用单位根变换一类式子的形式。有关单位根的基本概念可见我的这篇博客

\(\mathcal{Formula}\)

单位根反演的公式很简单:

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

\(\mathcal{Proof}\)

分类讨论:

  1. \(k|n\). 那么 \((\forall i)(\omega_k^{ni}=1)\),所以右侧为 \(\frac{1}k\sum_{i=0}^{k-1}1=1\)。
  2. \(k\not=n\). 等比数列求和,右侧为 \(\frac{1}k\cdot\frac{1-\omega_k^{kn}}{1-\omega_k^n}\),其中 \(\omega_k^{kn}=1\),故分子为 \(0\),分母不为 \(0\),式子的值为 \(0\)。

    综上,得证。

\(\mathcal{Inference}\)

实际问题中,我们往往需要求出对于某个多项式(多为生成函数)\(f\) 的特定倍数次数的系数和。即求:

[\sum_{i=0}^{\lfloor \frac{n}k\rfloor}[x^{ik}]f(x) ]

运用单位根反演的基本公式变形:

[\begin{aligned} \sum{i=0}^{\lfloor\frac{n}k\rfloor}[x^{ik}]f(x)&=\sum{i=0}^n[k|i][x^i]f(x)\ &=\sum{i=0}^n[x^i]f(x)\cdot\frac{1}k\sum{j=0}^{k-1}\omegak^{ij}\ &=\frac{1}k\sum{j=0}^{k-1}\sum_{i=0}^n[x^i]f(x)(\omegak^j)^i\ &=\frac{1}k\sum{j=0}^{k-1}f(\omega_k^j) \end{aligned} ]

只要能快速求出 \(f\) 在所有 \(k\) 次单位根处的点值,就能 \(\mathcal O(k)\) 得出原式的值啦。

更方便的形式,若我们想求 \(i\bmod k=r\) 时 \([x^i]f(x)\) 之和,只需要在运用反演时移动一下 \(\omega_k\) 的指标:

[\begin{aligned} \sum{i=0}^n[i\bmod k=r][x^i]f(x)&=\frac{1}k\sum{i=0}^n\left(\sum_{j=0}^{k-1}\omegak^{j(i-r)} \right)[x^i]f(x)\ &=\frac{1}k\sum{j=0}^{k-1}\omega_{k}^{-jr}f(\omega_k^j) \end{aligned} ]

当然,我们常用原根代替单位根。

\(\mathcal{Examples}\)

「LOJ 6485」 LJJ 学二项式定理 & my solution.

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。