• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

【loj6358】 前夕

开发技术 开发技术 2周前 (04-06) 6次浏览

题意

有n种元素,则共有(2^n)个不同的集合。

求所有选择集合的方案,使得选择的集合的并集大小为4的倍数。

Solution

考虑(f(k)),表示并集大小至少为k的选择集合方案数。

容易得到(f(k)=C_{n}^{k}(2^{2^{n-k}}-1))

我们考虑构造一个容斥系数(alpha(k)),使得满足如下等式:

(ans=sum_{k=0}^{n} f(k) alpha(k))

我们考虑每一个方案的贡献,设这个方案中集合的并集大小是(x),那么显然有它的贡献为([4|x])

我们考虑这个方案在哪里被计算过,显然是所有(k<=x)(f(k))

于是其贡献亦可以被表示为(sum_{k=0}^x C_{x}^{k} alpha(k)) ,其中C的意思即为钦定这k个是被(f(k))统计到的k个。

于是有:([4 mid x]=sum_{k=0}^x C_{x}^{k} alpha(k))

根据二项式反演,(alpha(x) = sum_{k=0}^{x} (-1)^{x-k} C_{x}^{k} [4 mid k])

接下来引入单位根反演

(forall k,有[n mid k]=frac{1}{n} sum_{i=0}^{n-1} omega_{n}^{ik})

证明:

显然,当(n mid k)时,(ik)(n)的倍数,右边式子即为(frac{1}{n} times n = 1)

(n nmid k)时,后面的式子是一个等比数列求和,可以发现分子始终为0。

那,把这个单位根反演暴力代入上式

[begin{aligned}
alpha(x) &= sum_{k=0}^{x} (-1)^{x-k} C_{x}^{k} frac{1}{4} sum_{i=0}^{3} omega_{4}^{ik}\
alpha(x) &= frac{1}{4} sum_{i=0}^{3} sum_{k=0}^{x} C_{x}^{k} (-1)^{x-k} (omega_{4}^{i})^{k}\
alpha(x) &= frac{1}{4} sum_{i=0}^{3} (-1+omega_{4}^{i})^x \
end{aligned}
]

然后就可以求了,注意要做到严格(O(n))

对于(f)的部分,预处理即可做到(O(n));对于(alpha)的部分,动态维护(omega)即可。


程序员灯塔
转载请注明原文链接:【loj6358】 前夕
喜欢 (0)