萌新TLE求调
查看原帖
萌新TLE求调
110009
Soul_Love楼主2023/11/30 20:10
#include<bits/stdc++.h>
#define ll int
using namespace std;
ll n,m,f[10010][200],b[100],l;
inline ll read()
{
	ll k=0,f=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) f|=c=='-';
	for(;isdigit(c);c=getchar()) k=(k<<1)+(k<<3)+(c^48);
	return f?-k:k;
}
inline ll dfs(ll pos,bool lead,bool limit,ll dig,ll sum)
{
	if(pos<1) return sum;
	if(!limit&&f[pos][sum]!=-1&&lead) return f[pos][sum];
	ll up=limit?b[pos]:9,ans=0;
	for(int i=0;i<=up;i++) ans+=dfs(pos-1,lead||i,limit&&i==up,dig,sum+((i||lead)&&(i==dig)));
	if(!limit&&lead) f[pos][sum]=ans;
	return ans;
}
inline ll dp(ll x,ll d)
{
	memset(f,-1,sizeof(f));
	l=0;
	while(x)
	{
		b[++l]=x%10;
		x/=10;
	}
	return dfs(l,0,1,d,0);
}
int main()
{
	while(1)
	{
		n=read(),m=read();
		if(n==0&&m==0) break;
		for(int i=0;i<9;i++) printf("%d ",dp(m,i)-dp(n-1,i));
		printf("%d\n",dp(m,9)-dp(n-1,9));
	}
	return 0;
}
2023/11/30 20:10
加载中...