有没有巨佬来捞下蒟蒻a
查看原帖
有没有巨佬来捞下蒟蒻a
587959
ydkxj楼主2024/1/27 21:10

代码如下

#include<iostream>
#include<cstring>
#define int long long
#define Mod 1000000007
using namespace std;
int f[50050][10],g[50050],ten[50050],L[50050],R[50050];
int answer(string s,string s1){
	int lenr=0,lenl=0,len=0,ans=0;
	ten[0]=1;
	for (int i=1;i<=50010;i++) 
		ten[i]=(ten[i-1]*10)%Mod;
	int r=0;
	lenr=s1.size();
	for (int i=1;i<=lenr;i++)
		R[i]=s1[lenr-i+1]-'0';
	g[lenr+1]=0;
	for (int i=lenr;i>=0;i--)
		g[i]=(g[i+1]*10+R[i])%Mod;
	for (int i=1;i<=lenr;i++){
		for (int j=0;j<=9;j++){
			f[i][j]=(g[i+1]*ten[i-1])%Mod;
			if(j<R[i])f[i][j]=(f[i][j]+ten[i-1])%Mod;
			else if(j==R[i])f[i][j]=(f[i][j]+r+1)%Mod;
		}
		r=(r+R[i]*ten[i-1])%Mod;
	}
	lenl=s.size();
	for (int i=1;i<=lenl;i++) 
		L[i]=s[lenl-i+1]-'0';
	L[1]--;
	for (int i=1;i<=lenl;i++) 
		if(L[i]<0){
			L[i]+=10;
			L[i+1]--;
			}
	while(lenl>1&&!L[lenl]) 
		lenl--;
	lenl=lenr;
	memset(g,0,sizeof g);
	for (int i=lenl;i;i--) 
		g[i]=(g[i+1]*10+L[i])%Mod;
	r=0;
	for (int i=1;i<=lenl;i++){
		for (int j=0;j<=9;j++){
			f[i][j]=(f[i][j]-g[i+1]*ten[i-1]+Mod)%Mod;
			if (j<L[i]) f[i][j]=(f[i][j]-ten[i-1]+Mod)%Mod;
			else if (j==L[i]) f[i][j]=(f[i][j]-r-1+Mod)%Mod;
		}
		r=(r+L[i]*ten[i-1])%Mod;
	}
	len=max(lenr,lenl);
	ans=0;
	for (int i=1;i<=len;i++)
		for (int j=0;j<=9;j++)
			for (int k=0;k<=9;k++) 
				ans=(ans+f[i][j]*f[i][k]*abs(j-k))%Mod;
	return ans;
}
signed main()
{
	string a,b;
	cin>>a>>b;
	cout<<answer(a,b)<<endl;
	return 0;
}
2024/1/27 21:10
加载中...