ABC的C求条
  • 板块学术版
  • 楼主sbno333
  • 当前回复3
  • 已保存回复3
  • 发布时间2025/1/4 22:01
  • 上次更新2025/1/5 11:26:12
查看原帖
ABC的C求条
416975
sbno333楼主2025/1/4 22:01
#include<bits/stdc++.h>
using namespace std;
#define int __int128
int m[19][19];
int ksm(int a,int b){
  if(b<0){
    return 1;
  }
	return m[a][b];
}
int dp[29][29];
int f(int cg,int ws,int x){
	if(ws<0){
		return 0;
	}
	if(ws==0){
		return min(x,cg-1)+1;
	}
	int p;
	p=x/ksm(10,ws);
	if(p==0){
		return f(cg,ws-1,x);
	}
	if(p>=cg){
		return ksm(cg,ws+1);
	}
	return p*ksm(cg,ws)+f(cg,ws-1,x-ksm(10,ws)*p);
}
int s(int x){
	if(x==0){
		return 1;
	}
	int g;
	g=0;
	for(int i=0;i<=18;i++){
		if(x/ksm(10,i)<10){
			g=i;
			break;
		}
	}
	int z;
	z=x/ksm(10,g);
	int ans;
	ans=dp[g][z];
	//cout<<g<<" "<<z<<" "<<ans<<endl;
	ans+=f(z,g-1,x-z*ksm(10,g));
	return ans;
}
signed main(){
	for(int i=1;i<=10;i++){
		m[i][0]=1;
		for(int j=1;j<=18;j++){
			m[i][j]=m[i][j-1]*i;
		}
	}
	for(int i=1;i<=9;i++){
		dp[0][i]=i;
	}
	for(int i=1;i<=18;i++){
		dp[i][1]=dp[i-1][9]+ksm(9,i-1);
		for(int j=2;j<=9;j++){
			dp[i][j]=dp[i][j-1]+ksm(j-1,i);
		}
	}
	long long l,r;
	cin>>l>>r;
	cout<<(long long)(s(r)-s(l-1));
	return 0;
}

玄关。

2025/1/4 22:01
加载中...