数位 dp

泛化

友情提示，泛化中有一些内容未经实践证实，请谨慎阅读，笔者会尽力验证的

这类问题通常具有明显的提示性质。

比如限制是两个相邻数位之间要满足一些条件，或者说数位之和要满足什么条件之类的。

一般有两种考虑方式，一种是从低到高，一种是从高到低，这个需要具体问题具体分析。

通常还不止有数位的限制，还有一些额外的限制：

• 大小关系，比如要求填出来的数满足形如 \(a < b\) 的限制，问方案数
  • 这个通常是考虑从高到低填，这样子如果某一位已经满足了条件了，接下来的所有位都随便填了（这里不考虑其它的限制），通常也会在状态里加上，强制前面的位都已经满足条件的限制。
  • 当然从低到高也能做，每次只需要记录已经填好的 \(a\) 的后缀和 \(b\) 的后缀的大小关系，最后答案取满足条件的就行。
  • 如果扩展一下，\(l \le a_i \le r\) 的限制呢？
  • 这个也是好做的，如果是从高到底就只需要记录三种状态：高位和 \(l, r\) 相同，或者之前已经满足了限制，现在随便填。
  • 如果是从低到高就要多记录两个后缀的大小关系。
  • 不过一种看起来比较好理解的方式是，可以直接把这个条件转化成两个 \(a < b\) 型的限制，考虑差分一下就能得到答案了。
• 加法限制：可能是填一些数，然后满足一些条件且和要小于等于 \(m\)。
  • 一般都是从低到高考虑，记录一下进了多少次位，比如说设 \(dp(i, j)\) 表示考虑低 \(i\) 位，第 \(i\) 位向前进了 \(j\) 的位的答案。
  • 当然也可以从高到低，状态就需要钦定后面进了多少位，比如说设 \(dp(i, j)\) 表示考虑高 \(i\) 位，钦定第 \(i\) 位被低位进了 \(j\) 的位的答案。
• 位运算限制: 比如说异或什么之类的位运算。
  • 位运算都是不进位的，所以说从低到高或者从高到低都没啥影响。
  • 反正也是套路的考虑每一位就行了。

提示，本人不写记忆化搜索，感觉不好描述限制。

例题

光说不练没用，上几个题来看看。

[SCOI2009] windy 数

你有两个数 \([l, r]\)，你需要计算有多少个 \(a\) 满足 \(l \le a \le r\)。

并且 \(a\) 为不含前导零且相邻两位差至少为 \(2\) 的数。

\(l, r \le 2e9\)。

显然区间限制应当差分转化为普通的 \(< r\) 限制。

不含前导零的意思是，0721 和 721 应当被视作一个数。

有一定概率和正常人设计出来的状态不一样，没关系，能过就行。

这里是有比较大小的限制，所以我们从高到低地考虑填数，等于就直接在填数的时候注意一下就好。

考虑 \(dp(i, j)\) 表示从高到低第 \(i\) 位，这一位填了 \(j\) 的方案数。

发现大小关系没有记录，我们发现只需要记录之前在某个高位是否已经满足了限制就行，这个多记一维 \(0/1\) 即可。

然后发现前导零没法处理，我们不妨再加一维 \(0/1\) 表示之前是否填过一个不为 \(0\) 的数。

也就是设 \(dp(i,j,g(0/1),z(0/1))\)，表示考虑高 \(i\) 位，第 \(i\) 位填了 \(j\)，且之前是否满足过限制，是否填过一个不为零的数。

考虑转移，需要一定的分讨，略烦人，不过也不算那么烦人。

首先每一位的枚举范围是 \([0, r_i]\) 这个没的扯，然后为了方便，处理 \(r\) 的时候我们使得它没有前导 \(0\)。

然后考虑转移。

假设之前已经有位置满足了小于的条件，也就是 \(g = 1\)。

那么分两种情况，一种是之前已经填过了不为 \(0\) 的数，也就是从 \(dp(i - 1, .., 1, 1)\) 转移过来，此时这一位填什么都行。

一种是之前全部填的是 \(0\)，因为我们的 \(r\) 是没有前导零的，所以此时一定有 \(g = 1\)，从 \(dp(i - 1, 0, 1, 0)\) 转移过来，考虑一下当前位填不填 \(0\) 就行。

如果不是 \(0\)，那么就说明这里真正开始填数了，\(dp(i, .., 1, 1)\) 应该设为 \(1\)，因为之前都是 \(0\) 嘛。

不然就只能转移到 \(dp(i, 0, 1, 0)\)。

然后考虑之前并没有满足小于的条件，也就是全部都等于 \(r\)，因为没有前导零所以我们不用考虑 \(z = 0\) 的情况。

考虑当前位的取值应该是什么：

1. \(r_i\)，继续卡满上界，显然由于限制只能从 \(dp(i - 1, r_i, 0, 1)\) 转移到 \(dp(i, r_i, 0, 1)\)。
2. \(< r_i\)，那么说明这一位就满足了限制，转移到 \(dp(i, .., 1, 1)\) 就行，即使这一位填的是 \(0\) 也不需要额外讨论，因为 \(r\) 没有前导零，在之前都等于 \(r\) 的前提下一定存在一个不为 \(0\) 的数。

于是就做完了！

但是你会伤心的发现，直接按照我们以上的思路，枚举当前位状态，再考虑上一位，是非常难实现的！

所以对于数位 dp，我们通常都是考虑，枚举上一位的状态 \(dp(i - 1, j, g, z)\)，然后枚举当前位选 \(k\)，根据 \(j, g, z, k\) 确定应当转移到哪一个状态。

那么这样的话，实现就简单了，我们只需要看看，上一位的的限制是否满足，来确定 \(k\) 的枚举范围，并判断是否有 \(|j - k| \ge 2\) 或者 \(z = 0\)（这就是之前全部为 \(0\)，这一位选什么都行）。

然后转移的时候看一下是不是满足了限制，是不是没有前导零就行了。

当然，按照这种方式思考能减少分类讨论数，是更为推荐的做法。

Code

// author : black_trees

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

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 12;

int n;
int dp[si][si][2][2];
int solve(int val) {
    if(!val) return 0;

    std::vector<int> v;
    while(val) v.push_back(val % 10), val /= 10;
    n = (int)v.size(), v.push_back(-1), reverse(v.begin(), v.end());

    memset(dp, 0, sizeof dp);
    for(int i = 0; i <= v[1]; ++i) 
        dp[1][i][i < v[1]][i != 0] = 1;
    for(int i = 1; i < n; ++i)
        for(int j = 0; j <= 9; ++j)
            for(int g = 0; g <= 1; ++g)
                for(int z = 0; z <= 1; ++z)
                    for(int k = 0; k <= (g ? 9 : v[i + 1]); ++k)
                        if(abs(j - k) >= 2 || !z)
                            dp[i + 1][k][g | (k < v[i + 1])][z | (k != 0)] += dp[i][j][g][z];
    int ans = 0;
    for(int i = 0; i <= 9; ++i)
        ans += dp[n][i][1][1] + dp[n][i][0][1];
    return ans;
} 

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    int l, r;
    cin >> l >> r;
    // cout << solve(r) << endl;
    // cout << solve(l - 1) << endl;
    cout << solve(r) - solve(l - 1) << endl;

    return 0;
}

Loj3215「PA 2019」Muzyka pop

给一个长度为 \(n\) 的序列 \(v\) 和一个数 \(m\)。

构造一个 \(a\) 使得 \(0 \le a_1 < a_2 < \dots < a_n \le m\)，最大化 \(\sum\limits_{i = 1}^{n}\text{popcnt}(a_i)v_i\)，求最大值。

\(1\le n \le 200, m \le 10^{18}\)

多个形如 \(a < b\) 的限制不太好处理，但是肯定是从高位开始看，不过这里的 popcnt 明示我们拆成二进制考虑。

不妨考虑二进制下，这些 \(a < b\) 的限制是什么样的，显然，这个序列的最高位应当是 \(00000\dots 0001111\dots 1111\) 的形式。

并且分下去之后的第二层，每一侧内也应该是这样的。

所以这是，形如：

000 00|111 11 (高位)
000|11|000|11 (次高位)
..............

的一系列数。

于是这就变成了一个个子问题，我们可以对每一层的做区间 dp，枚举一下分界点，然后把答案合并上来。

所以实际上我们是从低位开始填，每次填高位，还需要考虑和 \(m\) 的关系，如果 \(m\) 的这一位是 \(0\)，那么都只能填 0 了，相当于是你把 \(m\) 放在最右边，和整个数列一起比较。

虽然是从低位，但是只要我们区间 dp 的时候遵守左边都是 0 右边都是 1 的原则，就可以满足数列中的限制。

那么设 \(dp(l, r, k)\) 表示考虑区间 \([l,r]\)，只填低 \(k\) 位的答案。

不难得到转移：

\[ dp(l, r, k) = \max\limits_{i = l - 1}^{r - 1}(dp(l, i, k - 1) + dp(i + 1, r, k - 1) + \sum\limits_{j = i + 1}^rv_i) \\ \]

然后你发现 \(m\) 的大小限制还没满足，所以还需要设一维表示当前填的高位是不是存在和 \(m\) 相等的数，如果有且这一位 \(m\) 是零，那么就不会有贡献。

代码实现是简单的。

Code

// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'
#define int long long

using namespace std;
using i64 = long long;

const int si = 2e2 + 10;

int n, m, a[si];
int dp[65][si][si][2];

signed main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n >> m, a[0] = 0;    
    for(int i = 1; i <= n; ++i)
        cin >> a[i], a[i] += a[i - 1];

    memset(dp, -0x3f, sizeof dp);

    for(int i = 1; i <= n; i++)
        dp[0][i][i][0] = dp[0][i][i][1] = 0;

    for(int i = 0; i < 64; i++)
        for(int j = 1; j <= n + 1; j++)
            for(int k = 0; k < 2; k++)
                dp[i][j][j - 1][k] = 0;
    for(int i = 1; i < 64; i++)
        for(int l = 1; l <= n; l++)
            for(int r = l; r <= n; r++)
                for(int j = 0; j < 2; j++)
                    if(!(m & 1ll << i - 1) && j)
                        dp[i][l][r][j] = dp[i - 1][l][r][j];
                    else for(int k = l - 1; k <= r; k++)
                        dp[i][l][r][j] = max(dp[i][l][r][j], dp[i - 1][l][k][0] + dp[i - 1][k + 1][r][j] + a[r] - a[k]);

    cout << dp[63][1][n][1] << endl;
    return 0;
}

CF1670F Jee, You See?

之前 cf 做过，但是没想清楚。

给定 \(n, l, r, z\)，问有多少个长度为 \(n\) 的序列 \(a\) 使得

\(\sum a \in [l, r]\)， 且 \(\bigoplus\limits_i a_i = z\)。

\(n \le 1000, 1\le l, r, z \le 10^{18}\)。

明摆着是数位 dp 啊！一个加法限制一个异或限制，而且是数列。

因为会有进位所以我们从低位开始考虑，不妨前缀和一下变成算 \(\sum a \le r\)，的答案

因为有异或所以应该在二进制下面考虑。

首先考虑异或这个限制怎么弄，显然它决定了每一个位当中能有的 \(1\) 的个数。

不妨考虑设 \(dp(i)\) 表示考虑低 \(i\) 位，使得 \(a\) 的异或低 \(i\) 位和 \(z\) 低 \(i\) 位相同的方案数。

因为异或是不进位加法，所以我们考虑每一位的奇偶性就行，你可以发现其实就是一堆组合数加起来，我猜应该是能化简的，不过我懒得算了。

然后我们考虑 \(\le r\) 这个限制怎么弄，因为这里有加法，所以我们要考虑进位。

然后我们还需要保证大小关系，这个怎么做，好像可以考虑记录后缀的大小关系，换句话说设 \(dp(i, j, 0/1)\) 表示考虑低 \(i\) 位，第 \(i\) 位向前进了 \(j\) 次，后缀 \(i\) 是否小于等于后缀 \(r[i..n]\)。

于是转移就是，我们考虑枚举下一位填了多少个 \(1\) 进去，然后把这里的进位加上，转移到 \(dp(i + 1, j^\prime, 0/1)\)，后面的限制就看一下新一位是不是满足了，当然还需要注意 \(z\) 的限制。

最后答案应该是 \(dp(n, 0, 1)\)，因为要满足小于等于 \(r\) 的条件。

思考一下可以发现这也能覆盖完整个状态空间。

但是感觉这个巨大麻烦啊！至少我不是很想写。

那么换成从高到低呢？大小关系就可以不用关心了，直接钦定前面一定要满足条件就行，但是进位怎么办？我们就考虑钦定进了多少位。

换句话说，可以注意到 \(r\) 的限制实际上是说，假设每一位只能填一个 \(1\)，那么哪些位可以填一个，本质是钦定下一位至多进 \(j\) 位。

有可能我们选择不填，那么剩下的这些就可以留给后面的状态用。

所以不妨设 \(dp(i, j)\) 表示考虑高 \(i\) 位，当前位剩了 \(j\) 个 \(1\) 没填可以下放到低位。

于是低一位可以填的 \(1\) 就 \(2j + r[i + 1]\) 个 \(1\) 了。

这样 dp 就非常方便了！枚举这一位有多少个没填，枚举下一位填多少，转移即可。

Code

这东西 TL 了，比较忙没时间看，但是大概就是这个意思。

const int si = 2e3 + 10;

#define int long long
int n, l, r, z;
modint fact[si], dp[65][si];
modint C(int n, int m) {
    if(n < m || m < 0) return 0;
    return fact[n] / (fact[n - m] * fact[m]);
}
modint F(int val) {
    for(int i = 0; i < 65; ++i)
        for(int j = 0; j < si; ++j)
            dp[i][j] = 0;
    dp[64][0] = 1;
    for(int i = 63; i >= 0; --i) {
        for(int j = 0; j <= n; ++j) {
            int res = j * 2 + (val >> i & 1);
            for(int k = z >> i & 1; k <= min(n, res); k += 2)
                dp[i][min(res - k, n)] += dp[i + 1][j] * C(n, k);
        }
    }
    modint ans = 0;
    for(int i = 0; i <= n; ++i)
        ans += dp[0][i];
    return ans;
}

CF1290F Making Shapes

话说这题是 *3500 啊（放在这里当例题合适吗

---

最后更新: August 5, 2023