单位根与其若干应用

蔚落 2021-12-23 19:35 276阅读 0赞

# 单位根与其若干应用 #

### 单位根的几个性质 ###

对于一种运算条件下，若\\((w\_n^1)^n = 1\\)，那么\\(w\_n^1\\)即\\(n\\)次单位根。  
我们令\\(w\_\{n\}^k = (w\_\{n\}^1)^k\\)。  
单位根在复数意义下有三角表示：\\(w\_n^k = e^\{\\frac\{2\\pi k\}\{n\}i\} = cos(\\frac\{2\\pi k\}\{n\}) + sin(\\frac\{2\\pi k\}\{n\})i\\)。  
在模\\(p\\)意义下，由于原根\\(g\\)满足\\(g^\{p-1\} \\equiv 1(mod\\ p)\\)，所以可以令\\(w\_\{p\}^1 = g^\{\\frac\{p-1\}\{n\}\}\\)。  
复数运算的几何意义：模长相乘，转角相加。  
根据复数乘法的几何意义，显然有：

*  \\(w\_\{n\}^k = w\_\{nr\}^\{kr\}\\)
 *  \\(w\_\{n\}^k = w\_\{n\}^\{k\\% n\}\\)
 *  \\(w\_\{n\}^\{k + \\frac\{n\}\{2\}\} = -w\_\{n\}^k\\)

这几个性质后面都会用到。

### 单位根反演 ###

我们有式子：\\(\\frac\{1\}\{n\}\\sum\_\{i=0\}^\{n - 1\} (w\_\{n\}^k)^i = \[n|k\]\\)，证明其实不难。  
若\\(n|k\\)，那么\\(w\_n^k = w\_\{n\}^0 = 1\\)，所以\\(\\sum\_\{i=0\}^\{n-1\} (w\_n^k)^i = n\\)。  
否则，\\(\\sum\_\{i=0\}^\{n-1\} (w\_n^k)^i = \\frac\{1-(w\_\{n\}^\{k\})^n\}\{1 - w\_\{n\}^k\} = \\frac\{1 - w\_n^0\}\{1 - w\_n^k\} = 0\\)。  
证毕。  
可以化简大量包含形如\\(\\sum\_i\[d|i\] F(i)\\)的式子的计算。

### 离散傅里叶变换(DFT) ###

我们用\\(n\\)个点可以表示出\\(n-1\\)次多项式，称这种表示为点值表示法。  
点值表示法的多项式乘法显然为\\(O(n)\\)，即\\((x,y\_1)\*(x,y\_2) = (x,y\_1y\_2)\\)。  
点值表示法转系数表示法的传统做法为拉格朗日差值，复杂度\\(O(n^2)\\)。  
傅里叶提出，通过带入单位根，优化这个过程。  
对于一个\\(n-1\\)次多项式\\(A(x) = \\sum\_\{i=0\}^\{n-1\} a\_i x^i\\)，考虑带入\\(x\_k = w\_\{n\}^k\\)来做出点值表示，其中\\(k\\in\[0,n)\\)。  
我们设得到的点值表示为\\(A(x):\\\{(w\_n^k,y\_k)|k\\in \[0,n)\\\}\\) ，令\\(B(x) = \\sum\_\{i=0\}^\{n-1\} y\_i x^i\\)。  
把\\(w\_\{n\}^\{k\}\\)的倒数分别带入\\(B(x)\\)中：  
\\(B(w\_n^\{-k\}) = \\sum\_\{i=0\}^\{n-1\} y\_i w\_n^\{-ki\} = \\sum\_\{i=0\}^\{n-1\} (\\sum\_\{j=0\}^\{n-1\} a\_j w\_n^\{ij\})w\_n^\{-ki\}\\)  
\\(B(w\_n^\{-k\}) = \\sum\_\{j=0\}^\{n-1\} \\sum\_\{i=0\}^\{n-1\} a\_j w\_n^\{(j-k)i\}\\)，后面一坨就是单位根反演的变形。  
\\(B(w\_n^\{-k\}) = \\sum\_\{j=0\}^\{n-1\} a\_j (\\sum\_\{i=0\}^\{n-1\} w\_n^\{(j-k)i\}) = k\_j n\\)。  
所以\\(a\_k = \\frac\{B(w\_n^\{-k\})\}\{n\}\\)，爽！  
可以发现我们不需要拉格朗日差值了，带入单位根倒数得点值表示，然后除\\(n\\)就是每一项的系数了。  
总结一下，我们得到了这样的东西：  
\\(f\_i = \\sum\_\{j=0\}^\{n-1\} w\_n^j g\_j\\) \--------------------> \\(g\_i = \\frac\{1\}\{n\}\\sum\_\{j=0\}^\{n-1\} w\_\{n\}^\{-j\} f\_j\\)。

### 快速傅里叶变换(FFT) ###

考虑利用离散傅里叶变换，实现快速多项式乘法。  
我们假设求长度为\\(n\\)的多项式的离散傅里叶变换，设\\(d|n\\)。  
考虑求\\(A(x) = \\sum\_\{i=0\}^\{n-1\} a\_i x^i\\)带入\\(w\_n^\{0,1...n-1\}\\)的点值表示结果，我们按照模\\(d\\)剩余类分类。  
设\\(A\_r(x) = \\sum\_\{i=0\}^\{\\frac\{n\}\{d\} - 1\} a\_\{id+ r\} x^i\\)，假设我们已经求得了它们带入\\(w\_\{\\frac\{n\}\{d\}\}^\{0,1,...\\frac\{n\}\{d\}-1\}\\)的点值表示结果。  
那么\\(A(w\_\{n\}^k) = \\sum\_\{r=0\}^\{d-1\} (w\_\{n\}^\{kr\}) A\_r((w\_\{n\}^k)^d) = \\sum\_\{r=0\}^\{d-1\} (w\_n^\{kr\\% n\}) A\_r(w\_\{\\frac\{n\}\{d\}\}^k)\\)。  
所以貌似分治就行了......  
一般使用时，我们把\\(n\\)补全为\\(2^t\\)，这样\\(d\\)恒等于\\(2\\)，每次折半分治即可。  
关于非递归\\(FFT\\)：  
预处理每个点分治若干次后到达的实际位置，然后从底向上还原(每次合并都是一段区间)。  
快速数论变换(NTT)的原理与快速傅里叶变换(FFT)没有任何区别，所以就不写了。

### 循环卷积 ###

当多项式乘法在指数模\\(n\\)意义进行，我们乘其为指数模\\(n\\)意义下的循环卷积。  
而单位根有很好的性质：\\(w\_\{n\}^k = w\_\{n\}^\{k\\% n\}\\) 。  
我们假设能够求出带入\\(w\_n^\{0,1,2...,n-1\}\\)后多项式的值，那么\\(Idft\\)就能够求出原多项式的每一项系数。  
一类特殊循环卷积：  
考虑对于长度为\\(n\\)的多项式\\(A(x)\\),\\(B(x)\\)，求：  
\\(C(x):\\ C\_k = \\sum\_\{i=0\}^\{n-1\} \\sum\_\{j=0\}^\{n-1\}\[(i+j)\\%n=k\] a\_ib\_j\\)。  
一个非常有趣的结论：  
求得\\(A(x)\\)、\\(B(x)\\)的离散傅里叶变换的点值，那么\\(C(x)\\)的点值表示就为\\(A(x)\\)点值与\\(B(x)\\)点值的积。  
即若你要求\\(A(x)^m\\)，那么只需要求\\(A(x)\\)的傅里叶变换点值，把点值\\(m\\)次方后再还原回去即可。  
所谓傅里叶变换点值就是指带入\\(w\_\{n\}^\{0,1...,n - 1\}\\)得到的点值 。  
我们来证明一下，其实暴力带入验证即可。  
\\(C(w\_n^k) = A(w\_n^k) B(w\_n^k) = (\\sum\_\{i=0\}^\{n-1\} a\_i w\_n^\{ki\})(\\sum\_\{j=0\}^\{n-1\} b\_j w\_\{n\}^\{kj\})\\)  
\\(C(w\_n^k) = \\sum\_\{i=0\}^\{n-1\} \\sum\_\{j=0\}^\{n-1\} a\_ib\_j w^\{k(i+j)\}\_n = \\sum\_\{r=0\}^\{n-1\} \\sum\_\{i=0\}^\{n-1\} \\sum\_\{j=0\}^\{n-1\}\[(i+j)\\%n=r\] a\_ib\_j w\_n^\{k\}\\)  
刚好就是循环卷积要求的东西，证毕。

### 几道有趣的题目 ###

嘿嘿嘿......见下面。

### \[CTSC2010\] 性能优化 ###

问题就是求\\(B(x)^C\\)在指数模\\(n\\)意义下的循环卷积，同时模数为\\(n+1\\)，多项式长度为\\(n\\)。  
我们在上面已经讨论过这种循环卷积的处理方式了。  
所以只需要求\\(B(x)\\)带入\\(w\_\{n\}^\{0,1...n-1\}\\)的点值表示，然后\\(C\\)次方后再\\(Idft\\)回去。  
我们需要支持快速\\(dft\\)，而我们已知\\(n\\)能够分解为\\(2^\{k\_1\}3^\{k\_2\}5^\{k\_3\} 7^\{k\_4\}\\)。  
那么考虑分治\\(dft\\)，类似\\(fft\\)每次把多项式分成若干份，然后自底向上合并即可。  
由于每次分成的份数不超过\\(7\\)，所以合并的复杂度显然是正确的。  
可以预先搜出每个点在分治\\(dft\\)的过程中最后到了哪个位置，这样就可以非递归实现算法了。

### \[牛客挑战赛23F\] 计数(解法一) ###

对于一棵生成树，设其边权为\\(\\sum\_\{e\\in E\} val\_e\\)，那么\\(Ans = \\sum\_E \[k|\\sum\_\{e\\in E\} val\_e\]\\)。  
单位根反演有：\\(Ans = \\frac\{1\}\{k\}\\sum\_E \\sum\_\{j=0\}^\{k-1\} (w\_k^\{\\sum\_\{e\\in E\} val\_e\})^j = \\frac\{1\}\{k\} \\sum\_\{j=0\}^\{k-1\} \\sum\_E \\prod\_\{e\\in E\} (w\_k^j)^\{val\_e\}\\)。  
后面一坨是我们熟悉的变元矩阵树定理，所以\\(\\sum\_E \\prod\_\{e\\in E\} (w\_k^j)^\{val\_e\}\\)直接用矩阵树定理算即可。

### \[牛客挑战赛23F\] 计数(解法二) ###

依旧考虑变元矩阵树定理，考虑把边权相加变为边权相乘。  
定义每条边\\(e\\)的生成函数\\((1 + x^\{val\_e\})\\)，那么一个合法边集可以看做在指数模\\(k\\)意义下的循环卷积。  
考虑令\\(x = w\_\{k\}^\{0,1...k-1\}\\)，那么带入\\(w\_k^j\\)做矩阵树定理就能够得到\\(A(w\_k^\{j\})\\)。  
而我们的最终目标是求\\(A(x)\\)中的系数\\(a\_0\\)，所以再\\(Idft\\)即可。

### \[牛客挑战赛11E\] 白兔的刁难(解法一) ###

考虑组合意义，不难发现\\(ans\_t\\)就是\\((1+x)^n\\)在指数模\\(k\\)意义下的循环卷积第\\(t\\)项的系数。  
暴力带入\\(w\_k^\{0,1...,k-1\}\\)，得点值表示后再\\(Idft\\)即可。

### \[牛客挑战赛11E\] 白兔的刁难(解法二) ###

考虑暴力单位根反演，\\(Ans\_t = \\sum\_\{i=0\}^\{n\} \\binom\{n\}\{i\} \[k|i-t\] = \\frac\{1\}\{k\}\\sum\_\{i=0\}^\{n\} \\binom\{n\}\{i\} \\sum\_\{j=0\}^\{k-1\} (w\_\{k\}^\{i-t\})^j\\)。  
所以\\(Ans\_t = \\frac\{1\}\{k\} \\sum\_\{j=0\}^\{k-1\} (w\_k^\{-t\})^j \\sum\_\{i=0\}^n \\binom\{n\}\{i\} (w\_\{k\}^i)^j = \\frac\{1\}\{k\} \\sum\_\{j=0\}^\{k-1\} (w\_k^\{-t\})^j (1 + w\_k^j)^n\\) 。  
不难发现这是一个\\(Idft\\)形式。  
我们把\\((1+w\_k^j)^n\\)看做\\(A(w\_k^j)\\)(指数模\\(k\\)意义下的循环卷积)，即\\((1+w\_k^j)^n = A(w\_k^j) = y\_j\\) 。  
那么\\(Ans\_t = B(w\_k^\{-t\}) = \\frac\{1\}\{k\} \\sum\_\{j=0\}^\{k-1\} y\_j (w\_k^\{-t\}) = \\frac\{1\}\{k\} (a\_t k) = a\_t\\)。  
所以\\(Ans\_t\\)等于\\(A(x) = (1 + x)^n\\)这个循环卷积的第\\(t\\)项系数，与我们组合意义所得的内容一致。

#  #

转载于:https://www.cnblogs.com/GuessYCB/p/10324928.html