算法1
(记忆化搜索)
时间复杂度 (不大)
这题先写搜索,再加上记忆化, 难点在于数据范围很大, 处理不好的话很容易超过ll范围出错,所以记得到处取 MOD,
思路:
以一个6位数举例,
假设对于一个6位数 axxxxxx
我们想知道以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, 比如b1
形成的平方= a^2 * 10^5 * 10^5 + b1^2 + 2ab1* 10^5
我们可以提取一些公共的部分。
假设ab,ab1,ab2,ab3, … 都是满足要求的数字
那么(ab)^2 + (ab1)^2+ (ab2)^2+ … = (a^2 * 10^5 * 10^5) * cnt + 2 * a * 10^5 * (b+b1+b2+…) + (b^2+b1^2+b2^2…)
cnt为满足要求的数字个数, 10的多少次方可以根据数字长度预处理出来。
那么我们可以看出来
只要我们能获取满足要求的数字个数, 以及右侧所有b之和, 以及所有b^2之和 就能求出答案
所以我们dp数组类型定义成一个结构体,分别存长度,右侧数字之和, 右侧数字平方和这3项即可,
再就是状态划分了,长度缩短即可划分
具体可以看代码
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int C = 30, MOD = 1e9 + 7;
int t;
int a[C];
ll ten[C];
struct dp {
ll cnt;
ll sum;
ll sq_sum;
} f[C][C][C]; //f[i][j][k]表示从i位开始往后,最左侧到i位每位的数之和mod7 余j, 最左侧到i位的数 mod 7 余k
void ten_mi(){
ten[1] = 1;
for (int i = 2; i <= 18; i ++)
ten[i] = ten[i-1] * 10 % MOD;
}
dp dfs(int pos, int sum, int cur, bool limit) {
if (!pos) { //递归出口
int cnt = 0;
if (cur != 0 && sum != 0) cnt = 1; //为一个满足条件的数字,返回1
return f[pos][sum][cur] = (dp){cnt, 0, 0};
}
if (!limit && f[pos][sum][cur].cnt != -1) return f[pos][sum][cur];
int up = limit? a[pos] : 9;
dp ans{0, 0, 0};
for (int i = 0; i <= up; i ++) {
if (i==7) continue;
dp tmp = dfs(pos-1, (sum + i) % 7, (cur * 10 + i) % 7, limit && (i == a[pos]));
int k = i * ten[pos] % MOD;// 当前层的基值
ans.cnt = (ans.cnt + tmp.cnt) % MOD;
ans.sum = ((ans.sum + ((tmp.cnt * k) % MOD + tmp.sum) % MOD) % MOD) % MOD ;
ans.sq_sum += tmp.cnt * k % MOD * k % MOD;
ans.sq_sum += tmp.sq_sum % MOD;
ans.sq_sum += 2 * k % MOD * (tmp.sum % MOD) % MOD ;
ans.sq_sum %= MOD;
}
return limit ? ans : f[pos][sum][cur] = ans;
}
ll solve(ll x) { // 这题要注意数据范围必须是ll,我因为这里调试了很久
int len = 0;
while (x) {
a[++len] = x % 10;
x /= 10;
}
dp ans = dfs(len, 0, 0, true);
return ans.sq_sum % MOD;
}
int main() {
cin >> t;
ten_mi();
for (int i = 0; i < t; i ++) {
ll l, r;
cin >> l >> r;
memset(f, -1, sizeof f);
int x = solve(r);
int y = solve(l-1);
cout << (x - y + MOD) % MOD << endl;
}
return 0;
}
return f[pos][sum][cur] = (dp){cnt, 0, 0};这里面为什么返回的是{cnt,0,0}?
因为是自底向上递归的,回去的时候才把这一路的都加上