原根和循环卷积\(\ \ \ 2016\)国家集训队论文集—再探快速傅里叶变换

这个连原根都不明白的屑来补坑了

原根

阶\(:\)

设\(m>1,\gcd(a,m)=1,\)那么最小的\(r\)满足\(a^r=1(\mod m)\)称为\(r\)是\(a\)在\(\mod m\)意义下的阶,记为\(\delta_m(a)\)

有关定理\(:\)

\(1.\)若\(m>1,\)并且\(\gcd(a,m)=1,\)又有\(a^n=1(\mod m),\)那\(\delta_m(a)|n\),较为显然,\(1\times 1\times 1...=1\)

\(2.\delta_m(a)|\phi(m)\)易证

\(a^{\delta_m(a)}=1(\mod m),a^{\phi(m)}=1(\mod m)\)

原根\(:\)(至于怎么求暴力就好了,原根是\(3\)的就很多)
\(a\)的阶等于\(\phi(m),a\)就是原根

有关定理\(:\)

\(1.\)当\(m=2,4,p^k,2\times p^k\)存在原根

\(2.\)每一个素数\(p\)都有\(\phi(p-1)\)个原根,每一个数都有\(\phi(\phi(m))\)个原根

\(3.\)若\(g\)是\(m\)的一个原根,则\(g,g^2,...g^{\phi(m)}\)对于\(m\)取模就是与\(m\)互质数的排列

主要是下午看到一个神奇的东西,模意义下对数等于模数变为原根

这个屑连循环卷积都不会

循环卷积

先考虑一般的线性卷积

\(f[i]=\sum_{j=0}^i a[j]\times b[i-j]\)到现在,我这个再不会就可以退役了...

时间还够,那就通读一遍论文吧

卷积的定义

\(c_r=\sum[(p+q)\mod n=r]a_pb_q\)

首先设\(w^n=1,n\)是最小的使得\(w^n=1\)的数

可以得到\(\frac{1}{n}\sum_{k=0}^{n-1}w^{vk}=[v\mod n=0]\)

如果是\(n\)的倍数,每个都是\(1\),否则每个都能互相消掉

那么

\([(p+q)\mod n=r]\)

\(=[(p+q-r)\mod n=0]\)

\(=\frac{1}{n}\sum_{k=0}^{n-1}w^{(p+q-r)k}\)

带回原式

\(c_r=\sum_{p,q}\frac{1}{n}\sum_{k=0}^{n-1}w^{(p+q-r)k}a_p b_q\)

\(\frac{1}{n}\sum_{k=0}^{n-1}w^{-rk}\sum_pw^{pk}a_p\sum_qw^{qk}b_q\)

我们可以得到两种式子

\(a_m=\sum_{k=0}^{n-1}w^{mk}b_k\)

\(c_m=\frac{1}{n}\sum_{k=0}^{n-1}w^{-mk}d_k\)

设多项式\(A(x)=\sum_{k=0}^{n-1}b_kx^k\)

\(A(w^m)=\sum_{k=0}^{n-1}b_kw^{mk}=a_m\)

我们现在知道\(b_k\)系数,可以求得当前值下的权值,系数表示法就成功转化为点值表示法

现在开始今天的重点,循环卷积

还是考虑我们的式子的\(\mod n\)不能忽略,就很不好写了

\(a_m=\sum_{k=0}^{n-1}w^{mk}b_k\)

\(=\sum_{k=0}^{n-1}w^{\frac{-(m-k)^2+m^2+k^2}{2}}b_k\)

\(=w^{-\frac{m^2}{2}}\sum_{k=0}^{n-1}w^{-\frac{(m-k)^2}{2}}w^{-\frac{k^2}{2}}b_k\)

我们把这个式子化成了卷积形式,也就是说可以用卷积实现\(DFT\)

我们设\(B_i=w^\frac{-{(i-n)^2}}{2}\)

原式可化为

\(a_m=w^{-\frac{m^2}{2}}\sum_{k=0}^{n-1}B_{m-k+n}B_{k+n}b_k\)

就可以卷积了

所以说,我们只需要对于这个东西,按\(FFT\)一样卷积一下,就得到了结果

下面废弃

就是一堆式子\(a\times b(x^{i\mod n})\times c(x^{i\mod n})\)

就是卷积完之后下标都变成\(i\mod n\)

这个东西可以使用\(Bluestein\)算法,都不讲人话...

看看论文吧...(毕竟我没找到一个我能看明白的博客)

大概式子长这样

\(a\times b(\mod n)\)就是把上标全部\(\mod n\)得到解

还是从最暴力方向考虑,直接暴力做一遍\(FFT,\)然后把对应项取模后加到相应位置就好了

这是做一次循环卷积,好多次就直接\(TLE\)

我们考虑能不能直接做长度为\(n\)的\(DFT\)