题目大意
对于一个类斐波那契数列，有以下定义：
- 满足单调递增；
- 每一项均为非负整数；
- \(f_n = f_{n - 1} + f_{n - 2}\)。
求有多少个类斐波那契数列满足 \(f_k = n\)，其中 \(t, n \le 2 \times 10^5\)，\(k \le 10^9\)。
思路
\(k\) 的范围十分吓人，但我们发现，斐波那契数列的第 \(28\) 项是 \(317811\)，显然已经超过了 \(2 \times 10^5\) 这个范围。
但还要考虑我们这个数列不是真正的斐波那契数列，可以有第一项为 \(0\) 的情况，每一项会整体后移一位，所以当 \(k \geq 29\) 时，答案为 \(0\)。
那么我们现在只需要考虑 \(k \leq 28\) 的情况了，直接枚举前两项显然是不现实的，我们考虑换一个思路。
显然，对于这个数列，我们只要有其中两个相邻项的值，就可以递推求出每一项的值。
那我们可以枚举第 \(k-1\) 项的值，递推求出前两项的值，判断前两项是否合法（非递减且为非负整数序列）。
Code
void Work() {
cin >> n >> k;
if(k >= 29) {
cout << "0\n";
return ;
}
f[k] = n;
for(int i = 1;i <= n; i++) {
f[k - 1] = i;
for(int j = k - 2;j >= 1; j--)
f[j] = f[j + 2] - f[j + 1];
if(f[2] >= f[1] && f[1] >= 0)
ans ++;
}
cout << ans << "\n";
return ;
}