题解：P15132 [ROIR 2026] 位魔法
manboo
·
·
题解
看到按位与，首先需要想到二进制。再看到 16^{5 \times 10^4} 的数据范围，很容易想到数位 DP。
十六进制转二进制是好做的，每个十六进制数位都代表 4 个二进制数位，例如 B_{(16)} 代表 $1011_{(2)}
为了方便下面的 DP，需要注意把 $l, r, b$ 这三个数对齐，详见代码。
现在考虑对二进制串数位 DP，转化成差分：$[0, r]$ 内的合法方案数减去 $[0, l]$ 内的合法方案数加上 $l$ 是否合法。因为让 $l$ 减一有点麻烦，所以转化成如上差分。下面考虑 $[0, t]$ 内的合法方案数。
这个就比较模板了，我个人习惯记忆化搜索。设 $dp_{pos, lm}$ 表示到了第 $pos$ 位，先前是否顶到上界，此时的方案数。对于当前的第 $pos$ 位，设填充的数字从 $st$ 枚举到 $ed$，若 $b$ 串第 $pos$ 位为 $0$，则 $st = 0$ 表示随意；否则 $st = 1$ 表示必须填 $1$。若 $lm = 1$ 则 $ed = t_{pos}$，否则 $ed = 1$。然后继续递归即可。由于全 $0$ 也可能合法，因此不需要记录前导零。
时间复杂度 $O(n)$，$n$ 为二进制串长度。
```cpp
int cti[150];
const int N = 200005;
char hl[N], hr[N], hb[N];
int n, l[N], r[N], b[N];
inline void init(char *hc, int *c){
int m = strlen(hc + 1);
int top = (n - m) << 2; // 对齐。
for(int i = 1; i <= m; i++){
int x = cti[(int)hc[i]];
c[++top] = x >> 3;
c[++top] = x >> 2 & 1;
c[++top] = x >> 1 & 1;
c[++top] = x & 1;
}
}
const int mod = 1000000007;
inline void ADD(int &x, int y){
(x += y) >= mod && (x -= mod);
}
inline int check(){
for(int i = 1; i <= n; i++) if(b[i] && !l[i]) return 0;
return 1;
}
int maxn[N], dp[N][2];
int dfs(int pos, bool limit){
if(pos == n + 1) return 1;
if(dp[pos][limit]) return dp[pos][limit];
int res = 0, st = (b[pos] ? 1 : 0), lim = (limit ? maxn[pos] : 1);
for(int i = st; i <= lim; i++) ADD(res, dfs(pos + 1, limit && (i == lim)));
return dp[pos][limit] = res;
}
inline int solve(int *ep){
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++) maxn[i] = ep[i];
return dfs(1, true);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
for(int i = '0'; i <= '9'; i++) cti[i] = i - '0';
for(int i = 'A'; i <= 'F'; i++) cti[i] = i - 'A' + 10;
cin >> (hl + 1) >> (hr + 1) >> (hb + 1);
n = max({strlen(hl + 1), strlen(hr + 1), strlen(hb + 1)});
init(hl, l), init(hr, r), init(hb, b), n <<= 2;
cout << (solve(r) - solve(l) + check() + mod) % mod << '\n';
return 0;
}
// the name of the music at submission time: 《》
```