[真学习笔记] 前夕 - 单位根反演 - 广义容斥
这次是真的学习笔记了…… 真正意义上搞明白广义容斥实在说啥…… 真正搞明白了单位根的那个性质……题目大意:有个大小为n的集合S,求所有选出若干非空且互不相等的子集使得交集大小是k的倍数。要求一个O(nk)的做法。 先来说说二项式反演这件事情: P(x)=∑xk=0Q(k)(xk)Q(x)=∑xk=0P(k)(xk)(−1)x−kP(x)=∑k=0xQ(k)(xk)Q(x)=∑k=0xP...