悬棺,动态dp,调了两周,看不出什么问题,悬棺!
查看原帖
悬棺,动态dp,调了两周,看不出什么问题,悬棺!
1174770
xiaoqimingbozai楼主2024/6/2 13:17
#define ll long long
using namespace std;

ll f[20][20][20],ans[20];
ll ksm(int a,int b)
{
	ll ns=1;
	ll t=a;
	while(b)
	{
		if(b&1) ns*=t;
		t*=t;
		b>>=1;
	}
	return ns;
}
void work1(int k,int a,int b)
{
	ll t=0,w=0,fr=0,temp=0;
	while(b)
	{
		t=b%10;
		ans[k]+=f[w][t][k];
		w++;
		b/=10;
		if(t==k) ans[k]+=fr;
		fr+=ksm(10,w-1)*t;
//		printf("%d %d \n",w,fr);
	}
	t=0,w=0,fr=0;
	while(a)
	{
		t=a%10;
		temp+=f[w][t][k];
		w++;
		a/=10;
		if(t==k) temp+=fr;
		fr+=ksm(10,w-1)*t;
	}
	ans[k]-=temp;
}
ll work2(int c)
{
	ll temp=0,ns=0;
	for(int i=c;i>=1;i--)
	{
		ns+=i*temp;
		temp*=10;
		temp+=9;
	}
	return ns;
}
int main()
{
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=1;i<=9;i++)
		for(int j=i;j<=9;j++)
			f[0][j][i]=1;
	for(int k=0;k<=9;k++)
	{
//		printf("\n%d______________________\n",k);
		for(int i=1;i<=14;i++)
		{
//			printf("\n");
			for(int j=1;j<=9;j++)
			{
				if(j!=1)
				{
					f[i][j][k]=f[i][j-1][k]+f[i][1][k];
					if(k==1) f[i][j][k]--;
					if(j==k+1&&k!=0) f[i][j][k]+=(ksm(10,i)-1);
					if(j==k) f[i][j][k]++;
					if(k==0) f[i][j][k]+=work2(i);
				}
				if(j==1)
				{
					f[i][j][k]=f[i-1][9][k]+f[i-1][1][k];
					if(k==9) f[i][j][k]+=(ksm(10,i-1)-1);
					if(k==0) f[i][j][k]+=(1+work2(i-1));
				}
//				printf("f[%d][%d][%d]==%lld ",i,j,k,f[i][j][k]);
			}
		}
	}

	for(int i=0;i<=9;i++)
	{
		work1(i,a-1,b);
		printf("%lld ",ans[i]);
	}
	printf("\n");
	return 0;
}```
2024/6/2 13:17
加载中...