自创dp方法,但只有50分求助而且连#3都错了
查看原帖
自创dp方法,但只有50分求助而且连#3都错了
1041773
sherq楼主2024/1/22 21:40
#include<iostream>
#include<cmath>
using namespace std;

//f(i, j)表示从1 求和到 j*10^(i-1)的值
//计算一个数a,通过对其每一个数位进行计算得出结果
//例如4321:求值方法为(1,4000) (1,300) (1,20) (1,1) 的和再加上321个4,21个3,1个2 

long long int dp[19][10]; 
const int Mod = 1e9 + 7;

int main(){
	for(int i = 1; i < 10 ; i++){
		dp[1][i] = i + dp[1][i-1];
	}
	for(int i = 2 ; i < 19 ; i++){
		dp[i][0] = (dp[i-1][9] + dp[i-1][1] + 9 * ((long long)pow(10, i-2) % Mod) - 9) % Mod;
		for(int j = 1 ; j < 10 ; j++){
			dp[i][j] = (dp[i][j-1] + dp[i][1] + (j-1) * ((long long)pow(10, i-1) % Mod)) % Mod;
		}
	}
	int n;
	cin>>n;
	while(n--){
		long long int a, b;
		cin>>a>>b;
		a--;
		long long int tmp_a = a, tmp_b = b;
		long long int count_a = 0, count_b = 0;
		int count = 1;
		while(b){
			count_b = (count_b + dp[count++][b%10]) % Mod;
			count_b = (count_b + (tmp_b % (long long)pow(10, count - 2)) * (b % 10) % Mod) % Mod;
			b /= 10;
		}
		count = 1;
		while(a){
			count_a = (count_a + dp[count++][a%10]) % Mod;
			count_a = (count_a + (tmp_a % (long long)pow(10, count - 2)) * (a % 10) % Mod) % Mod;
			a /= 10;
		}
		cout<<(count_b - count_a + Mod) % Mod<<endl;
	}
	return 0;
}
2024/1/22 21:40
加载中...