Which is better: Lisp or Unix?
卷积与莫比乌斯反演
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\)