恨7不成妻

Acwing 算法提高课 数位dp

有史以来遇到过最变态的数位dp，算满了两张草稿纸

主要收获在于对于 非只计数状态 (如求所有数的和、平方和、立方和(三次往上就太过于复杂了))的处理:

本题要求的是所有数的平方和，接下来以处理所有数的一次和举例

就比如说我们要处理的是某某状态(我们暂且把它记作 i ),我们可以通过已知状态(我们暂且把它记作 i - 1 )计算.

倘若我们要维护的是数字的总和,则有如下(下列表达式中的j是i状态的首位数字)

$$f_1(i) = \sum_{k=1}^{t}\overline{jA_k}$$

t表示 i - 1 状态有多少个数

$$\iff f_1(i) = \sum_{k=1}^{t}10^{i - 1}j+A_k$$ $$= 10^{i-1}tj +\sum_{k=1}^{t}A_k$$

这里我们未知的量只有t,即状态i-1中数的个数,但是t不难维护

我们把这里的t记作f0(其实是状态 i-1 中所有数的'0'次方的和)以统一形式

则有

$$f_0(i) = \sum_{}f_0(i - 1)$$

把t替换成f0

$$f_1(i) = 10^{i - 1}jf_0(i - 1) + f_1(i - 1)$$

即可求出所有的数的一次和

相比之下本题所要求维护的平方和则更为复杂,我们把它的状态表示为f2(求每个数的二次方的和)，即

$$f2(i) = \sum_{k = 1}^{f_0(i-1)}(\overline{jAk})^2$$

$$= \sum_{k = 1}^{f_0(i - 1)}((10^{i-1}j + Ak) ^ 2)$$

$$= f_0(i-1)×(10^{i-1}j)^{2}+2×10^{i-1}j(\sum_{k = 1}^{f_0(i-1)}A_k)+\sum_{k = 1}^{f_0(i - 1)}A_k^2$$

$$= f_0(i-1)×(10^{i-1}j)^{2}+2×10^{i- 1}jf_1(i - 1)+f_2(i - 1)$$ 即使较为复杂,不难发现同样是由f0和f1这种相对易于维护的量去 表示

也就是说我们只需要在维护f2的同时去维护f0和f1,即可求解

而这也就是本题最大的难点：目标维护数的"平方和"

事实上本题的条件有三个,但这只能说是简单条件的堆砌

• 条件1与不要62类似
• 条件2和3对应数字游戏2

在上文的推导中我们使用了 i 和 i-1 以方便说明, 下面对状态 i 和 i-1 作具体表示
对应条件，我们用四个状态来进行维护

• i表示数字位数
• j表示首位的数字-
• a表示各数位个数之和(mod7)
• p表示该数(mod7)

这么设置状态的合理性在于i和j是数位dp常规状态,a和p对应了2和3的条件,条件1在数位dp过程中调整即可

那么即可对上文的状态进行具体表示 当前状态为 $$f(i, j, a, p)$$

则上一状态为

$$f(i - 1, k, get(j, a), get(10^{i-1}j, p))$$

状态转移get(x, y)函数手写,表示

$$x +get(x,y) \equiv y\ (mod\ 7)$$

具体过程和证明在我的数字游戏二中已经有说了

除去这些,有句话说的很好"少生儿子多模P"

2024 1 6 Wa 0/2 越界了

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

using namespace std;

typedef long long LL;
const int N = 20, P = 1e9 + 7;

int f0[N][15][10][10], f1[N][15][10][10], f2[N][15][10][10];
int pow10[0];

int get(int x, int y){
    return (y - x % 7 + 7) % 7;
}

void init(){
    pow10[0] = 1;
    for(int i = 1; i < N; i ++)
        pow10[i] = (LL)pow10[i - 1] * 10 % P;
    for(int i = 0; i <= 9; i ++){//len == 1初始化
        if(i == 7)continue;
        f0[1][i][i % 7][i % 7] = 1;
        f1[1][i][i % 7][i % 7] = i;
        f2[1][i][i % 7][i % 7] = i * i;
    }
    for(int i = 2; i <= 19; i ++){
        for(int j = 0; j <= 9; j ++){
            if(j == 7)continue;
            for(int a = 0; a <= 6; a ++){
                for(int p = 0; p <= 6; p ++){
                    for(int k = 0; k <= 9; k ++){
                        if(k == 7)continue;

                        int t = f0[i - 1][k][get(j, a)][get(j * pow10[i - 1], p)];
                        int sig1 = f1[i - 1][k][get(j, a)][get(j * pow10[i - 1], p)];
                        int sig2 = f2[i - 1][k][get(j, a)][get(j * pow10[i - 1], p)];

                        f0[i][j][a][p] += t;
                        f1[i][j][a][p] += t * j * pow10[i - 1] + sig1;
                        f2[i][j][a][p] += ((LL)(j * pow10[i - 1] % P) * (j * pow10[i - 1] % P) % P * t
                                        + (LL)2 * j * pow10[i - 1] * sig1 % P
                                        + sig2) % P;
                        f0[i][j][a][p] %= P;
                        f1[i][j][a][p] %= P;
                        f2[i][j][a][p] %= P;
                    }
                }
            }
        }
    }
}

int dp(LL n){
    LL back_n = n;
    // printf("n : %lld\n", n);
    if(n == 0)return 0;

    vector<int> nums;
    while(n)nums.push_back(n % 10), n /= 10;

    // printf("size : %d\n", nums.size());

    int res = 0, lasa = 0, lasp = 0;
    LL las = 0;
    for(int i = nums.size() - 1; i >= 0; i --){
        int x = nums[i];

        // printf("i : %d x : %d \n",i,  x);

        for(int j = 0; j < x; j ++){
            if(j == 7)continue;
            for(int a = 1; a <= 6; a ++){
                for(int p = 1; p <= 6; p ++){
                    int t = f0[i + 1][j][get(lasa, a)][get(lasp, p)];
                    int sig1 = f1[i + 1][j][get(lasa, a)][get(lasp, p)];
                    int sig2 = f2[i + 1][j][get(lasa, a)][get(lasp, p)];
                    res = (res
                              + ((LL)(las * pow10[i + 1] % P) * (las * pow10[i + 1] % P) % P * t
                              + (LL)2 * j * pow10[i - 1] * sig1 % P
                              + sig2) % P
                          ) % P;
                }
            }
        }

        if(!i && x != 7 && (lasa + x) % 7 != 0 && (lasp + x) % 7 != 0){
            // printf("last : %lld\n", (back_n % P) * (back_n % P));
            res = (res + (back_n % P) * (back_n % P) % P) % P;
        }

        if(x != 7){
            lasa = (lasa + x) % 7;
            lasp = (lasp + x * pow10[i]) % 7;
            las = las * 10 + x;
        }
        else break;

        // printf("lasa : %d lasp : %d res : %d\n", lasa, lasp, res);
    }

    return res;
}

int main(){
    init();

    int T;
    scanf("%d", &T);

    while(T --){
        LL l, r;
        scanf("%lld%lld", &l, &r);
        printf("%lld\n",dp(r) - dp(l - 1));
    }

    return 0;
}