P9825 [ICPC2020 Shanghai R] Fibonacci 题解

· · 个人记录

前言。

斐波那契数列真是考吐了。

分析。

给定正数 n 然后计算所以满足 n\leq i<j\leq n 中斐波那契数列中的 f_i\times f_j 为偶数的所有 \left(i,j\right) 的个数。

换种说法，就是将当前斐波那契数 f_i 分别与其后面到 n 的数相乘，求有多少种可能的一对数的值为偶数。

斐波那契的数列的定义不再赘述，这里提供一个思路。

我们给出下面的一段斐波那契数列： 

1 1 2   3 5 8   13 21 34  55

其中对应的斐波那契数与其后面的数的乘积为偶的个数是： 

3 3 7   2 2 4   1  1  1    0

很明显，如果让两个数相乘，则只需要其中一个数为偶数即可。因为偶数乘偶数为偶数，奇数乘偶数也为偶数。

因为斐波那契数列中的第一项与第二项均为 1 为奇数，第三项为 2 是偶数，则第四项 f_4=f_2+f_3=2+1=3 为奇数，第五项 f_5=f_3+f_4=2+3=5 为奇数，第六项 f_6=f_5+f_4=5+3=8 为偶数。由此类推，将斐波那契数列每三个分成一组，则前两个为奇数，后两个为偶数。因为每组前两个的计算为奇数加偶数，每组最后一个数是两个奇数相加。

下文中的“组”的定义均为 3 个斐波那契数为一组。

在此回到上面的例子，我们分开讨论。首先看奇数，很明显为 3,2,1 的等差数列。推广到 n 的情况，因为奇数只有乘偶数才能为偶数，所以在这个斐波那契数列中，在这个奇数后面有几个划分的组再加上它自己这个组就有几个答案。原因是每个组中都有且仅有一个偶数。

设能分成 Q 组。

因为每组有两个，所以 \times 2 再套上等差数列的公式 \frac{Q\times\left(1+Q\right)}{2} 就可以得到奇数能匹配的个数为 Q\times\left(1+Q\right) 个。

设余下的数的个数为 Z 则可以同理推出偶数向后匹配的个数为 Q\times Z+\left(\left(Q-1\right)\times 3\times Q\right)/2 的公式。因为余下的一定为奇数，所以有 Q\times Z 个，偶数的计算可以顺着奇数的推。

代码如下，仅供参考：

#include<iostream>
using namespace std;
unsigned long long n;
int main(){
    cin>>n;
    //ji ji ou ji ji ou.....
    unsigned long long a=n%3;
    unsigned long long b=n/3;
    unsigned long long ans;
    ans=b*(b+1)+a*b+(b-1)*3*b/2;
    cout<<ans<<"\n";
    return 0;
}

后记。

大家如有疑问，可以在评论区提出，我会尽力解答的。