折半搜索。
#include <bits/stdc++.h>
using namespace std;
#define lbrg p[c].begin(), p[c].end() //lower_bound range
int x, y,mo, k;
vector<vector<int> > p(50);
int main() {
freopen("zeros.in", "r", stdin);
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d%d%d", &x, &y, &mo, &k);
int rm = (x + y) >> 1; //二进制下右边的长度
int lm = x + y - rm; //左边的长度
for (int i = 0; i < (1 << rm); ++i) {
int c1 = __builtin_popcount(i);
p[c1].push_back(i % mo);
}
for (int i = 0; i < 50; ++i)
sort(p[i].begin(), p[i].end());
ll ans = 0;
for (ll i = 0; i < (1 << lm); ++i) {
if (((i >> (lm - 1)) & 1) == 0) continue;
int c1 = __builtin_popcount(i);
int c = x - c1;
if (c < 0) continue;
int lk = (i << rm) % mo;
if (lk <= k) {
ans += lower_bound(lbrg, mo - lk) - lower_bound(lbrg, k - lk);
} else {
ans += lower_bound(lbrg,mo - lk) - p[c].begin();
ans += lower_bound(lbrg, mo) - lower_bound(lbrg, mo + k - lk);
}
}
printf("%lld\n", ans);
for (int i = 0; i < 50; ++i)
p[i].clear();
}
return 0;
}
原文:https://www.cnblogs.com/huihao/p/13253543.html