Coloration Épique (Corrigé)

Solution 1

Remarquez qu'il n'y a que deux cas de parité de la somme du tableau, considérons quand $\sum a$ est impair, considérons tous les choix possibles pour la somme des paires :

• $\text{impair+impair=pair}$ et donc le complémentaire est $\text{impair-pair=impair}$.

• $\text{pair+pair=pair}$ et donc le complémentaire est $\text{impair-pair=impair}$.

• $\text{pair+impair=impair}$ et donc le complémentaire est $\text{impair-impair=pair}$

Remarquez qu'aucune des configurations ne correspond à la parité, donc la réponse est $0$ quand (\sum a \bmod 2=1).

Maintenant, considérons quand $\sum a$ est pair, nous avons toutes les configurations possibles :

• $\text{impair+impair=pair}$ et donc le complémentaire est $\text{pair-pair=pair}$.

• $\text{pair+pair=pair}$ et donc le complémentaire est $\text{pair-pair=pair}$.

• $\text{pair+impair=impair}$ et donc le complémentaire est $\text{pair-impair=pair}$

Remarquez que toutes les configurations correspondent, donc nous considérons tous les appariements qui est

Complexité $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;
}

Solution 2

Nous pouvons appairer séquentiellement chaque parité avec sa correspondante et accumuler le compte à chaque fois, chaque fois nous appairons les pairs avec les impairs et nous accumulons simplement le compte. Cela ne fonctionne que lorsque $\sum a$ est pair, sinon c'est 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;
}

Complexité $O(n)$.