数位 DP.
题意：给定 $n leqslant 10^{700}$，求 $1$ 到 $n$ 中每个数在各数位排序后得到的数的和.
这道题从整体上看上去貌似不太可做，不妨从每一位开始考虑.
比如说我们可以考虑第 $i$ 位为 $k$ 的数目，然后乘上 $10^i$ 后就是这一位的贡献了.
这么做的好处是不用考虑其他位置上填的是什么.
直接求第 $i$ 个位置上是 $k$ 不太好求，不妨考虑大于等于 $k$ 的方案数.
那么 $k$ 的贡献就是 $sum f[i][j]$ 其中 $j leqslant k$.
由于 $j$ 在 $1$ ~ $k$ 时会贡献 $k$ 次，所以我们求出 $f[i][j]$ 乘上对应次幂加和就是答案了.
假如第 $i$ 位置的数大于等于 $k$，那么 $i+1$ ~ $n$ 位置的数也必须大于等于 $k$.
所以不妨设状态 $f[i][j][k][l]$ 表示当前考虑到第 $i$ 位，有 $j$ 个位置大于等于 $k$，是否顶着 $n$ 的上界.
这个可以用数位 DP 求，转移也比较简单.
然后考虑最后求出了 $f[n][j][k][0/1]$，第 $i$ 位置的贡献就是 $sum f[n][j][k][0/1] imes 10^j$ ( $i leqslant j$)
那么总结下来就是 $ans=sum f[n][j][k][0/1] imes 111111$ ( $j$ 个 1）
code:
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 703
#define ll long long
#define mod 1000000007
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
char str[N];
int n,a[N],f[N][N][10][2];
int main() {
// setIO("input");
scanf("%s",str+1),n=strlen(str+1);
for(int i=1;i<=n;++i) a[i]=str[i]-'0';
for(int i=1;i<=9;++i) f[0][0][i][0]=1;
for(int i=0;i<n;++i) {
for(int k=1;k<=9;++k) {
for(int j=0;j<=i;++j) {
for(int l=0;l<2;++l) {
int lim=l?9:a[i+1];
for(int p=0;p<=lim;++p) {
(f[i+1][j+(p>=k)][k][l|(p<a[i+1])]+=f[i][j][k][l])%=mod;
}
}
}
}
}
int ans=0;
for(int k=1;k<=9;++k) {
int re=1;
for(int i=1;i<=n;++i) {
(ans+=(ll)re*(f[n][i][k][0]+f[n][i][k][1])%mod)%=mod;
re=(ll)((ll)re*10%mod+1)%mod;
}
}
printf("%d
",ans);
return 0;
}