【Trick】一类集合计数问题

HMF-have much fun Site

文章标签

✎首页

☰归档

★标签

☎关于

♚推荐

说说

友人帐

载入天数...

载入时分秒...

总访问量: | 访问人数:

阅

2023-09-03

2 min read

【Trick】一类集合计数问题

热度: loading...

一类集合计数问题，形如

给定一个数列 $A$ ，设一个集合 $S=$ $\{$ $a_{b_1},a_{b_2},a_{b_3},\dots ,a_{b_k}$ $\}$ ，其权值为 $val(S)$ ，求所有满足集合内所有元素进行⊕运算后值为 $x$ 的集合的权值和。

其中 ⊕ 运算是任意位运算， $val_S$ 是某种能用多项式表达出来的函数。

这种问题我们可以用 FWT 来解决。以 $val(S)=1$ 为例，显然我们可以将原式表达成集合幂级数形式：

\prod \limits_{i=1}^n (1+x^{a_i})

这里的乘是 ⊕ 运算。

显然直接 FWT 是不可行的。我们对每个因式考虑他的 FWT。由于因式只有两项，所以其对 FWT 每一位的贡献只有两种可能，我们设其为 $p$ 和 $q$ 。

这里运用到一个性质，FWT 的和等于和的 FWT，我们将所有因式加在一起进行 FWT。考虑 FWT 后第 $i$ 位的值为 $c_i$ ，显然可以列出式子 $kp+(n-k)q=c_i$ ,解完式子之后我们就可以知道这一位有多少个 $p$ ，多少个 $q$ ，我们变可以依此推出 FWT 的乘积在这一位为 $p^k q^{n-k}$ 。