每次重新算当前 cnt 的方案

#include <bits/stdc++.h>
#define int long long
using namespace std;
string s;
int ans;
int cnt[10];
int C[55][55];
void getC()
{
    for (int i = 0; i <= 50; i++)
        for (int j = 0; j <= i; j++)
            if (j == 0 || j == i)
                C[i][j] = 1;
            else
                C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
// 当前 cnt 对应的排列数量
int cal()
{
    int num = 0; // 当前多少个位置
    for (int i = 0; i <= 9; i++)
        num += cnt[i];
    int res = 1; // 一个个数往里放
    for (int i = 0; i <= 9; i++)
    {
        res *= C[num][cnt[i]];
        num -= cnt[i];
    }
    return res;
}
void dfs(int now)
{
    if (now == s.size())
        return;
    // 考虑 s[now] 与谁交换
    for (int i = 0; i < s[now] - '0'; i++)
    {
        
        if (!cnt[i])
            continue;
        cnt[i]--;     // 某个 i 与 s[now] 进行了交换因为要重新排列，所以和谁交换无所谓
        ans += cal(); // 当前的 cnt 的排列数量
        cnt[i]++;     // 还原
    }
    // 把 cnt 变为 s[now+1]~ 的状态
    cnt[s[now] - '0']--;
    dfs(now + 1);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    getC();
    cin >> s;
    for (int i = 0; i < s.size(); i++)
        cnt[s[i] - '0']++;
    ans = 0;
    dfs(0);
    cout << ans << endl;
    return 0;
}

动态维护当前 cnt 对应的方案数

#include <bits/stdc++.h>
#define int long long
using namespace std;
string s;
int ans;
int num, cnt[10]; // cnt 之和、每个数字出现次数
int C[55][55];
void getC()
{
    for (int i = 0; i <= 50; i++)
        for (int j = 0; j <= i; j++)
            if (j == 0 || j == i)
                C[i][j] = 1;
            else
                C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
// 当前 cnt 对应的排列数量
int cal;
void dfs(int now)
{
    if (now == s.size())
        return;
    // 考虑 s[now] 与谁交换
    for (int i = 0; i < s[now] - '0'; i++)
    {

        if (!cnt[i])
            continue;
        // 处理 cnt[i]--
        cal /= C[num][cnt[i]];
        cnt[i]--;
        num--;
        cal *= C[num][cnt[i]];
        // 记录答案
        ans += cal; // 当前的 cnt 的排列数量
        // 处理 cnt[i]++
        cal /= C[num][cnt[i]];
        cnt[i]++;
        num++;
        cal *= C[num][cnt[i]];
    }
    // 把 cnt 变为 s[now+1]~ 的状态
    cal /= C[num][cnt[s[now] - '0']];
    cnt[s[now] - '0']--;
    num--;
    cal *= C[num][cnt[s[now] - '0']];
    dfs(now + 1);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    getC();
    cin >> s;
    for (int i = 0; i < s.size(); i++)
        cnt[s[i] - '0']++;
    // 算初始 cal
    cal = 1;
    num = s.size(); // 当前多少个位置
    for (int i = 0; i <= 9; i++)
    {
        cal *= C[num][cnt[i]];
        num -= cnt[i];
    }
    num = s.size();
    // work
    ans = 0;
    dfs(0);
    cout << ans << endl;
    return 0;
}