最近在看CKKS方案,里面的编码/解码用到了n次单位根,感觉基于环上的加密,很多都会用到,现在系统的学习一下! 定义 先看定义: \[z^n=1,(n=1,2,3,...) \] 该方程的根z为n次单位根,就是说这些根是复数! 简单说:n次方根,就是多项式\(x^n-1\)或方程\(x^n-1=0\)在复数域内的n个不同的根,简称单位根 具体来讲,单位根有n次根的有n个:$$z_i=e^{2\pi ki/n },(k=0,1,2,..,n-1)$$ 复数域内:$$x_k=cos(2k\pi/n)

注意 由于蒟蒻实在太弱了~^_^~暂时无法完成证明,仅能写出简单版总结 与FFT的区别 \(NTT\)与\(FFT\)的代码区别就是把单位根换成了原根,从而实现无精度误差与浮点数的巨大常数 原根具有单位根的所有特点,原根是在特定模数下的定义 对于模数\(p\),原根\(g\)满足:\(~_{i=0}^{p-1}g^i (mod~p)\)均不同 用\(type=1,g^{\frac{p-1}{2*mid}}:type=-1,\dfrac{1}{g^{\frac{p-1}{2*mid}}}\)代替单

目录 「学习笔记」FFT 之优化--NTT 前言 引入 快速数论变换--NTT 一些引申问题及解决方法 三模数 NTT 拆系数 FFT (MTT) 「学习笔记」FFT 之优化--NTT 前言 \(NTT\) 在某种意义上说,应该属于 \(FFT\) 的一种优化. --因而必备知识肯定要有 \(FFT\) 啦... 如果不知道 \(FFT\) 的大佬可以走这里 引入 在 \(FFT\) 中,为了能计算单位原根 \(\omega\) ,我们使用了 \(\text{C++}\) 的 math 库中的

你看我都不好意思说是学习笔记了,毕竟\(FFT\)我怎么可能学得会 那就写一篇抄袭笔记吧ctrl+c真舒服 先从多项式说起吧 1.多项式 我们定义一个多项式 \[F(x)=\sum_{i=0}^{n-1}a_ix^i\] 这就是一个\(n-1\)次的多项式了 比如说\(F(x)=x^3+2x^2+x+1\)就是一个三次的多项式了 我们还可以把多项式理解成函数,比如说上面那个多项式\(F(2)=2^3+2\times2^2+2+1=19\) 很休闲吧,我会的也就这么多了 之后多项式还有两种表达形式

什么都不会的数学蒻菜瑟瑟发抖--Orz橙子(和兔子) 题目: BZOJ3328 分析: 橙子给我安利的数学题--(然后我就看着他因为矩阵乘法多模了一次卡了一天常数qwq表示同情) 先考虑一个子问题:求下面这个式子的值: \[\sum_{i=0}^n C_n^i F_i\] 首先我们知道\(F_i=\left[\begin{matrix}1 & 1\\1 & 0\end{matrix}\right]^i\).设那个矩阵为\(A\),即\(F_i=A^i\).(注意这题斐波那契数列下标从\(0

具体步骤: 1.补0:在两个多项式最前面补0,得到两个 $2n$ 次多项式,设系数向量分别为 $v_1$ 和 $v_2$. 2.求值:用FFT计算 $f_1 = DFT(v_1)$ 和 $f_2=DFT(v_2)$.这里得到的 $f_1$ 和 $f_2$ 分别是两个输入多项式在 $2n$ 次单位根处的各个取值(即点值表示) 3.乘法:把两个向量 $f_1$ 和 $f_2$ 的每一维对应相乘,得到向量 $f$.它对应输入多项式乘积的点值表示. 4.插值:用FFT计算 $v=IDFT(f)$,其实

目录 「学习笔记」FFT 快速傅里叶变换 啥是 FFT 呀?它可以干什么? 必备芝士 点值表示 复数 傅立叶正变换 傅里叶逆变换 FFT 的代码实现 还会有的 NTT 和三模数 NTT... 「学习笔记」FFT 快速傅里叶变换 几个星期之后,继 扩展欧拉定理 之后, \(lj\) 大佬又给我们来了一发数论... 虽然听得心态爆炸, 但是还好的是没有 \(ymx\) 大佬的飞机开得好... 至少我还没有坐飞机... 啥是 FFT 呀?它可以干什么? 首先,你需要知道 矩阵乘法 的相关知识. 通过

题面 传送门 思路 本文中所有$m$是原题目中的$k$ 首先,这个一看就是$d=1,2,3$数据分治 d=1 不说了,很简单,$m^n$ d=2 先上个$dp$试试 设$dp[i][j]$表示前$i$个复读机用掉了$j$个机会,注意这个东西最后求出来的是分配方案,还要乘以一个$n!$ $dp[i][j]=\sum_{k=0}^j [d|k]\binom{n-j+k}{k}dp[i-1][j-k]$ $dp[i][j]=\sum_{k=0}^j [d|k]\frac{(n-j+k)!}{(n-j)

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ450.html 题解 首先有一个东西叫做“单位根反演”,它在 FFT 的时候用到过: $$\frac 1 n \sum_{i=0}^{n-1} \omega_n ^{d\cdot i} = [d|n]$$ 其中 $\omega_n$ 表示 $n$ 次单位根. 接下来我们回到本题. 我们来搞一个指数生成函数,第 i 项表示总共复读 i 次,使得一个复读机开心的方案. $$f(x) = \sum_{i\ge

[UOJ#450][集训队作业2018]复读机(生成函数,单位根反演) 题面 UOJ 题解 似乎是\(\mbox{Anson}\)爷的题. \(d=1\)的时候,随便怎么都行,答案就是\(k^n\). \(d=2\)的时候,可以做一个\(dp\),设\(f[i][j]\)表示前\(i\)个复读机选了\(j\)个时间的方案数. 然后枚举当前这个复读机复读的次数,得到: \[f[x][j]=\sum_{i=0}^{j}[2|i]{n-j+i\choose i}f[x-1][j-i]\] 化简啥的之后

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3328 单位根反演主要就是有 \( [k|n] = \frac{1}{k}\sum\limits_{i=0}^{k-1}w_{k}^{i*n} \) 如果 k | n ,转 n 下就会是 1 :不然用等比数列求和公式可知是 0 . 一般是构造一个 \( f(x) = ( 1+x )^n \) 之类的,来求含有组合数的式子.比如 \( \sum\limits_{i=0}^{n}C_{n}^{i

传送门 直接的想法就是设 \(x^k\) 为边权,矩阵树定理一波后取出 \(x^{nk}\) 的系数即可 也就是求出模 \(x^k\) 意义下的循环卷积的常数项 考虑插值出最后多项式,类比 \(DFT\) 的方法 假设我们要求 \[C_i=\sum_{j=0}^{n}\sum_{k=0}^{n}A_jB_k[(j+k)~mod~n=i]\] \(A,B,C\) 为多项式 我们知道了 \(A,B\) 的 \(n\) 个点值 \[A(w_n^i)=\sum_{k=0}^{n}A_kw_n^{ik}\

数学杂烩总结(多项式/形式幂级数+FWT+特征多项式+生成函数+斯特林数+二次剩余+单位根反演+置换群) 因为不会做目录所以请善用ctrl+F 本来想的是笔记之类的,写着写着就变成了资源整理 一些有的没的的前置 导数 \(f'(x)=\lim\limits_{\triangle x\rightarrow 0}\frac{f(x+\triangle x)-f(x)}{\triangle x}\) \(\sin x:\cos x\) \(\cos x:-\sin x\) \(\ln x:\frac{

题目:https://loj.ac/problem/6485 先把 \( a_{i mod 4} \) 处理掉,其实就是 \( \sum\limits_{i=0}^{3} a_{i} \sum\limits_{j=0}^{n} C_{n}^{j} * s^{j} * [4|(j-i)] \) 然后把 \( [4|(j-i)] \) 单位根反演,得到 \( \sum\limits_{i=0}^{3} a_{i} \sum\limits_{j=0}^{n} C_{n}^{j} * s^{j} * \

题面 传送门 题解 我的生成函数和单位根反演的芝士都一塌糊涂啊-- \(d=1\),答案就是\(k^n\)(因为这里\(k\)个复读机互不相同,就是说有标号) \(d=2\),我们考虑复读机的生成函数 \[\left(\sum_{i=0}^\infty [2|i]{x^i\over i!}\right)^k[x^n]=\left(e^x+e^{-x}\over 2\right)^k[x^n]\] 后面那个可以二项式定理展开 顺便说一下,对于形如\(e^{ax}\)项的第\(n\)项系数就是把\(

题面 传送门 题解 我们设\(A=\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}\),那么\(A^n\)的左上角就是\(F\)的第\(n\)项 所以我们现在转化为求 \[\sum_{i=0}^n[k|i]{n\choose i}A^i\] 把\([k|i]\)单位根反演一下 \[ \begin{aligned} ans &=\sum_{i=0}^n[k|i]{n\choose i}A^i\\ &={1\over k}\sum_{i=0}

也许更好的阅读体验 \(\mathcal{Description}\) 原题链接 \(T\)组询问,每次给\(n,s,a_0,a_1,a_2,a_3\)求 \(\begin{aligned}\left(\sum ^{n}_{i=0}\begin{pmatrix} n \\ i \end{pmatrix}\cdot s^{i}\cdot a_{i\ mod\ 4}\right)mod\ 998244353\end{aligned}\) \(\mathcal{Solution}\) 这道题要用单位根

正题 题目链接:https://loj.ac/p/6247 题目大意 给出\(n,k\)求 \[\sum_{0\leq i\leq n,i|k}\binom{n}{i} \] 对\(998244353\)取模 \(1\leq n\leq 10^{15},1\leq k\leq 2^{20},k=2^p(p\in N)\) 解题思路 随便找的一题竟然是单位根反演,不过很基础而且很裸. 首先单位根反演的式子\([i|k]=\frac{1}{k}\sum_{j=0}^{k-1}\omega_k^{i\

FFT bilibili 3b1b视频讲解 核心过程: 原根 Definition 若 \(a\) 模 \(m\) 的阶等于 \(\varphi(m)\),则称 \(a\) 为模 \(m\) 的一个原根.\((a\in\mathbb{Z},m\in\mathbb{N^+})\) Special Case \(p=1004535809=2^{21}\times479+1,g=3\) \(p=998244353=2^{23}\times7\times17+1,g=3 \leftarrow most

\(\mathcal{Preface}\)   单位根反演,顾名思义就是用单位根变换一类式子的形式.有关单位根的基本概念可见我的这篇博客. \(\mathcal{Formula}\)   单位根反演的公式很简单: \[[k|n]=\frac{1}k\sum_{i=0}^{k-1}\omega_k^{ni} \] \(\mathcal{Proof}\)   分类讨论: \(k|n\). 那么 \((\forall i)(\omega_k^{ni}=1)\),所以右侧为 \(\frac{1}k\su