Piling Papers (USACO Gold 2023 February)

这个题初看还是比较复杂的，应该能看出是一个DP题，但是要数的是一个区间取值内的方案数，这个怎样构造状态是一个有难度的事情。测试点条件中间有一个 $A=B$ 的提示，所以我们可以从不是区间，而是确定的值情况开始进行思考。

如果我们限定只有一个固定的取值 $A$ ，那么DP状态应该就相对直观，比如我们确定从一个位置 $l$ 开始取纸（有了对应 $l$ 的所有结果后， $N$ 倍复杂度就可以得到所有结果，以执行需要的查询），那么 $\text{dp}[i][j][k]$ 定义为：前 $i$ 张纸，正好匹配 $A[j...j+k-1]$ 的方案数。因为每次处理一个数字时，三种选择分别是丢掉、放到现有数字末尾，或者前面。所以基于这个三动作可以写出 $\mathcal{O}(1)$ 的状态转换：

\text{dp}[i][j][k] = \text{dp}[i-1][j][k] \\ \text{if} (a[s+i-1]==A[j+k-1]) \text{dp}[i][j][k] += \text{dp}[i-1][j][k-1] \\ \text{if} (a[s+i-1]==A[j]) \text{dp}[i][j][k] += \text{dp}[i-1][j+1][k-1] \\

通过这个DP，可以把测试点4-5做出来。

接着考虑怎么把这个扩展到 $[A,B]$ 区间。我做此题的时候，想直接通过将区间转化成多个模式的方法来完成（比如 $[13,75]$ 对应 $1[3-9], [2-6]*, 7[0-5]$ 三个模式，这个事实证明会TLE掉，所以需要另想办法。

正解还是比较巧妙的，关键一步是想到区间方案数，可以转换成 $[0,A-1], [0-B]$ 这两个“小于”条件的方案数之差，而且这种“小于”的方案数，可以用类似等于的DP来求出来。

定义 $\text{dp}[i][j][k][c]$ ：前 $i$ 张纸，形成 $k$ 位数字，而且小于 $A[j...j+k-1]$ ( $c=0$ ), 等于 $A[j...j+k-1]$ ( $c=1$ ), 或者大于 $A[j...j+k-1]$ ( $c=2$ )的方案数。

DP状态转移还是可以 $\mathcal{O}(1)$ 完成，类似上面等于情况，但更复杂一些。分成 $c=0,1,2$ 三种情况，例如要求 $c=0$ 的方案数， $\text{dp}[i][j][k][0]$ 是下面五个之和：

前 $i-1$ 张纸，生成比 $X$ 中第 $j$ 位开始的 $k$ 位更小的 $k$ 位数的方案数， $\text{dp}[i-1][j][k][0]$ 。就是把新的第 $i$ 张纸直接丢弃。
前 $i-1$ 张纸，生成比 $X$ 中第 $j$ 位开始的 $k-1$ 位更小的 $k-1$ 位数，再跟上任意数（第 $i$ 张纸上的数）。这是一种追加一位的方式。
前 $i-1$ 张纸，生成和 $X$ 中第 $j$ 位开始的 $k-1$ 位相等的数，再跟上比 $X$ 中对应位置数字更小的一位数（第 $i$ 张纸上的数）。这是另一种追加一位的方式。
类似的，还有在前面插入的方式，第 $i$ 张纸比 $X$ 对应位小，再加上前 $i-1$ 张纸生成的任意 $k-1$ 位数。
最后一种前面插入的方式，是 $i$ 张纸和 $X$ 对应位相等，再加上前 $i-1$ 张纸生成的比 $X$ 中对应位置小的 $k-1$ 位数。

完整逻辑看代码。得到所有DP状态后， $[0,X]$ 的方案数，就是是 $\text{dp}[i][0][d][0] + \text{dp}[i][0][d][1] + \sum_{j>0,c=0,1,2} \text{dp}[i][j][d-j][c]$ ，其中 $d$ 是 $X$ 的位数。最后求和项是位数小于 $d$ 位的数的方案数，也是满足条件的。

此题思维难度较大，DP状态转移也比较细节，实现了一些DP求数字区间方案数的办法，值得记下这次个方法。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n, Q;
ll A, B;
int a[305];
int dp[305][19][19][3];     // dp[i][j][k][c]: first i numbers, covering digits [j, j+k-1], c=0 (less than A[j,j+k), 1 equal, 2 larger
int ans[305][305];          // result starting from a[i], len j
const int M = 1e9 + 7;
 
int clog10(ll x) {
    int res = 0;
    for (; x; x /= 10, res++);
    return res;
}
 
vector<int> solve(int s, ll x) {    // solve for starting position s, less than or equal to x
    vector<int> r(n-s+1, 0);
    int d = clog10(x);
    vector<int> X;
    for (; x; x /= 10)
        X.push_back(x % 10);
    reverse(X.begin(), X.end());            // most significant first
    for (int i = 0; i <= n-s; i++) {        // length
        for (int j = 0; j < d; j++) {       // start position in X
            dp[i][j][0][1] = dp[i][j+1][0][1] = 1;
            for (int k = 1; j+k <= d && k <= i; k++) {
                int p = a[s+i-1];
                // < X[j,j+k-1]
                dp[i][j][k][0] = dp[i-1][j][k][0];                                              // drop p=a[s+i-1]
                dp[i][j][k][0] = (dp[i][j][k][0] + dp[i-1][j][k-1][0]) % M;                     // append 
                if (p < X[j+k-1]) dp[i][j][k][0] = (dp[i][j][k][0] + dp[i-1][j][k-1][1]) % M;   // append
                if (p == X[j]) dp[i][j][k][0] = (dp[i][j][k][0] + dp[i-1][j+1][k-1][0]) % M;    // prepend
                if (p < X[j]) dp[i][j][k][0] = ((ll)dp[i][j][k][0] + dp[i-1][j+1][k-1][0] 
                                    + dp[i-1][j+1][k-1][1] + dp[i-1][j+1][k-1][2]) % M;         // prepend
                // =
                dp[i][j][k][1] = dp[i-1][j][k][1];                                              // drop
                if (p == X[j+k-1]) dp[i][j][k][1] = (dp[i][j][k][1] + dp[i-1][j][k-1][1]) % M;  // append
                if (p == X[j]) dp[i][j][k][1] = (dp[i][j][k][1] + dp[i-1][j+1][k-1][1]) % M;    // prepend                
                // >
                dp[i][j][k][2] = dp[i-1][j][k][2];                                              // drop
                dp[i][j][k][2] = (dp[i][j][k][2] + dp[i-1][j][k-1][2]) % M;                     // append
                if (p > X[j+k-1]) dp[i][j][k][2] = (dp[i][j][k][2] + dp[i-1][j][k-1][1]) % M;   // append
                if (p == X[j]) dp[i][j][k][2] = (dp[i][j][k][2] + dp[i-1][j+1][k-1][2]) % M;    // prepend
                if (p > X[j]) dp[i][j][k][2] = ((ll)dp[i][j][k][2] + dp[i-1][j+1][k-1][0] 
                            + dp[i-1][j+1][k-1][1] + dp[i-1][j+1][k-1][2]) % M;                 // prepend
            }
        }
        r[i] = ((ll)r[i] + dp[i][0][d][0] + dp[i][0][d][1]) % M;
        for (int j = 1; j < d; j++)
            for (int c = 0; c < 3; c++)
                r[i] = (r[i] + dp[i][j][d-j][c]) % M;
    }
    return r;
}
 
int main() {
    scanf("%d %lld %lld", &n, &A, &B);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (int s = 0; s < n; s++) {       // start position
        vector<int> ra = solve(s, A-1);
        vector<int> rb = solve(s, B);
        for (int i = 0; i <= n-s; i++)
            ans[s][i] = (rb[i] + M - ra[i]) % M;
    }
    scanf("%d", &Q);
    for (int q = 0; q < Q; q++) {
        int i,j;
        scanf("%d %d", &i, &j);
        printf("%d\n", ans[i-1][j-i+1]);
    }
    return 0;
}