二项式反演

对称的反演

二项式反演的主要内容就是:

\[ f_n = \sum_{i = 0}^n (-1)^i {n \choose i} g_i \longleftrightarrow g_n = \sum_{i = 0}^n (-1)^i {n \choose i} f_i \]

这个反演的式子非常的优美:在这种形式下,它们是对称的。当然,亦可以写作:

\[ f_n = \sum_{i = 0}^n {n \choose i} g_i \longleftrightarrow g_n = \sum_{i = 0}^n (-1)^{n – i} {n \choose i} f_i \]

继续阅读二项式反演

P3327:[SDOI2015]约数个数和题解

主要思路和推导

这道题还是比较有意思的(啊呀看了好久的题解才会写,真菜),主要就是把\(d\)转换成了:

\[ d(xy) = \sum_{i|x}^x \sum_{j|y}^y [\gcd(i,j) = 1] \]

可以感性理解一下:每一次约数被枚举出来的时候,只有互质的情况下才会被计数,避免了重复计数。 继续阅读P3327:[SDOI2015]约数个数和题解