AcWing 1086 恨7不是妻(Acwing 1086 hate 7 is not a wife)

题目传送门

一、思路分析

这题先写搜索,再加上记忆化, 难点在于数据范围很大, 处理不好的话很容易超过\(LL\)范围出错,所以记得到处取 \(MOD\)。

以一个\(6\)位数举例:
假设对于一个\(6\)位数 \(axxxxx\)
我们想知道以\(a\)开头的满足要求的\(6\)位数的平方和,(将抽象问题具体化,方便我们理解,理解清楚后,再将具体问题抽象化,方便推导

我们不妨设\(a\)右侧的\(5\)位形成的数字为\(b\)
(给一个例子,方便理解\(a\),\(b\)是啥, 比如对于一个\(6\)位数\(213456\),\(a\)就是\(2\), \(b\)就是\(13456\)
形成的平方为 \((a * 10^5 + b)^2 = a^2 * 10^5 * 10^5 + b^2 + 2ab* 10^5\)

那么对于右侧不同的数字\(b\), 比如\(b_1\)
形成的平方\(= a^2 * 10^5 * 10^5 + b_1^2 + 2ab_1* 10^5\)

假设\(ab\),\(ab_1\),\(ab_2\),\(ab_3\), … 都是满足要求的数字
那么题目要求的平方和\(=(ab)^2 + (ab_1)^2+ (ab_2)^2+ … = (a^2 * 10^5 * 10^5) * cnt + 2 * a * 10^5 * (b+b_1+b_2+…) + (b^2+b_1^2+b_2^2…)\)
cnt为满足要求的数字个数, 10的多少次方可以根据数字长度预处理出来。

那么我们可以看出来
只要我们能获取满足要求的数字个数, 以及右侧所有b之和, 以及所有b^2之和 就能求出答案

所以我们dp数组类型定义成一个结构体,分别存长度,右侧数字之和, 右侧数字平方和这3项即可,
再就是状态划分了,长度缩短即可划分

二、实现代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;//要求对结果进行模1e9+7
const int N = 20;      //L,R是18位的十进制数,数位最长开到20,肯定够了
const int M = 10;      //因为需要记录%7的状态,所以开到10就够了
int a[N];              //数位分离的每一位结果
LL pw[N];              //(10的i次幂)%MOD

struct Node {
    LL cnt;    //符合要求的数字个数
    LL sum;    //每个数位数字和%7的值
    LL sq_sum; //平方和%MOD的值
} dp[N][M][M];
//dp[i][j][k]表示从i位开始往后,最左侧到i位每位的数之和%7=j, 最左侧到i位的数%7=k
/**
 比如:原数 1234567
      pos 6543210
      假如现在pos=3,那么dp[i=3][j=10%7=3][k=1234%7]=统计好结构体Node (Node里有三个属性:)
 */

//当前在第pos位,最高位到第pos位每位数字之和(%7)为sum,整个数字(%7)为num,limit表示是否贴合上界
Node dfs(int pos, int sum, int num, bool limit) {
    //数字已填完,根据题目要求,若sum和num都不为0(不能被7整除),则贡献值++
    if (pos == -1) return (Node) {sum && num, 0, 0};
    //记忆化,如果不贴合上界(!lim),直接放回记录过的答案
    if (!limit && ~dp[pos][sum][num].cnt) return dp[pos][sum][num];
    //第pos位最大能填的数
    int up = limit ? a[pos] : 9;
    //声明一个结果变量,用来装本轮的结果值
    Node res = {0, 0, 0};
    for (int i = 0; i <= up; i++)   //枚举第pos位填的数
        if (i != 7) {   //题目要求,数位上没有7
            Node t = dfs(pos - 1, (sum + i) % 7, (num * 10 + i) % 7, limit && i == up);
            //k:当前层的基值
            LL k = i * pw[pos];
            res.cnt = (res.cnt + t.cnt % MOD) % MOD; //统计与7无关数出现次数
            res.sum = (t.cnt * k % MOD + t.sum % MOD + res.sum) % MOD;
            res.sq_sum = (res.sq_sum + t.cnt * k % MOD * k % MOD + t.sq_sum + 2 * t.sum % MOD * k % MOD) % MOD;
        }
    return limit ? res : dp[pos][sum][num] = res;
}


LL calc(LL x) {
    int pos = 0;
    memset(dp, -1, sizeof dp);
    while (x)a[pos++] = x % 10, x /= 10;
    return dfs(pos - 1, 0, 0, 1).sq_sum;
}

int main() {
    int T;
    cin >> T;
    //预处理(10的幂)%MOD
    pw[0] = 1;
    for (int i = 1; i < N; i++) pw[i] = pw[i - 1] * 10 % MOD;

    while (T--) {
        LL l, r;
        cin >> l >> r;
        printf("%lld\n", (calc(r) - calc(l - 1) + MOD) % MOD);
    }
    return 0;
}
————————

Title portal

1、 Train of thought analysis

The difficulty of this problem is that the data range is very large. If it is not handled well, it is easy to make mistakes beyond the range of \ (ll \), so remember to take \ (MOD \).

Take one \ (6 \) digit as an example:
Suppose for a \ (6 \) digit \ (axxxxx \)
We want to know the square sum of the digits of \ (6 \) beginning with \ (a \) that meet the requirements (< strong > concretize the abstract problem for our understanding. After understanding it clearly, we can abstract the specific problem for the derivation of < / strong >)

We might as well set the number formed by the \ (5 \) bit on the right side of \ (a \) as \ (B \)
(give an example to understand what \ (a \) and \ (B \) are. For example, for a \ (6 \) digit \ (213456 \), \ (a \) is \ (2 \), \ (B \) is \ (13456 \)
The square formed is \ ((a * 10 ^ 5 + b) ^ 2 = a ^ 2 * 10 ^ 5 * 10 ^ 5 + B ^ 2 + 2Ab * 10 ^ 5 \)

Then, for different numbers \ (B \) on the right, such as \ (b_1 \)
Square formed \ (= a ^ 2 * 10 ^ 5 * 10 ^ 5 + b_1 ^ 2 + 2ab_1 * 10 ^ 5 \)

Assume that \ (AB \), \ (ab_1 \), \ (ab_2 \), \ (ab_3 \),… Are all numbers that meet the requirements
Then the sum of squares required by the topic \ (= (AB) ^ 2 + (ab_1) ^ 2 + (ab_2) ^ 2 +… = (a ^ 2 * 10 ^ 5 * 10 ^ 5) * CNT + 2 * a * 10 ^ 5 * (B + b_1 + b_2 +…) + (b ^ 2 + b_1 ^ 2 + b_2 ^ 2…) \)
CNT in order to meet the required number of numbers, the power of 10 can be preprocessed according to the number length.

Then we can see
As long as we can get the number of numbers that meet the requirements, the sum of all B on the right and the sum of all B ^ 2, we can find the answer

Therefore, we define the DP array type as a structure, which can store the length, the sum of the numbers on the right, and the sum of the squares of the numbers on the right,
Then there is the state division, which can be divided if the length is shortened

2、 Implementation code

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;//要求对结果进行模1e9+7
const int N = 20;      //L,R是18位的十进制数,数位最长开到20,肯定够了
const int M = 10;      //因为需要记录%7的状态,所以开到10就够了
int a[N];              //数位分离的每一位结果
LL pw[N];              //(10的i次幂)%MOD

struct Node {
    LL cnt;    //符合要求的数字个数
    LL sum;    //每个数位数字和%7的值
    LL sq_sum; //平方和%MOD的值
} dp[N][M][M];
//dp[i][j][k]表示从i位开始往后,最左侧到i位每位的数之和%7=j, 最左侧到i位的数%7=k
/**
 比如:原数 1234567
      pos 6543210
      假如现在pos=3,那么dp[i=3][j=10%7=3][k=1234%7]=统计好结构体Node (Node里有三个属性:)
 */

//当前在第pos位,最高位到第pos位每位数字之和(%7)为sum,整个数字(%7)为num,limit表示是否贴合上界
Node dfs(int pos, int sum, int num, bool limit) {
    //数字已填完,根据题目要求,若sum和num都不为0(不能被7整除),则贡献值++
    if (pos == -1) return (Node) {sum && num, 0, 0};
    //记忆化,如果不贴合上界(!lim),直接放回记录过的答案
    if (!limit && ~dp[pos][sum][num].cnt) return dp[pos][sum][num];
    //第pos位最大能填的数
    int up = limit ? a[pos] : 9;
    //声明一个结果变量,用来装本轮的结果值
    Node res = {0, 0, 0};
    for (int i = 0; i <= up; i++)   //枚举第pos位填的数
        if (i != 7) {   //题目要求,数位上没有7
            Node t = dfs(pos - 1, (sum + i) % 7, (num * 10 + i) % 7, limit && i == up);
            //k:当前层的基值
            LL k = i * pw[pos];
            res.cnt = (res.cnt + t.cnt % MOD) % MOD; //统计与7无关数出现次数
            res.sum = (t.cnt * k % MOD + t.sum % MOD + res.sum) % MOD;
            res.sq_sum = (res.sq_sum + t.cnt * k % MOD * k % MOD + t.sq_sum + 2 * t.sum % MOD * k % MOD) % MOD;
        }
    return limit ? res : dp[pos][sum][num] = res;
}


LL calc(LL x) {
    int pos = 0;
    memset(dp, -1, sizeof dp);
    while (x)a[pos++] = x % 10, x /= 10;
    return dfs(pos - 1, 0, 0, 1).sq_sum;
}

int main() {
    int T;
    cin >> T;
    //预处理(10的幂)%MOD
    pw[0] = 1;
    for (int i = 1; i < N; i++) pw[i] = pw[i - 1] * 10 % MOD;

    while (T--) {
        LL l, r;
        cin >> l >> r;
        printf("%lld\n", (calc(r) - calc(l - 1) + MOD) % MOD);
    }
    return 0;
}