T2

模拟

题目大意

汉明距离代表两个数二进制位的不同的位置的数目。我们需要计算所有的 ($x, y$),($0 \le x<y\le n$), $x,y$之间汉明距离的和

题解思路

对于每一个 $n$ ，直接枚举所有可能的 ($x, y$),($0 \le x<y\le n$)。 对于每一对之间计算他们的汉明距离的和即可。

复杂度分析

O($t\times n^2 \log V$)

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
 
const int INF = 1e18 + 10;
const int N = 200010, M = 1000010;
const int mod = 998244353;
 

bool check(int a, int b,int k) {
    int res = 0;
    for (int i = 0; i <= 30; i++) {
        if (((a >> i) & 1) != ((b >> i) & 1)) res++;
    }
    return res <= k;
}

void solve() {
    int n, k;
    cin >> n >> k;


    int res = 0;
    for (int i = 0; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (check(i, j, k)) res++;
        }
    }
    cout << res << endl;
}

signed main() {
    //init();//Prime();
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}