题解：P16140 圆圈函数（circle）

furina_hhz · 2026-11-11 18:41:59 · 题解

思路

注意到是统计合法数字个数的题目，考虑数位 DP。

先对原式做一个简单的变形。设 m=10a+b，其中 0\le b\le 9，则原式等价于：

化简得：

所以问题便等价于合法的 a 的个数，易得 0\le a\le \lfloor\frac{n}{10}\rfloor。这里对于每个 a，贡献的方案数实际上是可以取得的个位数字的数量。在一般情况下，每个合法 a 贡献的方案数为 10。只有当 a=\lfloor\frac{n}{10}\rfloor 时，贡献的方案数为 n \bmod 10。

开始设计数位 DP，因为存在进位，所以由低到高枚举数位。设 dp_{i,j,k,c} 为枚举到第 i 位，f(n+a)-f(a)=j，当前枚举到当前数位时的数为 k，是否存在进位的方案数（若 c=0，则无进位，反之有进位）。

但是我们发现，k 的取值过大，无法进行 DP。但我们可以发现，在对于枚举到第 i 的具有相同 j,c 的两个不同的数 k_1,k_2，我们仅需关心 k_1,k_2 与 \lfloor\frac{n}{10}\rfloor 的前 i 位的大小关系。若 k_1,k_2 与 \lfloor\frac{n}{10}\rfloor 的前 i 位的大小关系相同，由于对下一位的影响相同，所以对应方案数也相同。

于是我们可以设计一个新的 DP 状态。dp_{i,j,b,c} 表示枚举到第 i 位，f(n+a)-f(a)=j，k 与 \lfloor\frac{n}{10}\rfloor 的前 i 位的大小关系（设 \lfloor\frac{n}{10}\rfloor 的前 i 位为 m，若 k\le m，则为 1，反之为 0），是否存在进位的方案数（若 c=0，则无进位，反之有进位）。

接下来就是数位 DP 板子了（链接是一道经典模板题，不会的可以去学习）。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,sumbit,fn,ans,dp[20][80][2][2];
int cmp(int x){
    if(!x || x == 4 || x == 6 || x == 9) return 1;
    else if(x == 8) return 2;
    else if(x < 10) return 0;
    return cmp(x / 10) + cmp(x % 10);
}
int dfs(int bit,int mx,int r,int rm,int sum,bool b,bool c){
    /*
    最后的结果要满足：
    1. a <= floor(n/10)
    2. f(n+a) - f(a) = f(n)
    */
    if(bit > mx) return (mx != sumbit || !b) && sum + (r + c ? cmp(r + c) : 0) == fn;

    if(~dp[bit][40+sum][b][c]) return dp[bit][40+sum][b][c];
    dp[bit][40+sum][b][c] = 0;
    for(int i = bit == mx;i <= 9;i++){
        int now = r % 10 + i + c;
        dp[bit][40+sum][b][c] += dfs(bit + 1,mx,r / 10,rm  / 10,sum + cmp(now % 10) - cmp(i),i + b > rm % 10,now > 9);
    }
    return dp[bit][40+sum][b][c];
}
signed main(){
    scanf("%lld",&n);
    sumbit = log10(n),m = n / 10 - 1,fn = cmp(n);
    ans = min(10ll,n + 1);
    // 枚举数字位数，消除前导零影响
    for(int i = 1;i <= sumbit;i++){
        memset(dp,-1,sizeof(dp));
        ans += 10 * dfs(1,i,n,m,0,0,0);
    }
    if(sumbit && cmp(n + m + 1) == cmp(n) + cmp(m+1)) ans += n % 10 + 1;
    cout << ans;
}