出题人题解 | #little w and Digital Root#

原题解链接：https://ac.nowcoder.com/discuss/150260

本来一开始是想找规律的,然后也确实有点规律,只要数字不进位,最后求出来的这个加权数根就是$2-92-9$循环的,但是每次进位都会跳一小段。

首先计算最大数字的加权数根，发现计算一次之后的结果小于$16001600$,所以预处理$11$到$16001600$的加权数根。( 当然多算几次压到$1010$以内也可以)并且把第一次计算数根的结果作为状态存入$dpdp$数组。

然后分别求$22$到$99$即可。( $11$不用求，只有$11$的加权数根才等于$11$ ,后面不可能出现$11$)

#include <bits/stdc++.h>
using namespace std;
long long dp[22][1600][15];
char s[22];
long long a[500];
int answer[1600];

long long dfs(int pos ,long long sta,int limit,long long  value)
{
	if(pos==-1)
		return answer[sta]==value;
	if(!limit&&dp[pos][sta][value]!=-1)return dp[pos][sta][value];
	long long  up=limit?a[pos]:9;
	long long ans=0;
	for (int i = 0; i <= up; i++)
	{
		ans+=dfs(pos-1,(i*(pos+1)+sta),limit&&i==a[pos],value);
	}
	if(!limit)dp[pos][sta][value]=ans;
	return ans;
}


long long solve(long long x,long long q)
{
	int pos=0;
	while(x)
	{
		a[pos++]=x%10;
		x/=10;
	}
	return dfs(pos-1,0,true,q);
}

int get_root(int x)
{
	if(x<10)return x;
	int ans=0;
	int cnt=1;
	while(x)
	{
		ans+=x%10*cnt;
		x/=10;
		++cnt;
	}
	return get_root(ans);
}

int main()
{
	for(int i=0;i<1600;i++)
	{
		answer[i]=get_root(i);
	}
	long long l,r;
	int t;
	cin>>t;	memset(dp,-1, sizeof(dp));
	for(int cas=1;cas<=t;cas++)
	{
		scanf("%lld%lld",&l,&r);
	
		printf("Case #%d: ",cas);
		printf("%lld",solve(r,1)-solve(l-1,1));
		for(long long q=2;q<=9;q++)
		printf(" %lld",solve(r,q)-solve(l-1,q));
		puts("");
	}
	return 0;
}