买水喝
　　小PP超喜欢喝水，所以他就去买水了。
　　商店里有 5 种水
　　第 1 种：商店里有无数瓶
　　第 2 种：商店里只有一瓶
　　第 3 种：商店里竟然有 4 瓶 。
　　第 4 种： 5 瓶5 瓶一包卖的
　　第 5 种： 2 瓶 2 瓶一包卖的
　　好奇心极强的小PP想买 n 瓶水，他想知道他有多少种买法。
样例输入
1
输出
3
数据规模
对于10%的数据，n<=10
对于20%的数据，n<=100000
对于100%的数据，n<=2147483647

writeln((n+1)*(n+2) div 2) 是可以水过的（找规律）
求推论 科学解法

本人初中渣 请不要太高中化来解释

我先说下我一般想法，推论本人不很擅长，晚点如果成功推导会再回帖的。
易知初值f[0]=1，其余皆为0.
首先不管2、3两种的话，递推式很好写：f[i]=f[i-1]+f[i-2]+f[i-5]。
然后只有2、3搭配的情况有
（空集）
2
23
233
2333
23333
3
33
333
3333
买0、1、2、3、4、5瓶的情况分别有1、2、2、2、2、1种。
Ans=f[n]+2f[n-1]+2f[n-2]+2f[n-3]+2f[n-4]+f[n-5]。
一看n很大绝对超时空，没关系矩阵乘法快速幂logn秒之。
另附矩阵：
a
b
c
d
e
×
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 0 1 1
=
b
c
d
e
a+d+e
另外要说的其实我也蒟蒻，不然行列式列出必然秒杀，因为数学计算不太会，迟迟无法得出结果。希望能帮到你

小pp

同问