AcWing1081. 度的数量

题目描述

求给定区间 ([X,Y]) 中满足下列条件的整数个数：这个数恰好等于 (K) 个互不相等的 (B) 的整数次幂之和。

例如，设 (X = 15, Y = 20, K = 2, B = 2)，则有且仅有下列三个数满足题意：

(17 = 2^4 + 2^0)
(18 = 2^4 + 2^1)
(20 = 2^4 + 2^2)

题意剖析

(qquad) 我们把原本的数拆成一个与 (B) 有关的多项式，系数最高只能是 (1)（这是因为要求互不相同），会呈现这样的情况：

(qquad)如果此时我们把系数数列单独提出来((forall xin a, xin[0,1]))，会呈现下面的这种情况：

那么只要在系数数列中有 (k) 个 (1) 就说明这个数符合题意。

因此题目转化成：当一个序列对应的B进制数在区间内时，中选出K个1的方案有多少种

解题思路

(qquad) 这种统计关于数字位的题目就采用数位dp，对于区间的方案数可以很自然转化成前缀方案数。

(qquad)问题就是如何进行数位DP
(qquad 1.)首先要把一个数的每一位分解出来，这一步比较简单。

while (x) a[ ++ len] = x % b, x /= b;

(qquad 2.)从最高位开始 (DP)

状态表示

状态边界

状态转移

(qquad) 我比较菜，这里就用记忆化搜索了

搜索参数：(dfs(p, cnt, limit))

limit的转移

(qquad) (limit) 表示的是前面填的数是否和区间右端点对应数相等，当 (limit=0) 代表 这个位置上可以填所有数，因为上一个数并未着区间右端点的这位上的最高，所以不管这位填谁，都不超出区间。相反，如果 (limit = 1)，那么我们只能填(0sim a[p])的数（(p)是当前搜索的位）。

(qquad)所以我们可以对 (limit) 的转移做以下分析

(qquad 1.)当(limit = 1) 且 填的数 (i = up), 的时候，(limit=1)
(qquad 2.)当(limit = 1) 且 填的数 (i eq up) 的时候，(limit = 0)
(qquad 3.)当(limit = 0)时，不论如何，(limit) 只能变成 (0)

(qquad)得到结论：limit转移到limit&&(i==up)

cnt的转移

(qquad)我们的(cnt)可以加的时候，只有填入的数 (i == 1)才可以转移，这个简单，不再赘述

p的转移

(qquad)从最高位开始，每次枚举上一位，这样每次 (p-1)

所以将上面三者结合起来，可以得到下面的代码

int dp(int p, int cnt, int limit) 
{
    int &v = f[p][cnt]; //记忆化

    if (!p) return cnt == k; //搜索完毕判断方案合法
    if (!limit && ~v) return v; // 记忆化

    int up = limit ? a[p] : b - 1, res = 0; // limit的限制填数上界

    for (int i = 0; i <= min(up, 1); i ++ ) //最多只能填到1
    {
        if (i == 1 && cnt == k) break ; //k个用完了，退出
        int l = limit & (i == up); // limit的转移
        res += dp(p - 1, cnt + (i == 1), l); // 统计子节点送上来的信息
    }

    return v = res; // 返回+记忆化
}

完整代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 35;
int f[N][N], k, b, l, r;
int a[N << 2], al;

int dp(int p, int cnt, int limit) 
{
    int &v = f[p][cnt];

    if (!p) return cnt == k;
    if (!limit && ~v) return v;

    int up = limit ? a[p] : b - 1, res = 0;

    for (int i = 0; i <= min(up, 1); i ++ ) 
    {
        if (i == 1 && cnt == k) break ;
        int l = limit & (i == up);
        res += dp(p - 1, cnt + (i == 1), l);
    }

    return v = res;
}

int calc(int x) 
{
    len = 0;
    memset(f, -1, sizeof f);
    while (x) a[ ++ len] = x % b, x /= b;
    return dp(len, 0, 1);
}

int main() 
{
    scanf("%d%d%d%d", &l, &r, &k, &b);
    printf("%d
", calc(r) - calc(l - 1));
    return 0;
}