D. Yarik and Musical Notes Codeforces Round 909 (Div. 3) 1899D

Problem - D - Codeforces

题目大意：给出一个n个数的数组a，问有多少对i，j满足i

1<=n<=1e5;1<=a[i]<=1e9

思路：用快速幂打个表发现满足条件的a[i]，a[j]要么a[i]=a[j]要么一个数等于1，另一个等于2，所以我们只需对于每个数，求出它后面有多少与它相等的数，如果是1或2再特判一下后面2或1的数量。

那么我们就先求出每个数的出现次数，然后每遍历一个数，就令那个数的出现次数-1，这时这个数的出现次数就等于在他后面有多少个这个数

//#include
#include<__msvc_all_public_headers.hpp>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const ll MOD = 1e9 + 7;
ll n;
ll a[N];
ll qpow(ll a, ll b)
{//快速幂
    if (b <= 0)
        return 1;
    ll ret = 1, temp = a;
    while (b)
    {
        if (b & 1)
        {
            ret = ret * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return ret;
}
void init()
{
 
}
void solve()
{
    cin >> n;
    init();
    mapcnt;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        cnt[a[i]]++;//求每个数的出现次数
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        cnt[a[i]]--;//当前数出现次数-1
        ans += cnt[a[i]];
        if (a[i] == 1)
        {//特判1和2
            ans += cnt[2];
        }
        if (a[i] == 2)
        {
            ans += cnt[1];
        }
    }
    cout << ans;
    cout << '\n';
}
int main()
{
    /*for (int i = 1; i <= 60; i++)
    {
        for (int j = 1; j <= 60; j++)
        {
            ll temp1 = qpow(2, i), temp2 = qpow(2, j);
            if (qpow(temp1, temp2) == qpow(temp2, temp1))
            {
                cout << i << " " << j << '\n';
            }
        }
    }*/
    //打表找规律
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}