Epik Rəngləmə (Həll təhlili)

Həll 1

Qeyd edin ki, massivdəki cəmin yalnız iki halı var, gəlin $\sum a$ tək olduqda düşünək, cüt cəmlər üçün bütün mümkün seçimləri nəzərdən keçirək:

• \text{tək+tək=çift} və buna görə də tamamlayıcı \text{tək-çift=tək}dır.

• \text{çift+çift=çift} və buna görə də tamamlayıcı \text{tək-çift=tək}dır.

• \text{çift+tək=tək} və buna görə də tamamlayıcı \text{çift-tək=çift}dır.

Bütün konfiqurasiyalarda heç biri pariteti uyğun gəlmir, buna görə də cavab $0$-dır, əgər (\sum a \bmod 2=1).

İndi $\sum a$ çift olduqda düşünək, bütün mümkün konfiqurasiyaları nəzərdən keçirək:

• \text{tək+tək=çift} və buna görə də tamamlayıcı \text{çift-çift=çift}dır.

• \text{çift+çift=çift} və buna görə də tamamlayıcı \text{çift-çift=çift}dır.

• \text{çift+tək=tək} və buna görə də tamamlayıcı \text{çift-tək=çift}dır.

Bütün konfiqurasiyaların uyğun gəldiyini qeyd edin, buna görə də bütün cütləşmələri nəzərə alırıq ki, bu da

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

Həll 2

Hər pariteti müvafiq olanla ardıcıl cütləşdirə bilərik və hər dəfə sayını toplaya bilərik, hər dəfə tək olanları çiftlərlə cütləşdirəcəyik və sayını sadəcə toplayırıq. Bu yalnız $\sum a$ çift olduqda işləyir, əks halda 0-dır.

#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;
}

Komplekslik $O(n)$.