如何使用「构造函数法」去做Möbius反演

以前的反演都是瞎推一气直接硬推

昨天才了解到这个玩意可以构造函数搞。

那么怎么搞呢?

比如来个这个吧:

f\left( d \right) =\sum_{i=1}^n{\sum_{j=1}^m{\left[ \left( i,j \right) =d \right]}}

那么我们一般是:

f(n)= \sum_{i=1}^n{\sum_{j=1}^m{\left[ \left( i,j \right) =d \right]}}\ \left( n\geqslant m \right)

= \sum_{id=1}^n{\sum_{jd=1}^m{\left[ \left( i,j \right) =1 \right]}}

= \sum_{1\leqslant id\leqslant n}{\sum_{1\leqslant jd\leqslant m}{\sum_{g|id\ \&\ g|jd}{\mu \left( g \right)}}}

= \sum_{1\leqslant i\leqslant \frac{n}{d}}{\sum_{1\leqslant j\leqslant \frac{m}{d}}{\sum_{g|i,g|j}{\mu \left( g \right)}}}

= \sum_{1\leqslant g\leqslant \frac{m}{d}}{\mu \left( g \right) \lfloor \frac{n}{dg} \rfloor \lfloor \frac{m}{dg} \rfloor}

 

那么我们现在不这样做了,我们使用第二个反演式:

g\left( n \right) =\sum_{n|d}{f\left( d \right)}\,\,\Leftrightarrow \,\,f\left( n \right) =\sum_{n|d}{\mu \left( \frac{d}{n} \right) g\left( d \right)}

首先我们需要构造出一个上面所谓的 g(n) ,这里我们定义:

f\left( n \right) =\sum_{i=1}^A{\sum_{j=1}^B{\left[ \left( i,j \right) =n \right]}}

F\left( n \right) =\sum_{n|d}{f\left( d \right)}=\sum_{i=1}^A{\sum_{j=1}^B{\left[ n|\left( i,j \right) \right]}}=\sum_{i=1}^{\lfloor \frac{A}{n} \rfloor}{\sum_{j=1}^{\lfloor \frac{B}{n} \rfloor}{1}}=\lfloor \frac{A}{n} \rfloor \lfloor \frac{B}{n} \rfloor

然后呢,我们直接代进第二个反演柿子:

f\left( n \right) =\sum_{n|d}{\mu \left( \frac{d}{n} \right) F\left( d \right)}=\sum_{t=1}^{\chi}{\mu \left( t \right) F\left( nt \right)}=\sum_{t=1}^{\chi}{\mu \left( t \right) \lfloor \frac{A}{nt} \rfloor \lfloor \frac{B}{nt} \rfloor}

\left( t\xlongequal{\text{def}}\frac{d}{n},\chi \xlongequal{\text{def}}\min \left( \lfloor \frac{A}{n} \rfloor ,\lfloor \frac{B}{n} \rfloor \right) \right)

叮叮!做完啦!

[莫名其妙的]二项式反演

\text{第一反演公式}

\text{设}n\in \mathbb{N}_+\,\,,\text{多项式序列}\left\{ p_n \right\} ,\left\{ q_n \right\} \text{有如下关系:}

p_n\left( x \right) =\sum_{k=0}^n{\alpha _{nk}q_k\left( x \right) \,\,},\,\,q_n\left( x \right) =\sum_{k=0}^n{\beta _{nk}p_k\left( x \right)}

\text{且}A=\left( \alpha _{ij} \right) ,B=\left( \beta _{ij} \right) \text{为非奇异矩阵},\,\text{则有}

v_n=\sum_{k=0}^n{\alpha _{nk}u_k}\Leftrightarrow u_n=\sum_{k=0}^n{\beta _{nk}v_k}

 

 

Proof.

\text{令}p=\left( p_0,p_1,\cdots ,p_n \right) ^T,q=\left( q_0,q_1,\cdots ,q_n \right) ^T

u=\left( u_0,u_1,\cdots ,u_n \right) ^T,v=\left( v_0,v_1,\cdots ,v_n \right) ^T

\text{则可将原式表示为}

p=Aq\,\,,\,\,q=Bp

\therefore p=Aq=ABp.

\because p\text{是线性空间}R\left[ x \right] \text{的一组基}

\therefore AB=I,\,\,A^{-1}=B

\therefore v=Au\Leftrightarrow u=A^{-1}v=Bv\,\,\,\,\blacksquare

 

 

\text{二项式反演}

\text{设}\left\{ a_n \right\} \text{和}\left\{ b_n \right\} \text{是两个数列}

a_n=\sum_{k=0}^n{\left( \begin{array}{c}n\\k\end{array} \right) b_k}\Leftrightarrow b_n=\sum_{k=0}^n{\left( -1 \right) ^{n-k}\left( \begin{array}{c}n\\k\end{array} \right) a_k}

 

 

Proof.

x^n=\left( 1+x-1 \right) ^n=\sum_{k=0}^n{\left( \begin{array}{c}n\\k\end{array} \right) \left( x-1 \right) ^k}

\left( x-1 \right) ^n=\sum_{k=0}^n{\left( -1 \right) ^{n-k}\left( \begin{array}{c}n\\k\end{array} \right) x^k}

\text{由第一反演公式可得证}