数位dp

数位 dp

本质是记忆化搜索。

\(lim\) 为 \(1\)，表示当前位之前都是最大的数，当前位的大小受限制，不是 1~9，是 1~up。

\(zero\) 为 \(0\)，表示这一位之前为前导 0。

\(lim\) 的转移：lim && (i == up)。

\(zero\) 的转移：zero || i。

例题1

P2602 [ZJOI2010] 数字计数

给定 \(a\) 和 \(b\)，求在 \([a,b]\) 的所有整数中，\(0 \sim 9\) 各出现了几次。\(1 \leq a \leq b \leq 10^{12}\)。

思路：

从高位到低位枚举，对于每一位，当前位的答案 \(ans\) 初始为 0，然后枚举这一位数字的种类，用更新后的状态来处理答案累加。

当位数为 0 时说明处理完了，返回当前的答案。

处理的过程中开 \(dp\) 数组存储 dfs 时的状态，实现记忆化。

ll n, m, k;
ll num[20], len;
ll f[20][20][2][2];

ll dfs(ll x, ll lim, ll zero, ll sum, ll d)
{
    if(x == 0) return sum;
    ll ans = 0;
    if(f[x][sum][lim][zero] != -1) return f[x][sum][lim][zero];
    ll up = 9;
    if(lim) up = num[x];
    fr(i, 0, up)
    {
        ans += dfs(x-1, lim && (i == up), zero || i, sum + ((zero || i) && (i == d)), d);
    }

    return f[x][sum][lim][zero] = ans;
}

ll Calc(ll x, ll d)
{
    len = 0;
    while(x)
    {
        num[++len] = x % 10;
        x /= 10;
    }
    memset(f, -1, sizeof(f));
    return dfs(len, 1, 0, 0, d);
}

int main()
{
    ll l = re, r = re;
    fr(i, 0, 9)
        W(Calc(r, i) - Calc(l-1, i), ' ');
    return 0;
}   

例题2

https://codeforces.com/gym/101982/attachments

给定两个整数 \(k\) 和 \(b\)，\(1 \leq k \leq 1000\)，\(1 \leq b \leq 128\)。

求 \([0,2^b-1]\) 内的所有整数中，为 \(k\) 的倍数的数在二进制表示下 \(1\) 的数量的总和。答案对 \(1e9+9\) 取模。

思路：

以二进制按位考虑。发现对于任意一个二进制数，左移一位，\(1\) 的数量不会被改变。

开三个状态。\(x\) 为当前位数，\(num1\) 为当前 \(1\) 的个数，\(mod\) 为当前这个数除以 \(k\) 的余数。

对于每一位，枚举当前位是 \(0\) 还是 \(1\)，转移答案和余数，转移过程比较简单。

ll n, m, k, b;
ll f[130][130][1010];
ll Mo = 1e9 + 9;

ll dfs(ll x, ll num1, ll mod)
{
    if(x <= 0)
    {
        if(mod != 0) return 0;
        return num1;
    }

    if(f[x][num1][mod] != -1) return f[x][num1][mod];
    ll ans = 0;

    fr(i, 0, 1)
    {
        ans += dfs(x-1, num1 + i, (mod * 2 + i) % k);
        ans %= Mo;
    }
    
    f[x][num1][mod] = ans;
    return ans;
}

int main()
{
    k = re, b = re;
    memset(f, -1, sizeof(f));
    W(dfs(b, 0, 0), '\n');
    return 0;
}