My solution
mango2011
·
·
题解
这道题算是比较套路的一道题目吧，下面是我的方法：
$2.$ 由于 $f(n)$ 的值下降迅速，而 $n$ 的值很大，所以考虑先进行一次操作，于是易知新的 $n'\le9000$，可以进行计算。
$3.$ 经过上面两步的转化，对于任意一个满足 $g(t,\min(4,k)-1)=m$ 的 $t$，答案都可以加上 $\le n$ 并且数位和为 $t$ 的数的个数。
$4.$ 由于 $3$，即把统计答案的过程分为两部分：
$1)$ 统计数位和为 $t(t\le9000)$ 的数的个数（非常简单的数位 $dp$）。
$2)$ 按照 $3$ 的思路统计答案。
$5.$ 时间复杂度正确，可以通过。
$6.$ 代码实现（码丑勿喷）：
```cpp
#include<bits/stdc++.h>
using namespace std;
string s;
int m,k,l,dp[1005][9005];
const int mod=1e9+7;
int o(int x)
{
int res=0;
while(x)
{
res+=x%10;
x/=10;
}
return res;
}
bool pd(int x)
{
int i;
for(i=1;i<=k;i++)
{
x=o(x);
}
if(x==m)
{
return true;
}
return false;
}
void solve()
{
int i,j,k,sum=s[0]-'0';
memset(dp,0,sizeof(dp));
for(i=0;i<s[0]-'0';i++)
{
dp[0][i]=1;
}
for(i=1;i<l;i++)
{
for(j=0;j<=9*(i+1);j++)
{
if(j-sum<s[i]-'0'&&j-sum>=0)
{
dp[i][j]++;
}
for(k=0;k<=9;k++)
{
if(k>j)
{
break;
}
dp[i][j]+=dp[i-1][j-k];
dp[i][j]%=mod;
}
}
sum+=s[i]-'0';
}
dp[l-1][sum]++;
}
int main()
{
ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
int T,ans,i;
cin>>T;
while(T--)
{
cin>>s>>k>>m;
if(k>4)
{
k=4;
}
k--;
l=s.size();
solve();
ans=0;
for(i=1;i<=9000;i++)
{
if(pd(i))
{
ans+=dp[l-1][i];
ans%=mod;
}
}
cout<<ans<<endl;
}
return 0;
}
```