Епічне Кольорування (Розбір)

Рішення 1

Зверніть увагу, що є лише два випадки парності суми масиву, розглянемо, коли $\sum a$ непарне, розглянемо всі можливі вибори для суми пари :

• $\text{непарне+непарне=парне}$ і, отже, комплементарне $\text{непарне-парне=непарне}$.

• $\text{парне+парне=парне}$ і, отже, комплементарне $\text{непарне-парне=непарне}$.

• $\text{парне+непарне=непарне}$ і, отже, комплементарне $\text{непарне-непарне=парне}$

Зверніть увагу, що в усіх конфігураціях жодна з них не відповідає парності, отже, відповідь дорівнює $0$, коли (\sum a \bmod 2=1).

Тепер розглянемо, коли $\sum a$ парне, ми маємо всі можливі конфігурації :

• $\text{непарне+непарне=парне}$ і, отже, комплементарне $\text{парне-парне=парне}$.

• $\text{парне+парне=парне}$ і, отже, комплементарне $\text{парне-парне=парне}$.

• $\text{парне+непарне=непарне}$ і, отже, комплементарне $\text{парне-непарне=парне}$

Зверніть увагу, що всі конфігурації відповідають, отже, ми розглядаємо всі пари, які є

Складність $O(n)$.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
    int n;cin>>n;
    vector<int>a(n);
    ll sum=0;
    for(auto &i:a){
        cin>>i;
        sum+=i;
    }
    if(sum&1){
        cout<<"0\n";
    }else{
        cout<<(ll)(n*(n-1))/2<<"\n";
    }
}
int main(){
    int t;cin>>t;
    while(t--){
        solve(); 
    }
    return 0;
}

Рішення 2

Ми можемо послідовно парувати кожну парність з відповідною і накопичувати кількість кожного разу, кожного разу ми будемо парувати парні з непарними і просто накопичувати кількість. Це працює лише тоді, коли $\sum a$ парне, в іншому випадку це 0.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
    int n;cin>>n;
    vector<int>a(n);
    int o=0;int e=0;
    ll sum=0;
    ll ans=0;
    for(auto i:a){
        cin>>i;
        sum+=i;
    }
    if(sum&1){
        cout<<"0\n";
        return;
    }else{
        for(auto i:a){
            ans+=e+o;
            if(i&1){
                e++;
            }else{
                o++;
            }
        }
    }
    cout<<ans<<"\n";
}
int main(){
    int t;cin>>t;
    while(t--){
        solve(); 
    }
    return 0;
}

Складність $O(n)$.