WA#18#20 求调
查看原帖
WA#18#20 求调
616996
Graph楼主2024/7/18 12:53
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int mod=1e9+7;
int dp[20][10][10],digit[20];

void init()
{
	for(int k=0;k<=9;k++)
		dp[1][k][k]=1;
	for(int i=2;i<=19;i++)
		for(int j=0;j<=9;j++)
		{
			for(int p=0;p<=9;p++)
				for(int k=0;k<=9;k++)
					dp[i][j][k]=(dp[i-1][p][k]+dp[i][j][k])%mod;
			dp[i][j][j]+=pow(10,(signed)(i-1));
			dp[i][j][j]%=mod;
		}
	return ;
}

int helper(int x,int id)
{
	int cnt=0;
	while(x!=0)
	{
		digit[++cnt]=x%10;
		x/=10;
	}
	int ans=0;
	for(int i=1;i<=cnt-1;i++)
		for(int j=1;j<=9;j++)
			ans=(ans+dp[i][j][id])%mod;
	for(int i=1;i<digit[cnt];i++)
		ans=(ans+dp[cnt][i][id])%mod;
	for(int i=cnt-1;i>=1;i--)
	{
		for(int j=0;j<digit[i];j++)
			ans=(ans+dp[i][j][id])%mod;
		for(int p=cnt;p>=i+1;p--)
			if(digit[p]==id)
				ans+=1ll*digit[i]*pow(10,(signed)(i-1)),ans%=mod;
	}
	return ans;
}

signed main()
{
    int T;
    cin>>T;
	init();
    while(T--)
    {
        int L,R,ans=0;
    	cin>>L>>R;
    	for(int i=1;i<=9;i++)
    		ans=(ans+(((helper(R+1,i)-helper(L,i)+mod)%mod+mod)%mod+mod)%mod*i%mod)%mod;
    	cout<<(ans+mod)%mod<<"\n";
    }
	return 0;
}
2024/7/18 12:53
加载中...