题解：P12397 「FAOI-R9」函数大师

· · 题解

函数 f_k(x) 是一个十分有趣的函数。

可以先做一下变形。

\begin{aligned}f_k(x)=S_0(x)+S_1(x)+S_2(x)\dots&=x+s(x)+S_0(s(x))+S_1(s(x))+\dots\\&=f_{k-1}(s(x))+x\end{aligned}

若 f_k(x)=m，则 m-f_{k-1}(s(x))=x。

由此可以看出符合条件的 x 不会超过 m。

因此，问题转化为每次询问有多少个 s(x) 使得 s(m-f_{k-1}(s(x)))=s(x)。由于 x\le m，所以 s(x) 不会很大，最大就到 162（当 x=10^{18}-1 时）。因此我们可以先预处理出 f_{k-1}(i),i\in[1,162]\land i\in\mathbb Z，处理询问时枚举所有可能的 s(x) 并对答案进行统计。时间复杂度 O(T\log m)。

代码如下：

#include<bits/stdc++.h>
using namespace std;
long long s(long long x){//求一个数在十进制下的各位数字之和
    long long ans=0;
    while(x) ans+=x%10,x/=10;
    return ans;
}
long long S[200][5];
long long f[200];//由于 k 是固定的，所以只需要开一维
int T,k;
long long m;
int main(){
    cin>>T>>k;
    for(int i=1;i<=162;i++){//预处理
        S[i][0]=i;
        S[i][1]=s(S[i][0]);
        S[i][2]=s(S[i][1]);
        if(k<=3)
            for(int j=0;j<k;j++) f[i]+=S[i][j];
        else f[i]=S[i][0]+S[i][1]+S[i][2]+1ll*(k-3)*S[i][2];
    }
    while(T--){
        cin>>m;
        long long ans=0;
        for(int i=1;i<=162;i++)//枚举 s(x)
            if(s(m-f[i])==i) ans++;
        cout<<ans<<'\n';
    }
}