Fe3b0onacci Pairs (Editorial)

Solution

First , any pair which has a value $(0,x)$ or $(x,0)$ is a fe3b0onacci pair.

because \text{Fib}(x + 0) = \text{Fib}(x) = \text{Fib}(x) + 0 = \text{Fib}(x) + \text{Fib}(0) and vice versa.

now using the formula of Fibonacci number

so \text{Fib}(a_i + a_j) = \text{Fib}(a_i + a_j - 1) + \text{Fib}(a_i + a_j -2).

but we need \text{Fib}(a_i + a_j) = \text{Fib}(a_i) + \text{Fib}(a_j).

by comparing the two formulas , we will have the two following equations.

by summing the two equations.

after fixing

by giving values for a_i we can find a_j.

when a_i = 0 , a_j = 3 , which is of form $(0,x)$.

when a_i = 1 , a_j = 2 , so pair with value $(1,2)$ is a fe3b0onacci pair.

when a_i = 2 , a_j = 1 , so pair with value $(2,1)$ is a fe3bo0nacci pair.

when a_i = 3 , a_j = 0 which is of form $(x,0)$.

but there is a special case when a_i + a_j = 4

\text{Fib}(4) = \text{Fib}(3) + \text{Fib}(2).

but since \text{Fib}(2) = \text{fib(1)} = 1 , we can rewrite $\text{Fib(4)}$ as follows.

\text{Fib}(4) = \text{Fib}(3) + \text{Fib}(1) or vice versa.

so pair with value $(1,3)$ or $(3,1)$ is a fe3b0onacci pair.

so the final answer will be \frac{cnt_0 \cdot (cnt_0 - 1)}{2} + cnt_0 \cdot (n - cnt_0) + cnt_1 \cdot cnt_2 + cnt_1 \cdot cnt_3.

where cnt_i is the frequency of the value $i$ in the array.

Time complexity : $\mathcal{O}(n)$.

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define F first
#define S second
using namespace std;
const int N = 2e5 + 1;
const int M = 1e9 + 7;
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int tc = 1;
    cin>>tc;
    while(tc--)
    {
        int n;
        cin>>n;
        int a[n+1];
        int ans = 0 , cnt0 = 0 ,cnt1 = 0 , cnt2 = 0 , cnt3 = 0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            cnt0 += (a[i] == 0);
            cnt1 += (a[i] == 1);
            cnt2 += (a[i] == 2);
            cnt3 += (a[i] == 3);
        }
        ans += cnt0 * (cnt0 - 1)/2; // 0 0
        ans += cnt0 * (n - cnt0); // (0,x) , (x,0)
        ans += cnt1 * cnt2; // (1,2) , (2,1)
        ans += cnt1 * cnt3; // (1,3) , (3,1)
        cout<<ans<<endl;
    }
}