怎么简化这个递推？

litaoye

http://www.51nod.com/question/index.html#!questionId=478

wayne

先可求得g(n)的表达式：
$g(n) = \frac{(-1)^{n/2} n! C_{n-2}^{n/2-1}}{n/2}$ (n为大于2的偶数)
g(n) = 0 (n为奇数)

接下来，组合数的模运算就不难了

mathematica

2# wayne


你是怎么简化出来的？？？？？？？

litaoye

先可求得g(n)的表达式：
g(n) = \frac{(-1)^{n/2} n! C_{n-2}^{n/2-1}}{n/2} (n为大于2的偶数)
g(n) = 0 (n为奇数)

接下来，组合数的模运算就不难了
wayne 发表于 2012-8-29 12:55

wayne现在好厉害呀！这个化简是怎么做的？

litaoye

先可求得g(n)的表达式：
g(n) = \frac{(-1)^{n/2} n! C_{n-2}^{n/2-1}}{n/2} (n为大于2的偶数)
g(n) = 0 (n为奇数)

接下来，组合数的模运算就不难了
wayne 发表于 2012-8-29 12:55

g(n) = 0好像有问题呀！

litaoye

难道是我算错了？

g(0) = 0
g(1) = 1
g(2) = -3
g(3) = 12
g(4) = -63

mathematica

这个问题的背景是什么呢？？？？？？？？？

mathematica

我不会，看到这个问题就觉得很难

litaoye

这个问题的背景是什么呢？？？？？？？？？
mathematica 发表于 2012-8-29 18:57

背景就是这道题本身，前两天在一个群里大家互相弄些比较难的ACM题，这是其中一道。

wayne

6# litaoye
是我理解错了吗?
g(2) = -2*2*g(1) +C(2,1)*g(1)*g(1)  =  -2
g(3) = -2*3*g(2) + C(3,1)*g(1)*g(2)+C(3,2)*g(1)*g(2) = 0