计数问题小技巧

计数问题小技巧

转化为前缀和,后缀和形式

二项式反演

可以直接将”恰好“转化为”不多于“,”不少于“,有时可以很好的简化问题

但要满足如下要求

[f(x) = sum_{i = 0}^x {x choose i}g(i)\ g(x) = sum_{i=0}^x (-1)^{x-i}{xchoose i} f(x) ]

还有其他形式

莫比乌斯反演

比较套路,数论相关题必备芝士

但需要满足如下要求

[若 F(x) = sum_{d|x}f(x) = f * I\ f(x) = sum_{d|x}F(x) * mu(frac xd) = F * mu ]

学到了新的在更新吧

原文地址:https://www.cnblogs.com/Hs-black/p/12782002.html