P4451 [国家集训队]整数的lqp拆分
题面
题解
考虑斐波那契数列生成函数是 (F(x)=frac{x}{1-x-x^2})
而要求的东西相当于：
[F(x)^0+F(x)^1+F(x)^2+cdots
]
的第 (n) 次项。
注意与 (frac{1}{1-F(x)}) 相等，所以直接把这个东西的化部分分式，展开就行了。
思考
这题里面生成函数的用处主要是处理 (F(x)^0+F(x)^1+F(x)^2+cdots)
还有一个关键的地方是处理和一定的某个权值乘积可以用生成函数。系数当权值，和当指数。