题目链接: P4999 烦人的数学作业
题目大意
详见题目
solution
有一个显而易见的结论
发现 \(ans_{l, r} = ans_{1. r} – ans_{1, l – 1}\)
那只需要处理 \(1 – r\) 的即可
设 \(f_{i, j}\) 表示长度为 \(i\) 最高位为 \(j\) 的和
\(f_{i, j} = \sum\limits_{k = 0}^{k \leqslant 9} f_{i – 1, k} + j * 10^{i – 1}\)
对于\(ans_{1, r}\) 我们可以采用以下策略 :
设 \(len\) 为 \(r\) 的位数, \(a_{len}\) 为 \(r\) 的每一位
- 对于所有长度小于 \(len\) 的 \(f\) , \(res += f_{i, j}, i \in [1, len – 1], j \in [1, 9]\)
- 对于长度等于 \(len\)且最高位小于 \(a_{len}\) 的 \(f\) , \(res += f_{len, j}, j \in [1, a_{len})\)
- 然后对于剩下的 \(len – 1\) 位, 我们继续执行 \(2\) 操作同时对之前已经操作过去的位数加和然后在往后操作时加上对应的次数的乘积, 不过 \(j\in [0, a_i)\) (因为最高位已经不为0了)
不过我们在处理时, 处理不到 \(r\)(其实是因为我不会)
那么答案就是 \(ans_{1, r + 1} – ans_{1, l}\)
那么状态转移就出来了,然后对结果进行分治即可
Code:
/**
* Author: Aliemo
* Data:
* Problem:
* Time: O()
*/
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>#define int long long
#define rr register#define inf 1e9
#define MAXN 100010using namespace std;const int mod = 1e9 + 7;inline int read() {
int s = 0, f = 0;
char ch = getchar();
while (!isdigit(ch)) f |= ch == '-', ch = getchar();
while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
return f ? -s : s;
}void print(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar(x % 10 + 48);
}int L, R, T, len, ans;int f[20][20], a[20];inline int f_pow(int x, int y) {
int ans = 1;
while (y) {
if (y & 1) ans = (ans * x) % mod;
x = (x * x) % mod;
y >>= 1;
}
return ans % mod;
}inline void init() {
memset(f, 0, sizeof f);
for (rr int i = 0; i <= 9; i++) f[1][i] = i;
for (rr int i = 2; i <= 18; i++) {
for (rr int j = 0; j <= 9; j++) {
for (rr int k = 0; k <= 9; k++)
f[i][j] = (f[i][j] + f[i - 1][k]) % mod;
f[i][j] = (f[i][j] + j * f_pow(10, i - 1)) % mod;
// cout << f[i][j] << " ";
}
// cout << "\n";
}
}inline int solve(int x) {
memset(a, 0, sizeof a);
len = ans = 0;
int sum = 0;
while(x) {
a[++len] = x % 10;
x /= 10;
}
for (rr int i = 1; i < len; i++)
for (rr int j = 1; j <= 9; j++)
ans = (ans + f[i][j]) % mod;
for (rr int i = 1; i < a[len]; i++) ans = (ans + f[len][i]) % mod;
// cout << ans << "\n";
sum += a[len];
for (rr int i = len - 1; i >= 1; i--) {
for (rr int j = 0; j < a[i]; j++)
ans = (ans + f[i][j]) % mod;
ans = (ans + sum * a[i] * f_pow(10, i - 1) % mod) % mod;
sum += a[i];
}
return ans % mod;
}signed main() {
T = read();
init();
while (T--) {
L = read(), R = read();
cout << (solve(R + 1) - solve(L) + mod) % mod<< "\n";
}
}
