卷积与莫比乌斯反演

卷积与莫比乌斯反演

Part 1 卷积

卷积是一种由两个函数生成第三个函数的操作,定义如下:

\[ h(x) = \sum_{d|x} f(d)g(\frac{x}{d} ) = \sum_{ab = x} f(a)g(a) \]

就是枚举 x 的每对因数,计算 f, g 填入他们的和。

一般记为 \(h = f \ast g\)

卷积满足交换律,结合率,分配律,且 \(f = g\) 的充要条件是 \(f \ast h = g \ast h\) 且 \(h(1) \neq 1\)

动态规划进阶

动态规划是一种常用的方法,通过记录“状态”将原问题划分为多个子问题从而使原问题得到解决。