https://acm.ecnu.edu.cn/contest/363/
D. 一！二！三！
题意：给定 L,R,0≤L≤R≤1018，求满足 x⊕3x=2x 的 x 的个数。
数位dp
看到这数据范围就要想到数位 dp。
首先推式子。
左右同时异或上 x，得到 3x=x⊕2x，即 x⊕2x=x+2x。
我们知道 x+y=x⊕y+((x&y)<<1)，所以 x+2x=x⊕2x+((x&2x)<<1)，所以 x⊕2x+((x&2x)<<1)=x⊕2x，即 (x&2x)<<1=0，即 x&2x=0。
也就是说 x 没有两个相邻的 1。
接下来就可以数位dp了。
cal(pos, lim, sta) 表示在处理第 pos 位，lim 表示上界限制，sta=0表示该位只能放 0，sta=1表示该位可以放 0 或 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int T;
ll L, R;
int a[N];
map<int, ll>dp[2];
ll cal(ll x, int pos, int lim, int sta) {
if (x == -1)return 0;
if (pos == -1) {
return 1;
}
if (!lim && dp[sta].count(pos))return dp[sta][pos];
ll ans = 0;
int up = (lim ? (x >> pos & 1) : 1);
if (sta == 0)ans += cal(x, pos - 1, lim&(up == 0), 1);
else {
if (up == 0)ans = cal(x, pos - 1, lim&(up == 0), 1);
else ans = cal(x, pos - 1, lim&(up == 0), 1) + cal(x, pos - 1, lim&(up == 1), 0);
}
if (!lim)dp[sta][pos] = ans;
return ans;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%lld%lld", &L, &R);
ll x = cal(R, 60, 1, 1), y = cal(L - 1, 60, 1, 1);
printf("%lld\n", x - y);
}
return 0;
}
|
