数位 DP
数位 DP 的本质就是将数字的每位分开考虑，从而降低时间复杂度。数位 DP 的问题分为几种类型：
- 求出 \([l,r]\) 区间内，数位满足指定条件的数的个数；
- 求出数位满足指定条件的数中，按大小排名第 \(k\) 的是哪个；
- ...
常用的方法有
- 差分法：将区间询问转化为前缀询问；
- 试填法：求出第 \(k\) 小（大）的数字
给出两个数 \(a,b\)，求出 \([a,b]\) 间各位数字之和能整除原数的数的个数。
\(1\le a\le b\le 10^{18}\)
注意到一个 \(\le 10^{18}\) 的数字的数位之和不会超过 \(18\times 9=162\)，我们枚举 \([1,162]\) 之间的所有数，然后进行数位 dp，时间复杂度 \(O(162\times 18\times 162^2\times 10)\)。
多次询问，第一行给出询问次数 \(T\)。
每次询问给定 \(l,r,k\)，问区间 \([l,r]\) 内有多少数字满足，各数位的 LIS 长度恰好为 \(k\)。
\(T\le 10^4,\ 0<L\le R<2^{63}-1,\ 1\le k\le 10\)
先差分转化为前缀的询问。然后考虑如何处理 LIS 的限制。我们有两种 dp 来求 LIS：\(f_{i}\) 表示前缀中最后一个数字为 \(i\) 的 LIS；\(f_i\) 表示前缀中长度为 \(i\) 的 LIS 中最后一个数字的最小值。其中第一种方法我们常用 BIT 进行优化，第二种方法就是常说的二分法。
第一种 dp 有值的位置不连续，似乎没什么前途。而观察第二种 dp 我们发现一些性质：\(f_i\) 有值的部分是一个前缀，并且值严格单调递增。因此，我们只需记录哪些数字出现在 \(f_i\) 中，然后将它们顺序排列，即可得到 \(f\) 数组。
由于值域很小，\(f_i\) 最多出现 \(0\sim 9\) 十个数字。因此可以直接将 \(f_i\) 状压进一个 \(2^{10}\) 的 int 中即可。写出状压状态的转移函数，剩余部分的实现是容易的，记得处理前导零。
代码
| #include<iostream>
#include<bitset>
#include<cassert>
#define int long long
using namespace std;
int k, ans;
int num[20], nn;
int lg[1 << 10], popcnt[1 << 10];
int trans(int s, int c) {
if(s == 0) return s ^ (1 << c);
int tmp = lg[s & ((1 << c) - 1)];
int pre = s & ~((1 << (tmp + 1)) - 1);
if(!pre) return s ^ (1 << c);
pre = lg[pre & -pre];
if(c < pre) return s ^ (1 << pre) ^ (1 << c);
return s;
}
int f[11][20][1 << 10];
int dfs2(int x, int s, bool zero) {
if(!zero && ~f[k][x][s]) return f[k][x][s];
if(x == 0) {
if(zero) return 0;
if(popcnt[s] == k) return f[k][x][s] = 1;
return f[k][x][s] = 0;
}
int res = 0;
for(int i = 0; i <= 9; i++) {
res += dfs2(x - 1, zero && (i == 0) ? 0 : trans(s, i), zero && (i == 0));
}
if(!zero) {
f[k][x][s] = res;
}
return res;
}
void dfs1(int x, int s, bool zero) {
if(x == 0) {
if(popcnt[s] == k) ++ans;
return;
}
for(int i = 0; i < num[x]; i++) {
ans += dfs2(x - 1, zero && (i == 0) ? 0 : trans(s, i), zero && (i == 0));
}
dfs1(x - 1, trans(s, num[x]), 0);
}
int calc(int r) {
ans = 0;
nn = 0;
while(r) {
num[++nn] = r % 10;
r /= 10;
}
dfs1(nn, 0, 1);
return ans;
}
signed main() {
lg[0] = -1;
for(int i = 2; i < (1 << 10); i++) lg[i] = lg[i >> 1] + 1;
for(int i = 1; i < (1 << 10); i++) popcnt[i] = popcnt[i ^ (i & -i)] + 1;
for(int k = 0; k <= 10; k++) {
for(int i = 19; i >= 0; i--) {
for(int j = 0; j < 1024; j++) f[k][i][j] = -1;
}
}
int T;
cin >> T;
while(T--) {
int l, r;
cin >> l >> r >> k;
cout << calc(r) - calc(l - 1) << '\n';
}
return 0;
}
|
给定两个正整数 \(l,r\)，询问满足以下条件的数对 \((x,y)\) 的个数：
- \(l\le x\le y\le r\)；
- \(y\bmod x=y\operatorname{xor} x\)；
\(1\le l\le r\le 10^{18}\)
注意到若 \(y\ge 2x\)，那么 \(y\) 的最高位不存在于 \(x\) 中，因此 \(y\operatorname{xor}x\) 的结果中该位一定为 \(1\)；而 \(y\bmod x\) 中该位一定为 \(0\)，矛盾。因此 \(y<2x\)，从而推出 \(y\bmod x=y-x\)。又因为 \(y\operatorname{xor}x=y\bmod x=y-x\)，因此 \(y\) 的二进制位包含 \(x\) 的二进制位。
因此，\((x,y)\) 合法的充要条件是：\(x,y\) 最高位相同，并且 \(x\subseteq y\)。这里使用数位 dp 即可，记一个前导零，\(x\) 是否顶格，\(y\) 是否顶格即可。
代码
| #include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
int l, r;
int f[70][2][2][2];
int dfs(int x, bool z, bool mn, bool mx) {
int &res = f[x + 1][z][mn][mx];
if(~res) return res;
if(x < 0) {
return res = 1;
}
res = 0;
for(int i = 0; i <= 1; i++) {
for(int j = 0; j <= i; j++) {
if(z && (i ^ j)) continue;
if(mn && (j == 0) && (l & (1ll << x))) continue;
if(mx && (i == 1) && !(r & (1ll << x))) continue;
res = (res + dfs(x - 1, z && !i, mn && (j == (bool)(l & (1ll << x))), mx && (i == (bool)(r & (1ll << x))))) % MOD;
}
}
return res;
}
signed main() {
memset(f, -1, sizeof(f));
cin >> l >> r;
cout << dfs(63, 1, 1, 1) << '\n';
return 0;
}
|