数位dp

动态规划

本文参考2009年国家集训队论文《浅谈数位类统计问题》——刘聪

数位dp解决这样一类问题：求给定区间内，满足给定条件的某个D进制数或此类数的数量。

就我个人而言，最重要的是理解数位dp中图形的思考方式和数位的思考方式

【例题 1】Amount of degrees (ural 1057)

题目大意：

求给定区间[X,Y]中满足下列条件的整数个数：这个数恰好等于K 个互不相等的B的整数次幂之和。例如，设X=15，Y=20，K=2，B=2，则有且仅有下列三个数满足题意：

17 = 24+20，
18 = 24+21，
20 = 24+22。

输入：第一行包含两个整数X 和Y。接下来两行包含整数K 和B。
输出：只包含一个整数，表示满足条件的数的个数。
数据规模：1 ≤ X ≤ Y ≤ 231−1，1 ≤ K ≤ 20， 2 ≤ B ≤ 10。

分析

所求的数为互不相等的幂之和，亦即其B进制表示的各位数字都只能是0和1。因此，我们只需讨论二进制的情况，其他进制都可以转化为二进制求解。
很显然，数据范围较大，不可能采用枚举法，算法复杂度必须是log(n)级别，因此我们要从数位上下手。
本题区间满足区间减法，因此可以进一步简化问题：令count[i..j]表示[i..j]区间内合法数的个数，则count[i..j]=count[0..j]-count[0..i-1]。换句话说，给定n，我们只需求出从0 到n
有多少个符合条件的数。
假设n=13，其二进制表示为1101，K=3。我们的目标是求出0到13中二进制表示含3个1的数的个数。为了方便思考，让我们画出一棵高度为4 的完全二叉树：

为了方便起见，树的根用0 表示。这样，这棵高度为4的完全二叉树就可以表示所有4位二进制数（0..24-1），每一个叶子节点代表一个数。其中，红色路径表示n。所有小于n的数组成了三棵子树，分别用蓝色、绿色、紫色表示。因此，统计小于13 的数，就只需统计这三棵完整的完全二叉树：统计蓝子树内含3 个1的数的个数、统计绿子树内含2 个1 的数的个数（因为从根到此处的路径上已经有1 个1），以及统计紫子树内含1个1的数的个数。注意到，只要是高度相同的子树统计结果一定相同。而需要统计的子树都是“右转”时遇到的。当然，我们不能忘记统计n 本身。实际上，在算法最初时将n 自加1，可以避免讨论n本身，但是需要注意防止上溢。
剩下的问题就是，如何统计一棵高度为i的完全二叉树内二进制表示中恰好含有j个1的数的个数。这很容易用递推求出：设f[i,j]表示所求，则分别统计左右子树内符合条件数的个数，有f[i,j]=f[i-1,j]+f[i-1,j-1]。这样，我们就得出了询问的算法：首先预处理f，然后对于输入n，我们在假想的完全二叉树中，从根走到n所在的叶子，每次向右转时统计左子树内数的个数。下面是C++代码：

int dp[50][50]; //dp[i][j]表示一颗高度为i的完全二叉树内二进制表示中恰好含有j个1的个数
void init() { //预处理dp
    dp[0][0] = 1;
    for (int i = 1; i <= 31; i ++) {
        dp[i][0] = dp[i-1][0];
        for (int j = 1; j <= i; j ++) dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
    }
}
int calc(int x, int k) { //统计[0..x]内二进制表示含k个1的数的个数
    int tot = 0;
    int ans = 0;
    for (int i = 31; i > 0; i --) { //从根往下
        if (x & (1 << i)) { //如果第i位为1
            tot ++;
            if (tot > k) break;
            x ^= (1 << i); //转移到左子数上，应为以i+1为根的左右两个子树一模一样
        }
        if ((1 << (i - 1)) <= x) ans += dp[i-1][k-tot]; //如果下一层是1
    }
    if (tot + x == k) ans ++; //如果x的二进制也恰好含有k个1
    return ans;
}

最后的问题就是如何处理非二进制。对于询问n，我们需要求出不超过n的最大B进制表示只含0、1的数：找到n 的左起第一位非0、1 的数位，将它变为1，并将右面所有数位设为1。将得到的B进制表示视为二进制进行询问即可。
预处理递推f的时间复杂度为O(log2(n))，共有O(log(n))次查询，因此总时间复杂度为O(log2(n))。
实际上，最终的代码并不涉及树的操作，我们只是利用图形的方式来方便思考。因此也可以只从数位的角度考虑：对于询问n，我们找到一个等于1的数位，将它赋为0，则它右面的数位可以任意取，我们需要统计其中恰好含有K-tot个1 的数的个数（其中tot表示这一位左边的1的个数），则可以利用组合数公式求解。逐位枚举所有”1”进行统计即可。
我们发现，之前推出的f正是组合数。同样是采用“逐位确定”的方法，两种方法异曲同工。当你觉得单纯从数位的角度较难思考时，不妨画出图形以方便思考。

AC代码

int dp[40][40];
void init() {
    dp[0][0] = 1;
    for (int i = 1; i <= 32; i ++) {
        dp[i][0] = 1;
        for (int j = 1; j <= i; j ++) {
            dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
        }
    }
}
int calc(int x, int k) {
    int ret = 0;
    int cnt = 0;
    for (int i = 30; i >= 0; i --) {
        if (x & (1 << i)) {
            ret += dp[i][k - cnt];
            cnt ++;
            if (cnt > k) break;
            x ^= (1 << i);
        }
    }
    if (cnt + x == k) ret ++;
    return ret;
}
int bit[40];
int gao(int x, int b) {
    int tot = 0;
    while (x) {
        bit[tot ++] = x % b;
        x /= b;
    }
    for (int k = tot; k >= 0; k --) {
        if (bit[k] > 1) {
            for (int i = k; i >= 0; i --) bit[i] = 1;
            break;
        }
    }
    int ret = 0;
    for (int i = tot; i >= 0; i --) ret = ret << 1 | bit[i];
    return ret;
}
int main() {
    init();
    int x, y, k, b;
    while (~scanf("%d %d %d %d", &x, &y, &k, &b)) {
        int xx = gao(x, b);
        int yy = gao(y, b);
        printf("%d\n", calc(yy, k) - calc(xx - 1, k));
    }
    return 0;
}

【例题 2】Sorted bit sequence (spoj 1182)

题目大意

将区间[m,n]内的所有整数按照其二进制表示中1的数量从小到大排序。如果1的数量相同，则按照数的大小排序。求这个序列中的第k个数。其中，负数使用补码来表示：一个负数的二进制表示与其相反数的二进制之和恰好等于232。例如，当m=0，n=5 时，排序后的序列如下：

当m=-5，n=-2 时，排序后的序列如下：

输入：包含多组测试数据。第一行是一个不超过1000的正整数，表示测试数据数量。每组数据包含m,n,k三个整数。
输出：对于每组数据，输出排序后的序列中第k个数。
数据规模：m × n ≥ 0， -231 ≤ m ≤ n ≤ 231-1 ，1 ≤ k ≤ min{n − m + 1, 2 147 473 547}。

分析

我们首先考虑m、n同正的情况。
由于排序的第一关键字是1 的数量，第二关键字是数的大小，因此我们很容易确定答案中1的个数：依次统计区间[m,n]内二进制表示中含1的数量为0,1,2,…的数，直到累加的答案超过k，则当前值就是答案含1的个数，假设是s。利用例一的算法可以解决这个问题。
同时，我们也求出了答案是第几个[m,n]中含s个1 的数。因此，只需二分答案，求出[m,ans]中含s个1 的数的个数进行判断即可。
由于每次询问的复杂度为O(log(n))，故二分的复杂度为O(log2(n))，这同时也是预处理的复杂度，因此此算法较为理想。
m<0的情况，也不难处理，我们只要忽略所有数的最高位，求出答案后再将最高位赋回1即可。或者也可以直接将负数视为32位无符号数，采用同正数一样的处理方法。两种方法都需要特别处理n=0的情况。