Trick 6: 组合数学小技巧

1. 求解递推式 \(a_n = xa_{n-1} + y\)。

分析：换元，加入一个常数 \(c\)，我们期望得到这样一个结果：

\(a_n + c = x(a_{n-1} + c)\)。

化简后和上式对应，解得 \(c = \dfrac{y}{x-1}\)。

答案不放了。

2. 求 \(\sum \limits_{k=0}^n {3k \choose x}\)，\(n=10^6\)，预处理出所有 \(x\)。

分析：很巧妙，我们引入 \(\sum \limits_{k=0}^{n-1} {3k+1 \choose x}\) 和 \(\sum \limits_{k=0}^{n-1} {3k+2 \choose x}\)。(先假设是 \(0 \sim n-1\)，最后加上)

众所周知，\({3k+1 \choose x} = {3k \choose x} + {3k \choose x-1}\)。于是我们设递推式 \(f(x,0/1/2)\)。

则 \(f(x,1) = f(x,0) + f(x-1,0)\)。\(f(x,2) = f(x,1) + f(x-1,1)\)。牛不牛逼？

可是 \(f(x,0)\) 还没的推？？？那么核心所在，利用可推的那两个：\(f(x,0) + f(x,1) + f(x,2) = \sum \limits_{k=0}^{3n-1} {k \choose x} = {3n \choose x+1}\)。

于是做完了。

\(f(0,0) = f(0,1) = f(0,2) = n\)。