CF908G

我们考虑给数字排序后一个数位的贡献。

每个数字的贡献可以表示成 $10^i$ 的形式，就是它的位置乘上 $10^i$

所以

$$ans = \sum_{dig} dig\times c(dig)$$

其中 $c(i)$ 表示 这一位最后被分配到的位置置 1 所得到的一串 11…111000…00

我们给这个式子差分一下，成为了：

$$ans = \sum_{dig} \sum_{i\ge dig} c(i)$$

考虑后面那一段，所有大于等于 $dig$ 的 $c(i)$ 的和，就是一串纯 1 的数（越大的会被排在后面）。

于是我们设 $dp[i][j][k][0/1]$ 表示前 $i$ 个位置有 $j$ 位大于等于 $k$ ，最后是否严格小于等于 $n$ 的方案数量。

于是 $dp[i][j][k][b]$ 可以转移到 $dp[i+1][j+[p\ge k]][k][b|(p<a_{i+1})]$ 。

显然它关于 $k$ 独立，可以直接去掉，并且可以滚一下，于是数组只需要开 $O(n)$。。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
using namespace std;
#define MAXN 706
#define P 1000000007
int n;
char d[MAXN];
int f[2][MAXN][2] , A[MAXN];
int main() {
    scanf("%s",d + 1);
    n = strlen( d + 1 );
    for( int i = 1 ; i <= n ; ++ i ) A[i] = d[i] - '0';
    int res = 0;
    for( int k = 1 ; k < 10 ; ++ k ) {
        memset( f[0] , 0 , sizeof f[0] );
        for( int i = 0 ; i < 10 ; ++ i ) f[0][i][0] = 1;
        int cur = 1 , nxt = 0;
        for( int i = 0 ; i < n ; ++ i ) {
            cur ^= 1 , nxt ^= 1;
            memset( f[nxt] , 0 , sizeof f[nxt] );
            for( int j = 0 ; j <= i ; ++ j )
                for( int l = 0 ; l <= 1 ; ++ l )
                    for( int p = 0 ; p <= ( l ? 9 : A[i + 1] ) ; ++ p )
                        ( f[nxt][j + ( p >= k )][l | (p < A[i + 1])] += f[cur][j][l] ) %= P;
//                        cout << i + 1 << ' ' << ( j + ( p >= k ) ) << ' ' << ( l | ( p < A[i + 1] ) ) << " <-- " << i << ' ' << j << ' ' << l << " : " << f[cur][j][l] << endl;
        }
        int c = 1;
        for( int i = 1 ; i <= n ; ++ i )
            ( res += 1ll * ( f[nxt][i][0] + f[nxt][i][1] ) * c % P ) %= P , c = ( 10ll * c + 1 ) % P;
    }
    cout << res << endl;
}