链接
Robot - http://acm.hdu.edu.cn/showproblem.php?pid=5673
分析
- 从原点出发回到原点，且不会出现在原点左侧
- 从开始到任意时刻，向右步数不少于向左步数，且最终向右、向左步数相等；
- 若共 n n n步，向右和向左各 k k k步，则不动有 n − 2 k n-2k n−2k步，因此， C n n − 2 k × C k ， k ∈ { 0 , 1 , 2 , … ， ⌊ n 2 ⌋ } C_n^{n-2k} \times C_k，k\in\{0,1,2,…，\lfloor\frac{n}{2}\rfloor\} Cnn−2k×Ck，k∈{0,1,2,…，⌊2n⌋}
- 结论： M n = C n n × C 0 + C n n − 2 × C 1 + … + C n n − 2 × k × C k + … + C n n − 2 × ⌊ n 2 ⌋ × C ⌊ n 2 ⌋ M_n= C_n^n \times C_0 + C_n^{n-2} \times C_1 + … + C_n^{n-2 \times k} \times C_k+ …+ C_n^{n-2 \times \lfloor\frac{n}{2}\rfloor} \times C_{\lfloor\frac{n}{2}\rfloor} Mn=Cnn×C0+Cnn−2×C1+…+Cnn−2×k×Ck+…+Cnn−2×⌊2n⌋×C⌊2n⌋
-
C
k
C_k
Ck为卡特兰数，
M
n
M_n
Mn称为默慈金数
- 一个给定的数n的默慈金数是“在一个圆上的n个点间，画出彼此不相交的弦的全部方法的总数【允许某些或全部点不连线】
- 最初的几个默慈金数如下（OEIS中的数列A001006）：
1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, 310572, 853467, 2356779, 6536382, 18199284, 50852019, 142547559, 400763223, 1129760415, 3192727797, 9043402501, 25669818476, 73007772802, 208023278209, 593742784829 - 递推式： M n + 1 = M n + ∑ i = 0 n − 1 M i × M n − 1 − i = 2 n + 3 n + 3 M n + 3 n n + 3 M n − 1 M_{n+1}=M_n+\sum_{i=0}^{n-1}M_i \times M_{n-1-i}=\frac{2n+3}{n+3}M_n+\frac{3n}{n+3}M_{n-1} Mn+1=Mn+i=0∑n−1Mi×Mn−1−i=n+32n+3Mn+n+33nMn−1
- 此外，本题取模运算涉及费马小定理求逆元
代码
在这里插入代码片