主题

主题

 
   

莫比乌斯反演

  • 一维前缀和


给出G(i)所有的函数值,要求F(i)某一个指定的函数值。

这个大家都会求:


  • 二维前缀和


给出G(i,j)所有的函数值,求F(i)某一指定函数值。

这个大家勉强可以记起来,用一个容斥原理:

  • 高维前缀和

先想象一个三维的前缀和。

接下来我们在想象四维、五维的前缀和?

感觉有点晕。

但是凭借三维前缀和、二维前缀和以及一维前缀和的性质,我们似乎不难得到这样一个基于容斥原理的想法。

题目要求一致,同样给出G(p[1],p[2],p[3],……,p[k]),求F(p[1],p[2],p[3],……p[k])。

(由于OI关系,接下来的一些函数表达式可能会用数组的写法,有些可能不会很规范)

有;


于是:


  • 从高维前缀和的启发

从F推导出G,称之为一个变换。

从G推导出F,称之为一个反演。

  • 另一种一维前缀和

给出下面的一个函数:


给出所有的G(1),G(p),G(p^2),G(p^3)……,求F(1),F(p),F(p^2),F(p^3)……

不难发现:

G(1)=F(1)

G(p)=F(1)+F(p)

G(p^2)=F(1)+F(p)+F(p^2)

……

于是可以得到,G为F在某种意义上的前缀和。

那么对于问题而言:


  • 另一种高维前缀和

同样这个函数:


如果限定n=p[1]^e[1]*p[2]^e[2],其中p[1]与p[2]是质数。那么做一次反演,我们就可以得到:


  • 另一种形式的高维前缀和

由于任何一个数都可以质因数分解(除了1,我们自动忽略1好了),于是我们可以把这个式子按照类似高维前缀和一样推广下去:

给出函数G,做一次变换,得到:


(第三次出现这个式子,但是现在它已经是没有任何限定的了)

做一次反演,得到


由上面的对应关系,可以发现。


显然d|n。

而末尾还有一部分(-1)的次幂。我们现在对此进行讨论:

我们把后面这一部分记为另一个函数:


为什么参数是n/d呢?因为如果n/d确定了,那么指数sigma(k[i])也就确定了。由此我们可以把参数设置为n/d。

换一个表达形式:


接下来这个函数的值就很清楚了。

  1. 由于在我们的分析中,k[i]始终属于{0,1}。因此如果这个函数的自变量分解质因数以后,出现了某一个质因子的2次方以及2次方以上。我们就令此函数为0。这样在反演过程中,sigma式子中不会计算到任何值。

  2. 如果自变量分解质因数全部都是一次幂,那么我们数出有多少个质因数(在上面的式子(“换一个表达形式”这句话后面的那个式子)中即为m)。如果m为奇数,那么sigma(k[i])即为奇数,函数值为-1。如果m为偶数,函数值为1。

  3. 特别的,如果自变量为0,我们令函数值为1。这可以视为m=0,即偶数。

规范化的表达如下:


这就是莫比乌斯函数。

于是我们就得到了在网上经常看见的莫比乌斯函数的形式。

那么现在拥有了这一个函数,我们重新回顾变换与反演:


总算搞清楚一点莫比乌斯函数了。我本以为要搞一个晚上。看来是不必了。

 
 
评论
 
 
热度(1)