汉明距离 题解

相信ACGO评测机！1秒1e9！！！！

---

题意解析：请输入文本。

考虑对于每个 $n$，求出 $1\le i\lt n$ 且 $d_H(i,n)=k$ 的总方案数。

如果 $n$ 的第 $j$ 位为 $1$，则如果 $i$ 的前面几位相同，而第 $j$ 位为 $0$，显然不论后面的数怎么填，$i$ 都小于 $n$。这时，如果汉明距离为 $k$，则就是后面有 $k-1$ 位不同，有 $j\choose k-1$ 种方案数。然后弄个前缀和就能解决了。

$\log n\le 20$，所以排列组合不需要求逆元，直接手搓杨辉三角 $O(\log^2 n)$ 预处理也能解决。

显然，这题的答案不会超过 $2^{64}-1$。所以对 $998244353$ 取模的意义是？

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int mod = 998244353;
int a[1000005][23];
int C[25][25];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	C[0][0] = 1;
	for(int i = 1; i <= 21; i++){
		for(int j = 0; j <= i; j++){
			C[i][j] = C[i - 1][j];
			if(j) C[i][j] += C[i - 1][j - 1];
		}
	}
	for(int i = 1; i <= 1000000; i++){
		for(int j = 0; j <= 20; j++){
			if(i >> j & 1){
				for(int k = 0; k <= 20; k++){
					a[i][k] += C[j][k - 1];
				}
			}
		}
		for(int j = 1; j <= 20; j++){
			a[i][j] += a[i][j - 1];
		}
		for(int j = 0; j <= 20; j++){
			a[i][j] += a[i - 1][j];
		}
	}
	int t;
	cin >> t;
	while(t--){
		int x, y;
		cin >> x >> y;
		cout << a[x][y] % mod << '\n';
	}
	
	return 0;
}

时间复杂度 $O(n\log^2 n)$，常数小评测机速度快，可以过。