1.暴力

　　2.矩阵

　　3.母函数

　　设$F(x)=\sum\limits_{i=0}^{\infty} f(i)x^i$,

　　有$xF(x)=\sum\limits_{i=1}^{\infty} f(i-1)x^i$，$x^2F(x)=\sum\limits_{i=2}^{\infty} f(i-2)x^i$

　　那么$F(x)=xF(x)+x^2F(x)+x$，最后一项是$[x^1]$

　　$F(x)=\frac{x}{1-x-x^2}$，然后需要把分母的x弄掉

　　$F(x)=\frac{-x}{(x-x_0)(x-x_1)}$此处解出$x_0,x_1$

　　$F(x)=\frac{A}{x-x_0}+\frac{B}{x-x_1},A+B==-1,Ax_1+Bx_0==0$此处解出$A,B$

　　$F(x)=\frac{-A}{x_0}\frac{1}{1-\frac{x}{x_0}}+\frac{-B}{x_1}\frac{1}{1-\frac{x}{x_1}}$

　　此时分母的x已经可以去掉了，因$\frac{1}{1-x}=\sum\limits_{i=0}^{\infty} x^i$

　　$F(x)=\sum\limits_{i=0}^{\infty} (\frac{-A}{x_0^i}+\frac{-B}{x_1}^i)x^i$故$f(i)=-A(\frac{1}{x_0})^i-B(\frac{1}{x_1})^i$

　　4.特征根法