2025 ICPC Asia Manila Regional（2025 ICPC 亚洲 菲律宾 马尼拉）——I. Stone Steps（在解决样例中出现的问题的时候，处理问题的方式尽量的这个能够和原来的方式有所关联，或者说，样例中出现的问题是提示我们思路中的漏洞，我们最好进行重新推导）

题目大意

题目名称： Stone Steps

题目描述：
给定一个仅包含非零十进制数字的字符串 $s$（长度 $1 \le |s| \le 5 \times 10^5$）。

对于任意不包含数字 0 的正整数 $n$，定义 $H(n)$ 为将 $n$ 的所有数位按非降序（从小到大）重新排序后得到的新整数。例如：$H(1971) = 1179$，$H(3) = 3$。

你的任务是计算字符串 $s$ 的所有非空连续子串所代表的十进制整数的 $H$ 函数值之和。即对于所有满足 $1 \le i \le j \le |s|$ 的子串 $s[i...j]$，求出 $H(s[i...j])$ 并求和。最终的结果需要对 1000696967 取模后输出。

输入格式：
单行输入一个字符串 $s$。

输出格式：
输出一个整数，表示所有非空连续子串的 $H$ 函数值之和对 1000696967 取模的结果。

样例 1：

输入：
3141

输出：
1432

样例 1 解释：
当 $s$ 为 3141 时，共有 10 个非空连续子串，计算过程如下：

• $s[1...1]$ 为 3，$H(3) = 3$

• $s[2...2]$ 为 1，$H(1) = 1$

• $s[3...3]$ 为 4，$H(4) = 4$

• $s[4...4]$ 为 1，$H(1) = 1$

• $s[1...2]$ 为 31，$H(31) = 13$

• $s[2...3]$ 为 14，$H(14) = 14$

• $s[3...4]$ 为 41，$H(41) = 14$

• $s[1...3]$ 为 314，$H(314) = 134$

• $s[2...4]$ 为 141，$H(141) = 114$

• $s[1...4]$ 为 3141，$H(3141) = 1134$

将其相加得：$3 + 1 + 4 + 1 + 13 + 14 + 14 + 134 + 114 + 1134 = 1432$。

样例 2：

输入：
1

输出：
1

样例 3：

输入：
11234567891234567891

输出：
43138332

思路讲解

还是要使用拆分算贡献的思想。

我们还需要利用一个东西，就是数位，其实只有 9 个，所以我们不用想着一次遍历去解决，可以遍历 9 次。

不过，我认为最有用的，还是把这个所有的东西，贡献，全部写下来。然后看看有什么规律。全部都写下来以后，我们发现这个规律非常的简单。

然后就跟着上面的这个公式求就完了。

以样例一具体而言就是：

推这种式子就是要细心。

AC代码

AC

https://codeforces.com/gym/106262/submission/365694725

源代码

/**
 * Problem: I. Stone Steps
 * Contest: 2025 ICPC Asia Manila Regional
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106262/problem/I
 * Created: 2026-03-07 12:15:37
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10/*, INF = (1ll<<61)-1*/;
static constexpr ll mod = 1000696967;
// static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
ll pow10[MAXN];
void Solve() {
    string s;
    cin>>s;
    ll N=SZ(s);
    s.insert(s.begin(),'#');
    vector<ll> A(N+2);
    for (int i=1;i<=N;++i) {
        A[i]=s[i]-'0';
    }
    ll ans=0;
    // set<ll> st_pos;
    for (int d=1;d<=9;++d) {
        vector<ll> suf_sum_diff_gt_d(N+2)/*,suf_cnt_gt_d(N+2)*/;
        vector<ll> suf_pos(N+2);
        suf_pos[N+1]=N+1;
        do {
            vector<ll> i_vec;
            i_vec.push_back(N+1);
            for (ll i=N;i>=1;--i) {
                suf_sum_diff_gt_d[i]=suf_sum_diff_gt_d[i+1];
                suf_pos[i]=suf_pos[i+1];
                // suf_cnt_gt_d[i]=suf_cnt_gt_d[i+1];
                if (A[i]>=d) {
                    suf_sum_diff_gt_d[i]+=i_vec.back()-i;
                    suf_sum_diff_gt_d[i]*=10;
                    suf_sum_diff_gt_d[i]%=mod;
                    suf_pos[i]=i;
                    i_vec.push_back(i);
                    // suf_cnt_gt_d[i]++;
                }
            }
        }while (false);

        vector<ll> i_pos;
        // 哨兵节点
        i_pos.push_back(0);
        ll glo_sum=0;
        for (int i=1;i<=N;++i) {
             if (A[i]>d) {
                 glo_sum*=10;
                 glo_sum%=mod;
                 glo_sum+=i-i_pos.back();
                 i_pos.push_back(i);
             }else if (A[i]==d) {
                 ll sum=glo_sum;
                 sum*=10;
                 sum%=mod;
                 sum+=i-i_pos.back();
                 // lsum 是在前面的，所有的值的条件下，的贡献
                 ll lsum=A[i]*sum%mod;
                 // lans 是算的是后面的
                 ll lans=sum*suf_sum_diff_gt_d[i+1]%mod;
                 lans+=sum*(suf_pos[i+1]-(i+1))%mod;
                 lans%=mod;
                 lans*=A[i];
                 lans%=mod;
                 ans+=lans;
                 ans+=lsum;
                 ans%=mod;
                 ans%=mod;
             }
        }
    }
    ans%=mod;
    if (ans<0) {
        ans+=mod;
    }
    cout<<ans<<"\n";
    // mod 1000696967
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif
    pow10[0]=1;
    for (int i=1;i<=MAXN-5;++i) {
        pow10[i]=pow10[i-1]*10;
        pow10[i]%=mod;
    }
    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*

_______________[ Stress test, testcase 14 INPUT ]_______________
832

_______________[ Stress test, testcase 14 OUTPUT]_______________
282

expected：312

*/

心路历程（WA，TLE，MLE……）

在处理 lans，也就是背后的时候，忘记处理了不含 i7 的情况，即什么都不含，只含 i5 的背后情况。