2020 Petrozavodsk Winter Camp Day 5 B

发表于 分类于 ，

Problem B. Binomial

Statement

给定序列 $a_1,a_2,\dots, a_n$，问有多少对 $(a_i,a_j)$ 满足 $\binom{a_i}{a_j} \bmod 2 = 1$ 。有 $z$ 组测试数据。

$1 \leq z \leq 10$

$1 \leq n \leq 10^6$, $1 \leq a_i \leq 10^6$

Solution

Lucas 定理有一个经典的推论：

$$
\binom{a_i}{a_j} \bmod 2 = 1 \leftrightarrow a_i & a_j = a_j
$$

因此，问题转化为求

$$
\sum_{i=1}^{n} \sum_{j=1}^{n} [a_i & a_j = a_j]
$$
记 $m = \lceil \log (\max a_i) \rceil$。显然，暴力枚举可以做到 $O(n^2)$ 的复杂度。优化一下，枚举子集可以做到 $O(3^m)$ 的复杂度。但是要通过这题还是不够。clp012345 说可以 Sum over Submask DP 做到 $O(m2^m)$，于是 triple_a 就现学现用写了一个。

这个算法本身就不讲了，可以看上面链接的文章。在国内，这个算法一般被称作快速莫比乌斯变换 (FMT) 或者子集和变换，英文不好的话也可以搜这两个词，但感觉其实大部分文章都写得对新手不是很友好。个人觉得可以看这篇，我觉得下面这张插图真的把 FMT 解释得非常清楚。

一个栗子

是的，FMT 和 FWT 相关的题代码基本都不长，但是，我觉得确实不太好懂。

Code (By triple_a)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
#define int long long
using namespace std;
 
const int maxn=(1<<20);
int a[maxn],b[maxn],F[maxn],n,t;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin>>t;
	while (t--){
		cin>>n;
		for (int i=0;i<(1<<20);++i) b[i]=0;
		for (int i=0;i<n;++i) cin>>a[i], b[a[i]]++;
		for(int i = 0; i<(1<<20); ++i)
			F[i] = b[i];
		for(int i = 0;i < 20; ++i) for(int mask = 0; mask < (1<<20); ++mask){
			if(mask & (1<<i))
				F[mask] += F[mask^(1<<i)];
		}
		int res=0;
		for (int i=0;i<(1<<20);++i){
			res+=b[i]*F[i];
		}
		cout<<res<<endl;
	}
	return 0;
 
}