https://codeforces.com/contest/1734/problem/F
思路:
我在想前面分区间往前跳的时候发现相当于枚举每一个二进制位,并且只有当前位为 1 的时候 val 才会 ^= 1
然后发现了一个事情,第 i 位的是 0 还是 1 取决于 popcount & 1
就是求下面这个式子:
然后可以数位 dp,需要从低位往高位去 dp
请看代码:
#include
using namespace std;
typedef long long LL;
LL n, m, f[70][2][2][2];
LL dp(int now, int fl, int p, int q) {
if (~f[now][fl][p][q]) return f[now][fl][p][q];
if (now == 63) return p && !fl && !q;
LL &ans = f[now][fl][p][q]; ans = 0;
for (int i = 0; i < 2; ++i) {
int cur = i + (n >> now & 1) + q;
ans += dp(now + 1, (m >> now & 1) ? (fl & (i == 1)) : (!i ? fl : 1), p ^ i ^ (cur & 1), cur / 2);
}
return ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T; cin >> T;
while (T--)
{
cin >> n >> m; --m;
memset(f, -1, sizeof f);
cout << dp(0, 0, 0, 0) << "\n";
}
return 0;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)