解题思路

用“频次统计 + FWT-AND（按位与卷积）+ 子集和 DP（SOS DP）”：

1. 统计每个值的出现次数 cnt；
2. 对 cnt 做 AND-Zeta 变换，逐点相乘，再 AND-Mobius 逆变换，得到所有有序对 (x,y) 的 x&y 等于 mask 的个数 pair[mask]；
3. 对 pair 做 子集和 DP 得到 sum[mask]=∑_{s⊆mask} pair[s]；
4. 枚举每个 z，把 sum[FULL ^ z] 累加即为答案。

复杂度分析

题目内容

给你一个整数数组 $nums$，返回其中"按位与三元组"的数目。

“按位与三元组"是由下标 $(i,j,k)$ 组成的三元组，并满足下述全部条件：

$0<=i< nums.length$

$0 <=j< nums.length$

$0<= k< nums.length$

$nums[i]$&$nums[j]$&$nums[k]==0$ ，其中 & 表示按位与运算符。

提示：

$1<= nums.length <= 10000$

$0＜= nums[i]< 2^{16}$

注意：时间复杂度是 $O(n^3)$ 的算法，会超出时间限制。

输入格式：

整数数组 $nums$ 以 "," 分隔字符串形式作为输入

输出格式：

一个数字，字符串形式

输入描述

整数数组 $nums$ 以 "," 分隔字符串形式作为输入

输出描述

一个数字，字符串形式

补充说明

注意：时间复杂度是 $O(n^3)$ 的算法，会超出时间限制。

样例1

输入

2,1,3

输出

12