CodeForce 887 div.2 B. Fibonaccharsis 题解

题意给定斐波那契数列的长度为k，指定f[k]==n时 有多少中组合方法

知道 f[3]=f[1]+f[2] f[4]=f[1]+2*f[2] f[5]=2*f[1]+3*f[2]

所以可以看出来每一个f[i]都是由 w1个f[1]和w2个f[2]组成

所以假设k=3时    f[3]=f[1]+f[2] 我们只需要枚举f[1]和f[2]的值即可，但是由于题干中要求非减序列所以有个要求就是 f[2]<=f[3] f[1]<=f[2] 

可得 f[1]+f[2]==n 所以枚举f[1]时 f[2]=n-f[1], 可以得到 f[1]<=n-f[1] 即f[1]<=n/2 所以我们只需要在[0,n/2]的区间内枚举f[1]即可

同理 k=4时 f[1]<=n/3 n=2*f[2]+f[1]  f[2]=(n-f[1])/2 每当枚举f[1]时 (n-f[1])%2==0时便可以得到一个合法解

以此类推发现枚举的f[1]的范围和f[2]的余数也是斐波那契数列即

0 1 1 2 3 5 8 13...   

代码