2020ICPC上海 Fibonacci（水过）

本文主要是介绍2020ICPC上海 Fibonacci（水过），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

康复训练，水水代码证明我还活着。

思路：
可以发现斐波那契数列数列是奇奇偶、奇奇偶这样排列的。
所以3个数分为一组，假设为$k$组。
偶数和后面的数组合的$g$值都为1。
第一个偶数有$n-3$个组合
第二个有$n-3\ast 2$个组合
第三个有$n-3\ast 3$个组合
。。。
直到最后一个有$n-3\ast k$个组合
等差数列求和算出偶数贡献为$\frac{2\ast n-3-3\ast k}{2}$

奇数只能和后面偶数求和，
前两个奇数有$2\ast k$个组合
3、4个奇数有$2\ast (k-1)$个组合
…
也是一样的等差数列求和算出奇数贡献为$\frac{(2k+2)\ast k}{2}$

所以总贡献为$\frac{2\ast n-3-3\ast k}{2}+\frac{(2k+2)\ast k}{2}$

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;
const int maxn = 2e3 + 7;
typedef long long ll;int main() {ll n;scanf("%lld",&n);ll k = n / 3;ll ans = (2 * n - 3 - 3 * k) * k / 2;ans += (2 * k + 2) * k / 2;printf("%lld\n",ans);return 0;
}

这篇关于2020ICPC上海 Fibonacci（水过）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---