CF908G New Year and Original Order题解

发表于

标签

数位dp + 性质

性质１

对于一个各数位上的数递增的数(如 14791479 )，这个数可以表示为 1111+1111+11+11+1...1111+1111+11+11+1...　这样的形式，具体如下 :

设 f(x,j)f(x, j) 表示 xx 中有 f(x,j)f(x, j) 个大于等于 jj 的数位。

那么 x=∑i=19∑j=1f(x,i)10j−1x = \sum_{i=1}^{9}\sum_{j=1}^{f(x,i)}10^{j-1}

不形式化的来说，如 34593459 可以表示为一下几个数的和。

1111111111111111111111111\\ 1111\\ 1111\\ 111\\ 11\\ 1\\ 1\\ 1\\ 1\\

一个 99 行，对于第 ii 行, 其中 11 的个数是原数中大于等于 ii 的数位的个数。

思路

那么得到这个性质后有什么用呢？，我们发现对于 1−91-9 每一个数，在运用这个性质后就是独立的了，所以我们可以对于1−91-9 每一个数单独做一遍数位 dpdp , 设 f[i][j][0/1]f[i][j][0/1] 表示当前是第 ii 位，要 dpdp 的数出现了 jj 次的方案数，0/10/1 至少用来维护是否压上界.

1−91-9 每一个数的贡献就是 ∑i=1len(f[len][i][0]+f[len][i][1])∑j=1i10j−1\sum_{i=1}^{len}(f[len][i][0] + f[len][i][1])\sum_{j=1}^{i}10^{j - 1} 即方案数乘每种情况的贡献

然后把每个数的贡献加起来就行。

Code

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long

using namespace std;

const int N = 710;
const ll mod = 1e9 + 7;
ll f[2 * N][2 * N][2];
int n, len, a[N];
char ch[N];
ll ans;

int add(int a, int b)
{
  return a + b >= mod ? a + b - mod : a + b;
}

int main()
{
  scanf("%s", ch + 1);
  len = strlen(ch + 1);
  for (int i = 1; i <= len; ++i)
  {
    a[i] = ch[i] - '0';
  }
  for (int d = 1; d <= 9; ++d)
  {
    memset(f, 0, sizeof(f));
    f[0][0][1] = 1;
    for (int i = 0; i <= len - 1; ++i)
    {
      for (int j = 0; j <= i; ++j)
      {
        for (int k = 0; k <= 9; ++k)
        {
          if (k >= d) f[i + 1][j + 1][0] = add(f[i + 1][j + 1][0], f[i][j][0]);
          else f[i + 1][j][0] = add(f[i + 1][j][0], f[i][j][0]);
        }
        for (int k = 0; k < a[i + 1]; ++k)
        {
          if (k >= d) f[i + 1][j + 1][0] = add(f[i + 1][j + 1][0], f[i][j][1]);
          else f[i + 1][j][0] = add(f[i + 1][j][0], f[i][j][1]);
        }
        if (a[i + 1] >= d) f[i + 1][j + 1][1] = add(f[i + 1][j + 1][1], f[i][j][1]);
        else f[i + 1][j][1] = add(f[i + 1][j][1], f[i][j][1]);
      }
    }
    ll tmp = 1;
    for (int i = 1; i <= len; ++i)
    {
      ans = add(ans, tmp * add(f[len][i][1], f[len][i][0]) % mod), tmp = add(tmp * 10 % mod, 1);
    }
  }
  cout << ans << endl;
  return 0;
}