//#pragma comment(linker, "/STACK:1024000000,1024000000") #include <algorithm> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <string> #include <set> #include <vector> using namespace std; #define pr(x) cout << #x << " = " << x << " " #define prln(x) cout << #x << " = " << x << endl const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7; typedef long long LL; void fwtXor(LL* a, int len) { if(len == 1) return; int h = len >> 1; fwtXor(a, h); fwtXor(a + h, h); for(int i = 0; i < h; ++i) { LL x1 = a[i]; LL x2 = a[i + h]; a[i] = (x1 + x2); a[i + h] = (x1 - x2); } } void ifwtXor(LL* a, int len) { if(len == 1) return; int h = len >> 1; for(int i = 0; i < h; ++i) { // y1=x1+x2 // y2=x1-x2 LL y1 = a[i]; LL y2 = a[i + h]; a[i] = (y1 + y2) / 2; a[i + h] = (y1 - y2) / 2; } ifwtXor(a, h); ifwtXor(a + h, h); } LL n, m; const int C = 1 << 17; LL cnt[C]; int main() { ios_base::sync_with_stdio(0); cin >> n >> m; for(int i = 1; i <= n; ++i) { int x; cin >> x; ++cnt[x]; } fwtXor(cnt, C); for(int i = 0; i < C; ++i) cnt[i] *= cnt[i]; ifwtXor(cnt, C); cnt[0] -= n; for(int i = 0; i < C; ++i) cnt[i] >>= 1; LL ans = 0; for(int i = m + 1; i < C; ++i) ans += cnt[i]; cout << ans << endl; return 0; } 用FWT过了，这题应该是需要字典树做。