2020 Petrozavodsk Winter Camp Day 5 B | Nanako

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 定理有一个经典的推论:

因此,问题转化为求

记 $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;

}

欢迎关注我的其它发布渠道