最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

数位DP基础概念 指路：【数位DP基本概念+数位DP记忆化搜索】

题目描述

给定整数区间 $[l,r]$，求该区间内，数位上没有 $7$，且整个数字 不是 $7$ 的倍数 的数字的 平方和

分析

想了解 数位DP 基础概念的，可以看一下最上面我贴的链接，这里不会对 重复内容 进行额外讲解

这题如果只是求整数区间 $[l,r]$ 内满足要求的数的 个数，难度可以归为 简单

我们先想一下如何求解我说的这个 简单问题

毫无疑问是用 数位DP 来求解，那么搜索的过程中，需要记录的参数有：

1. 当前搜索的数的前 $pos$ 位模 $7$ 的余数 $val$
2. 当前搜索的数的前 $pos$ 位数位上的数字之和模 $7$ 的余数 $sum$

也就比 前5道数位DP 多了一个参数罢了

可惜就可惜在，本题要求的不是满足要求的 数字的个数，而是满足要求的 数字的平方和

我们还是先用 数位DP-记忆化搜索 求解问题的方式去思考，如何在求解的过程中 记录/合并信息

既然是 搜索，不妨先用 分治的思想，把 大问题集合 划分成多个 子问题集合，最后再进行 合并

假设 我们当前已经搜出了 pos-1 层的信息，现在向上 回溯，如何把该信息合并到 大集合 中呢？

考虑在 搜索 时，如何合并多条搜索分支 回溯 的 平方和信息

$$ \begin{align} \sum_i (\overline{aA_i})^2 &= \sum_i (a \times 10^{~p-1} + A_i)^2 \\\\ &= \sum_i \bigg((a \times 10^{~p-1})^2 + 2 \times (a \times 10^{~p-1}) \times (A_i) + A_i^2\bigg) \\\\ &= (\sum_i 1) \times (a \times 10^{~p-1})^2 + 2 \times (a \times 10^{~p-1}) \times \sum_i A_i + \sum_i A_i^2 \end{align} $$

根据上述 递推式 可知，我们枚举当前数位填 $a$ 以后下沉 搜索，然后 回溯时 需要传递的 信息 有:

1. 能接在 $a$ 以后的数字 $A_i$ 的个数 $\sum_i 1$
2. 能接在 $a$ 以后的数字 $A_i$ 的总和 $\sum_i A_i$
3. 能接在 $a$ 以后的数字 $A_i$ 的平方和 $\sum_i A_i^2$

于是我们可以把 记忆化搜索 的 属性值 开成 3维，分别记录这三个值： s0, s1, s2

回溯的时候，分别对这三个值进行合并即可

上述递推式给出了 s2 的合并， s1 的合并如下：

$$ \sum_i (\overline{aA_i}) = \sum_i (a\times 10^{~p-1} + A_i) = (\sum_i 1) \times (a\times 10^{~p-1}) + \sum_iA_i $$

s0 的合并就是直接个数相加即可

这题唯一一个 最不起眼的减法操作 在第一步 $calc(r) - calc(l - 1)$，这里也要 取模

就这里调了我半小时

Code

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

using namespace std;

typedef long long LL;

const int N = 20, MOD = 1e9 + 7;

LL T, l, r;
int a[N], al;
int pow10[N];

//f记录的是枚举到第pos位，数字模7余数为val，数位之和模7余数为sum
struct F
{
    LL s0, s1, s2;
    F(): s0(0ll), s1(0ll), s2(0ll){};//无参构造函数
    F(LL _0, LL _1, LL _2): s0(_0), s1(_1), s2(_2){};//含参构造函数
    void operator += (const F& t)//重载+=，之后合并信息的时候用到的
    {
        s2 = (s2 + t.s2) % MOD;
        s1 = (s1 + t.s1) % MOD;
        s0 = (s0 + t.s0) % MOD;
    }
}f[N][N][N];

//val记录搜索到第pos位上时，当前数字模7的余数
//sum记录搜索到第pos位上时，前几位数位上数字之和模7的余数
//op记录当前搜索是否贴着上界：1:= 0:<
F dp(int pos, int val, int sum, int op)
{
    if (!pos)   //递归搜索结束，如果此时符合要求，则加一计数
    {
        if (val && sum) return {1, 0, 0};
        else return {0, 0, 0};
    }
    //记忆化搜索
    if (!op && ~f[pos][val][sum].s0) return f[pos][val][sum];

    F res(0, 0, 0);//答案
    int maxx = op ? a[pos] : 9;//搜索上界

    for (int i = 0; i <= maxx; i ++ )//合并信息
    {
        if (i != 7)//题目中要求数位上不能出现7
        {
            //dfs到下一层
            F t = dp(pos - 1, (val * 10 + i) % 7, (sum + i) % 7, op && i == a[pos]);
            //为了方便看代码，这里用一个中间变量k来存储 a * 10^{p-1}
            LL k = (LL) i * pow10[pos - 1] % MOD;  //k = a * 10^{p-1}
            //二次幂和的合并
            t.s2 = (t.s2 + 2ll * k % MOD * t.s1 % MOD) % MOD;
            t.s2 = (t.s2 + k * k % MOD * t.s0 % MOD) % MOD;
            //一次幂和的合并
            t.s1 = (t.s1 + k * t.s0 % MOD) % MOD;
            //信息合并（用到之前重载的+=运算符
            res += t;
        }
    }
    return op ? res : f[pos][val][sum] = res;
}
LL calc(LL x)
{
    memset(f, -1, sizeof f); al = 0;        //初始化
    for ( ; x; x /= 10) a[ ++ al] = x % 10; //扣数位
    return dp(al, 0, 0, 1).s2;              //记忆化搜索
}
int main()
{
    //预处理10的幂次
    pow10[0] = 1;
    for (int i = 1; i < 20; i ++ )
    {
        pow10[i] = 10ll * pow10[i - 1] % MOD;
    }
    //solve
    cin >> T;
    while (T -- )
    {
        cin >> l >> r;
        //这里一个减法取模要注意（我调了一小时，没发现这里爆了
        cout << ((calc(r) - calc(l - 1)) % MOD + MOD) % MOD << endl;
    }
    return 0;
}