大部分抄了 这篇
对其叙述上的不精确做了一定修正。
((F*G)) 表示迪利克雷卷积，([F*G]) 表示多项式卷积。
迪利克雷卷积：
[(F*G)(n) = sum_{ij=n} F(i)G(j)
]
多项式卷积：
[[F*G](n) = sum_{i+j=n}F(i)G(j)
]
多项式卷积及其反演
交换律， ([f*g]=[g*f])
结合律，([f*g]*h = f*[g*h])
存在单位元， 即有 (e) 使得 (e*f=f)， 显然， (e = [n=0])。
存在逆元，即有 (f^{-1}) 使得 (f^{-1}*f = e)
一般反演
对于数列 (f)、(g)， 如果它们可以写成如下的形式：
[g_n = sum_{i=0}^n a_{n-i}f_i \
f_n = sum_{i=0}^n b_{n-i}g_i
]
那么称这两个序列是互反的， 即 (g = [a*f])， (f = [b*g])。
显然， (f = [b*g] = [b*a*f])， 即 ([b*a] = e)。
二项式反演与矩阵
二项式反演是一般反演的加强版：
[g_n = sum_{i=0}^n a_{n,i}f_i\
f_n = sum_{i=0}^n b_{n,i}g_i
]
这里 (a)、(b) 就可以看成矩阵， 上面的式子就可以看成矩阵乘法：
[egin{align}
egin{bmatrix}
g_0\
g_1\
g_2\
end{bmatrix} &=
egin{bmatrix}
a_{00} & 0 & 0\
a_{10} & a_{11} & 0\
a_{20} & a_{21} & a_{22}\
end{bmatrix} imes
egin{bmatrix}
f_0\
f_1\
f_2\
end{bmatrix}\
egin{bmatrix}
f_0\
f_1\
f_2\
end{bmatrix} &=
egin{bmatrix}
b_{00} & 0 & 0\
b_{10} & b_{11} & 0\
b_{20} & b_{21} & b_{22}\
end{bmatrix} imes
egin{bmatrix}
g_0\
g_1\
g_2\
end{bmatrix}\
end{align}
]
推导下矩阵 (A)、(B) 的关系：
[egin{align}
vec{F} &= A imes vec{G}\
vec{G} &= B imes vec{F}\
Rightarrow vec{F} = A imes vec{G} &= A imes B imesvec{F} \
A imes B &= E
end{align}
]
满足这样关系的典型的 (a,b) 其一：
[g_n = sum_{i=0}^ninom{n}{n-i}f_i\
f_n = sum_{i=0}^n(-1)^{n-i}inom{n}{n-i}g_i
]
其二：
[g_n = sum_{i=0}^n(-1)^iinom{n}{i}f_i\
f_n = sum_{i=0}^n(-1)^iinom{n}{i}g_i
]
迪利克雷卷积及其反演
交换律、结合律、单位元 (e=[n=1])， 对于函数 (f eq 0)， 总有逆元， 且逆元唯一。
莫比乌斯反演即：
[f = (1*g) quad Rightarrow quad g = (mu*f)
]
构造 (mu)：
[(mu*1)(n) = sum_{dmid n} mu(d) = [n=1]
]
((1*mu)(1)=[1=1]=1)， 即 (mu(1)=1)。
((1*mu)(p) = mu(1)+mu(p) = [p=1]=0)，即 (mu(p)=-1)
那么由于 ((1*mu)(p^k) = 0)， (mu(p^k)=0) 就是显然的了。
由于 (mu) 是积性函数（由积性函数的逆也是积性函数），
[mu(n) = egin{cases}
1, quad n=1 \
(-1)^k, quad n=p_1p_2cdots p_k \
0, quad n的质因子有平方因子
end{cases}
]
验算下：
[(mu*1)(n) = sum_{dmid n} mu(d) = mu(1) + mu(p_1) + cdots + mu(p_1p_2)+cdots+mu(p_1p_2cdots p_k)\
= sum_{i=0}^k inom{k}{i}(-1)^i\
= [k=0] \
= [n=1]
]