学习笔记—狄利克雷卷积

· · 个人记录

0 前置芝士

一、积极性函数

$\qquad$对于 $gcd(n,m)=1$ 则有 $f(nm)=f(n)\times f(m) $\qquad$对于任意的 $n$,$m$ 都有 $f(nm)=f(n)\times f(m)

二、常用函数

$\qquad \varepsilon(n)=e(n)=[n=1]$注：定义：自变量为 $0

时函数值为\dfrac{1}{2}

$\qquad 1(n)=1 $\qquad id(n)=n $\qquad id^k(n)=n^k $\qquad \varphi(n) $\qquad \sigma_k(n)=\sum\limits_{d|n}d_k$ 特别的当 $k=0$ 时即为约数个数 $d(n) $\qquad\mu(n)=\begin{cases}0&n=0\\1&n=1\\0&n=p^2\\(-1)^k&n=p_1^{r_1}\times p_2^{r_2}\times ...\times p_k^{r_k}\end{cases}

1 狄利克雷卷积

$\qquad$ 两个数论函数 $f\&h$ 的卷积定义为： $\qquad\qquad (f \times h)(n)=\sum\limits_{d|n}f(d)g(\dfrac{n}{d}) $\qquad$ 交换律：$f\times g=g\times ff\times g=g\times f \qquad$ 结合律：$(f\times g)\times h=f\times (g\times h)(f\times g)\times h=f\times (g\times h) \qquad$ 分配率：$f\times (g+h)=f\times g+f\times hf\times (g+h)=f\times g+f\times h \qquad$ 单位元：$f\times e=e\times ff\times e=e\times f $\quad$ 三、狄利克雷前缀和 $\qquad$ 特殊的，对于定义式，当 $g(n)=1(n)=1$ 时 $\qquad\qquad f(n)\times 1=\sum\limits_{d|n}f(d)

2 计算机卷积形式：

$\qquad (f\times g)(n)=\sum\limits_{a+b=n}f(a)\times g(b) $\quad$ 二、循环卷积 $\qquad (f\times g)(n)=\sum\limits_{(a+b)\%n=k}f(a)\times g(b) $\qquad (f\times g)(n)=\sum\limits_{axorb=n}f(a)\times g(b) # 3 计算卷积的快速程序 $\quad$ 一、快速博里叶变换 $(FFT) $\qquad$ 代码： ```cpp struct FastFourierTransform { Complex omega [N], omegaInverse [N] ; void init ( const int& n ) { for ( int i = 0 ; i < n ; ++ i ) { omega [i] = Complex ( cos ( 2 * PI / n * i), sin ( 2 * PI / n * i ) ) ; omegaInverse [i] = omega [i].conj ( ) ; } } void transform ( Complex *a, const int& n, const Complex* omega ) { for ( int i = 0, j = 0 ; i < n ; ++ i ) { if ( i > j ) std :: swap ( a [i], a [j] ) ; for( int l = n >> 1 ; ( j ^= l ) < l ; l >>= 1 ) ; } for ( int l = 2 ; l <= n ; l <<= 1 ) { int m = l / 2; for ( Complex *p = a ; p != a + n ; p += l ) { for ( int i = 0 ; i < m ; ++ i ) { Complex t = omega [n / l * i] * p [m + i] ; p [m + i] = p [i] - t ; p [i] += t ; } } } } void dft ( Complex *a, const int& n ) { transform ( a, n, omega ) ; } void idft ( Complex *a, const int& n ) { transform ( a, n, omegaInverse ) ; for ( int i = 0 ; i < n ; ++ i ) a [i] /= n ; } } fft ; ``` $\qquad$ 由于对 $FFT$ 的描述太长，在此不予给出 $\quad$ 二、快速沃尔什变换 $(FWT) ```cpp void FWT(ll *P,int opt) { for(int i=2;i<=N;i<<=1) for(int p=i>>1,j=0;j<N;j+=i) for(int k=j;k<j+p;++k) P[k+p]+=P[k]*opt; } ``` $\qquad$ $and$ 卷积只需要在 $or$ 卷积的基础上修改一点点就好了 ```cpp void FWT(ll *P,int opt) { for(int i=2;i<=N;i<<=1) for(int p=i>>1,j=0;j<N;j+=i) for(int k=j;k<j+p;++k) P[k]+=P[k+p]*opt; } ``` $\qquad$ $xor$ 卷积其实也差不多(这个是在模意义下的 $FWT$ ) $\qquad$ 如果不是在模意义下的话，开一个$long$ $long$，然后把逆元变成直接除二就好了。 ```cpp void FWT(int *P,int opt) { for(int i=2;i<=N;i<<=1) for(int p=i>>1,j=0;j<N;j+=i) for(int k=j;k<j+p;++k) { int x=P[k],y=P[k+p]; P[k]=(x+y)%MOD;P[k+p]=(x-y+MOD)%MOD; if(opt==-1)P[k]=1ll*P[k]*inv2%MOD,P[k+p]=1ll*P[k+p]*inv2%MOD; } } ```