CF908G

CF908G

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

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

所以

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

我们给这个式子差分一下,成为了:

考虑后面那一段,所有大于等于 $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)$。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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;
}
文章作者: yijan
文章链接: https://yijan.co/cf908g/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog