luoguP4999 烦人的数学作业

时间：2023-03-08 23:43:44
luoguP4999 烦人的数学作业

写在前面

这两天信息量有点大，需要好好消化一下，呼呼

\(f[i][j]\) 的转移式还是好理解的，但是对于其实际意义课上有点糊

求 \(ans_{1, x}\) 是感觉手动把数拆开看会好理解一点？？

同级某巨佬wxf会用记忆化搜索做，我不会，太菜了

luoguP4999 烦人的数学作业

简述题意：

给定区间 \([ L , R ]\) ,求 \(L\) 到 \(R\) 区间内每个数字和 $ (1 \le L \le R \le 10^{18}) $ ，共 \(T\) 组数据 \((1 \le T \le 20)\)

Solution:

数位DP入门题？

设 \(f[i][j]\) ，第一维表示枚举到第 \(i\) 位， 第二维表示以 \(j\) 为最高位， \(f\) 数组用来存数字和

如 \(f[i][j]\) 中存的是 \([j000\cdots \ , \ j999\cdots]\) 这一区间的数字和，（其中每个数都有 \(i\) 位）

初始状态： \(f[1][i] = i \ (0 \le i \le 9)\)

考虑怎么转移，新枚举到的 \(f[i][j]\) 是在 \(f[i -1][k]\) 基础上加上新的一位，而因为新的一位后面可以跟 \(0 - 9\) 所有数，所以 \(k\) 的取值是 \(0 - 9\) ， 因为这样的数的数量是 \(10^{i - 1}\) 个，所以转移方程就推出来啦：

\[f[i][j] = ( \sum_{k = 0}^{9} f[i - 1][k] ) + j \times 10^{i - 1}
\]

考虑最后怎么合并答案 \(ans_{l, r}\) ，

可以考虑先求出 \(ans_{1, l}\) 和 \(ans_{1, r + 1}\) 的答案，最后在进行合并（至于为什么是 \(l\) 和 \(r + 1\) 后面会进行解释

手模一个样例看看： \(ans_{1, 114514}\)

发现可以将它拆开：

\[\begin{aligned}
& 114514 = \{ 0 - 99999 \} + \{ 100000 - 109999\} \\
& + \{ 110000 - 110999 ，111000 - 111999 ， 112000 - 112999 ， 113000 - 113999 \} \\
&+ \cdots \\
\end{aligned}
\]

用 \(f[i][j]\) 数组一个一个代换即可，前面多出的数可以用 \(sum\) 存一下在循环最后处理

在每一层后面处理一下前面多出的数（感觉说不清楚，感性理解一下/kk

可以发现循环到最后一位时并不会加上最后一个数，所以将所求区间整理一下就好啦

LL solve(LL x){

	LL ans = 0, sum = 0;

	LL s[22], len = 0;

	for(;x; x /= 10) s[++len] = x % 10;

	for(int i = len; i >= 1; --i){

		for(int j = 0; j < s[i]; ++j){

			ans = (ans + f[i][j]) % mod;

		}

		ans = (ans + sum * s[i] * quick_pow(10, i - 1) % mod) % mod;

		sum = (sum + s[i]) % mod;

	}

	return ans;

}

（一开始感觉这样写比 \(Aliemo\)写的简单，后来发现并没有什么本质的区别）

code：

/*

Work by: Suzt_ilymics

Knowledge: 数位DP

Time: luogu最优解第五？

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define LL long long

using namespace std;

const int mod = 1e9+7;

LL read(){

	LL s = 0, w = 1;

	char ch = getchar();

	while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar();	}

	while(ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + ch - '0', ch = getchar();

	return s * w;

} 

LL T, l, r, ans = 0;

LL f[22][22];

LL quick_pow(LL x, LL p){//快速幂

	LL res = 1;

	for( ; p; p >>= 1){

		if(p & 1) res = res * x;

		x = x * x;

	}

	return res;

}

void init(){//初始化

	for(int i = 1; i <= 9; ++i) f[1][i] = i; 

	for(int i = 2; i <= 19; ++i){

		for(int j = 0; j <= 9; ++j){

			for(int k = 0; k <= 9; ++k){

				f[i][j] = (f[i][j] + f[i - 1][k]) % mod;

			}

			f[i][j] = (f[i][j] + j * quick_pow(10, i - 1)) % mod;

//			cout<<f[i][j]<<" ";

		}

//		cout<<"\n";

	}

}

LL solve(LL x){//求ans（1 - x）

	LL ans = 0, sum = 0;

	LL s[22], len = 0;

	for(;x; x /= 10) s[++len] = x % 10;

	for(int i = len; i >= 1; --i){

		for(int j = 0; j < s[i]; ++j){

			ans = (ans + f[i][j]) % mod;

		}

		ans = (ans + sum * s[i] * quick_pow(10, i - 1) % mod) % mod;

		sum = (sum + s[i]) % mod;

	}

	return ans;

}

signed main()

{

	init();

	T = read();

	while(T--){

		l = read(), r = read();

		printf("%lld\n", (solve(r + 1) - solve(l) + mod) % mod);

	}

	return 0;

}

/*

in:

2

1 1000000000000000000

1 1000000000000000000

out:

3970

3970

*/

相关文章