Coloreado Épico (Editorial)

Solución 1

Observe que solo hay dos casos de paridad de la suma del arreglo, consideremos cuando $\sum a$ es impar, consideremos todas las elecciones posibles para la suma de pares:

• $\text{impar+impar=par}$ y por lo tanto el complementario es $\text{impar-par=impar}$.

• $\text{par+par=par}$ y por lo tanto el complementario es $\text{impar-par=impar}$.

• $\text{par+impar=impar}$ y por lo tanto el complementario es $\text{impar-impar=par}$

Observe que en todas las configuraciones ninguna de ellas coincide con la paridad, por lo tanto la respuesta es $0$ cuando (\sum a \bmod 2=1).

Ahora consideremos cuando $\sum a$ es par, tenemos todas las configuraciones posibles:

• $\text{impar+impar=par}$ y por lo tanto el complementario es $\text{par-par=par}$.

• $\text{par+par=par}$ y por lo tanto el complementario es $\text{par-par=par}$.

• $\text{par+impar=impar}$ y por lo tanto el complementario es $\text{par-impar=par}$

Observe que todas las configuraciones coinciden, por lo tanto consideramos todas las combinaciones que son

Complejidad $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;
}

Solución 2

Podemos emparejar secuencialmente cada paridad con su correspondiente y acumular el conteo cada vez, cada vez emparejaremos pares con impares y acumularemos el conteo simplemente. Solo esto funciona cuando $\sum a$ es par, de lo contrario es 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;
}

Complejidad $O(n)$.