2025 ICPC Asia Manila Regional（2025 ICPC 亚洲 菲律宾 马尼拉）——I. Stone Steps（在解决样例中出现的问题的时候，处理问题的方式尽量的这个能够和原来的方式有所关联，或者说，样例中出现的问题是提示我们思路中的漏洞，我们最好进行重新推导） · znzryb
## 题目大意
**题目名称：** 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](https://codeforces.com/gym/106262/submission/365694725)
::: 源代码
```cpp
/**
* 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 的背后情况。
