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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
| 开放局面
国际象棋中，在给定大小的棋盘上（按照固定朝向）摆放一系列棋子，称为局面。接下来，只考虑在n*n的棋盘上摆放n个兵，并使得每一行每一列都只有一个兵的局面。
如果棋盘的左下角是空的，且在这个位置摆放的车能够在不吃掉任何一个兵的情况下，通过只向右或向上移动到达棋盘的右上角，则称这样的局面为开放局面。
记f(n)为n*n棋盘上开放局面的数目。例如，f(3)=2，这两种开放局面如下图所示：
开放局面1
空兵空
兵空空
车空兵
开放局面2
兵空空
空空兵
车兵空
已知f(5)=70。
求f(10**8)对1\ 008\ 691\ 207取余的结果。
我的思路:dp.
首先打表,发现所有不开放局面都是堵成一条直线,比如样例为5时,除掉直接堵住出发点或结束点的所有不开放局面长下面的样子:
x |
x |
x |
x|
x |
x |
x |
x |
x|
x |
x |
x |
x|
x |
x |
x |
x |
x|
x |
x |
x |
x |
x |
x|
x |
x |
x |
x |
x|
x |
x |
x |
x |
x|
x |
x|
x |
x |
x |
x |
70
公式:
$$n!-2\sum_{i=1}^{n}(n-i)!+1+\sum_{i=1}^n\sum_{j=1}^n(n-i-j)!$$
大概是这样
所以我们枚举一边dp的围堵情况,另一边随便排列棋子,最后加上两边都堵住的情况即可.
注意这不是卡特兰数,数列的前几项为:
0,0,2,12,70,464,3498,29572
请给我c++代码,注意取模.
下面是一个样例程序,但是复杂度是n^2的,优化一下
import math
def compute_f(n):
"""
计算 f(n) = n! - 2*sum_{i=1}^n (n-i)! + 1 + sum_{i=1}^n sum_{j=1}^n (n-i-j)!
注意：当 (n-i-j) 为负数时，(n-i-j)! 视为 0
"""
# n!
n_fact = math.factorial(n)
# 第一项求和: sum_{i=1}^n (n-i)!
sum1 = 0
for i in range(1, n+1):
sum1 += math.factorial(n-i)
# 第二项双重求和: sum_{i=1}^n sum_{j=1}^n (n-i-j)!
sum2 = 0
for i in range(1, n+1):
for j in range(1, n+1):
k = n - i - j
if k >= 0:
sum2 += math.factorial(k)
# 当 k < 0 时，阶乘视为 0，不累加
result = n_fact - 2*sum1 + 1 + sum2
return result
# 测试几个值
if __name__ == "__main__":
for n in range(1, 11):
result = compute_f(n)
print(f"f({n}) = {result}")
|
