Fe3b0onacci пари#12462

Fe3b0onacci пари (Розбір)

Автор задачі:	Hadi Takla (TaklaOI)
Підготував:	Hadi Takla (TaklaOI)
Відредагував:	Hadi Takla (TaklaOI)

Розв'язок

По-перше, будь-яка пара зі значенням $(0, x)$ або $(x, 0)$ є fe3b0onacci-парою.

оскільки $Fib (x + 0) = Fib (x) = Fib (x) + 0 = Fib (x) + Fib (0)$ \text{Fib}(x + 0) = \text{Fib}(x) = \text{Fib}(x) + 0 = \text{Fib}(x) + \text{Fib}(0) і навпаки.

тепер скористаємося формулою числа Фібоначчі

Fib (x) = Fib (x - 1) + Fib (x - 2)

\text{Fib}(x) = \text{Fib}(x-1) + \text{Fib}(x-2)

отже $Fib (a_{i} + a_{j}) = Fib (a_{i} + a_{j} - 1) + Fib (a_{i} + a_{j} - 2)$ \text{Fib}(a_i + a_j) = \text{Fib}(a_i + a_j - 1) + \text{Fib}(a_i + a_j -2).

але нам потрібно $Fib (a_{i} + a_{j}) = Fib (a_{i}) + Fib (a_{j})$ \text{Fib}(a_i + a_j) = \text{Fib}(a_i) + \text{Fib}(a_j).

порівнюючи дві формули, отримаємо такі два рівняння.

a_{i} = a_{i} + a_{j} - 1

a_i = a_i + a_j - 1

a_{j} = a_{i} + a_{j} - 2

a_j = a_i + a_j - 2

додавши два рівняння.

a_{i} + a_{j} = 2 \cdot a_{i} + 2 \cdot a_{j} - 3

a_i + a_j = 2\cdot a_i + 2\cdot a_j - 3

після спрощення

a_{i} + a_{j} = 3

a_i + a_j = 3

підставляючи значення для $a_{i}$ a_i, можна знайти $a_{j}$ a_j.

при $a_{i} = 0$ a_i = 0, $a_{j} = 3$ a_j = 3, що має вигляд $(0, x)$ .

при $a_{i} = 1$ a_i = 1, $a_{j} = 2$ a_j = 2, тому пара зі значенням $(1, 2)$ є fe3b0onacci-парою.

при $a_{i} = 2$ a_i = 2, $a_{j} = 1$ a_j = 1, тому пара зі значенням $(2, 1)$ є fe3bo0nacci-парою.

при $a_{i} = 3$ a_i = 3, $a_{j} = 0$ a_j = 0, що має вигляд $(x, 0)$ .

але є особливий випадок, коли $a_{i} + a_{j} = 4$ a_i + a_j = 4

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

але оскільки $Fib (2) = fib(1) = 1$ \text{Fib}(2) = \text{fib(1)} = 1, можна переписати $Fib(4)$ таким чином.

$Fib (4) = Fib (3) + Fib (1)$ \text{Fib}(4) = \text{Fib}(3) + \text{Fib}(1) або навпаки.

тому пара зі значенням $(1, 3)$ або $(3, 1)$ є fe3b0onacci-парою.

отже, остаточна відповідь дорівнює $\frac{c n t _{0} \cdot ( c n t _{0} - 1 )}{2} + c n t_{0} \cdot (n - c n t_{0}) + c n t_{1} \cdot c n t_{2} + c n t_{1} \cdot c n t_{3}$ \frac{cnt_0 \cdot (cnt_0 - 1)}{2} + cnt_0 \cdot (n - cnt_0) + cnt_1 \cdot cnt_2 + cnt_1 \cdot cnt_3.

де $c n t_{i}$ cnt_i — це частота значення $i$ в масиві.

Часова складність: $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;
    }
}