小迟的数字2
题目大意：如果一个数字的十进制表示中，有连续的 1 个 1，或者有连续的 2 个 2，或者有连续的 3 个 3，或者有连续的 4 个 4，或 者有连续的 5 个 5，或者有连续的 6 个 6，或者有连续的 7 个 7，或者有连 续的 8 个 8，或者有连续的 9 个 9，认为这个数字是 good number。 现在想知道在所有 N 位数中有多少个 good number？ 这个数字可能有点大，所以对 109 + 7 取模就好了
区别上一道题,此题动规(因为有连续)
状态:设\(f[i][j][k]\)表示前i位,结尾位j,且持续了k个的方案数目
转移:见代码.主要就是把零和别的数字区别开来
边界:0至9
代码如下: 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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
using namespace std;
const int N = 1e3 + 6, mod = 1e9 + 7;
/*
inline int func(int x)
{
if (x == 1) return 1;
if (x == 2) return 19;
if (x == 3) return 269;
if (x == 4) return 3393;
if (x == 5) return 40175;
if (x == 6) return 457247;
if (x == 7) return 5065622;
if (x == 8) return 55038455;
if (x == 9) return 589325826;
return 239296951;
}
*/
int n;
int f[N][10][10];
inline int ksm(int a, int b)
{
int ret(1);
for (; b; b >>= 1)
{
if (b & 1) ret = ret * a % mod;
a = a * a % mod;
}
return ret;
}
signed main()
{
int i, j, k, l;
n = read();
for (i = 2; i < 10; ++ i) f[1][i][1] = 1;
for (i = 1; i < n; ++ i)
{
// j = 0;
{
j = 0;
k = 1;
for (l = 0; l < 10; ++ l)
{
if (! l) (f[i + 1][0][1] += f[i][0][1]) %= mod;
else if (1 < l) (f[i + 1][l][1] += f[i][0][1]) %= mod;
}
}
{
for (j = 1; j < 10; ++ j)
{
for (k = 0; k < j; ++ k)
{
for (l = 0; l < 10; ++ l)
{
if (l == j)
{
if (k + 1 < j)
{
(f[i + 1][j][k + 1] += f[i][j][k]) %= mod;
}
}
else
{
if (1 < l || ! l) (f[i + 1][l][1] += f[i][j][k]) %= mod;
}
}
}
}
}
}
int res = ((ksm(10, n) - ksm(10, n - 1)) % mod + mod) % mod;
for (i = 0; i < 10; ++ i)
{
for (j = 0; j < 10; ++ j)
{
if (! i || j < i)
{
res -= f[n][i][j];
res = (res % mod + mod) % mod;
}
}
}
put(res);
return 0;
}
后记:
打表程序并没有消除
因为打出来这个表,程序就跑了将近半个小时
在此记录,不枉存在