非数位DP做法
查看原帖
非数位DP做法
982513
EternalHeart1314楼主2024/9/26 16:51
#include<bits/stdc++.h>
#define int long long
using namespace std;

int l, r, c[33][33];

inline int qwq(int x) {
	int sum = 0;
	while (x) x ^= x & -x, ++sum;
	return sum;
}

inline int awa(int l, int r) {
	int x, y, sum = 0;
	while (l < r) {
		x = qwq(l), y = (int)log2(l) + 1 - x;
//		cout << c[(int)log2(l & -l)][min(y - x >> 1, (int)log2(l & -l))] << '\n';
		if (y >= x) for (int i = y - x >> 1; ~i; --i) sum += c[(int)log2(l & -l)][i];
		l += l & -l;
//		cout << l << ' ' << x << ' ' << y << ' ' << k << '\n';
	}
	return sum + (qwq(l) <= (int)log2(l) + 1 >> 1);
}

inline int qaq(int r) {
	int sum = 0;
	while (r) sum += awa((r ^ (r & -r)) + 1, r), r ^= r & -r;
	return sum;
}
main() {
	for (int i = 0; i < 30; ++i) c[i][0] = 1;
	for (int i = 1; i < 30; ++i) for (int j = 1; j <= i; ++j)
		c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
	return cin >> l >> r, cout << qaq(r) - qaq(l - 1), 0;
}//l=1010001 r=1011000
//l=1000001 r=1010000
//l=1 r=1000000
//l+=l&-l;

正在写题解

2024/9/26 16:51
加载中...