[nguyen minh duc]

Cho dãy n số nguyên không âm a1, a2, an. Người ta tiến hành chọn ra 2 chỉ số i, j sao cho i < j

Và xóa khỏi dãy 2 số ai, aj để tổng giá trị các số còn lại trong dãy là số chẵn.

Yêu cầu: Cho dãy số a1, a2, an. Hãy đếm số lượng cách chọn 2 chỉ số i, j thỏa mãn. Hai cách chọn khác nhau nếu tồn tại một chỉ số khác nhau.

Dữ liệu nhập: gồm 2 dòng

- Dòng 1: Chứa số nguyên n (2 ≤ n ≤ 106)

- Dòng 2: Chứa n số nguyên không âm a1, a2, an (0 ≤ ai ≤ 109)

Dữ liệu xuất:

- Là một số nguyên cho biết số cách chọn 2 chỉ số i, j thỏa mãn.

Thuật toán:

• Ta sẽ đếm số lượng các số chẵn và lẻ trong dãy, đồng thời xác định tổng các phần tử trong dãy là lẻ hay chẵn.
  
• Nếu tổng của dãy là một số lẻ, tức là ta phải xóa một số lẻ và 1 số chẵn để tổng trở về chẵn. ⇒ Với c số chẵn và l số lẻ, là có số lượng các cặp có thể xóa là c*l.
  
• Nếu tổng của dãy là một số chẵn, ta phải xóa 2 số chẵn hoặc 2 số lẻ. Tức tổng số cách xóa sẽ bằng tổng số cách chọn ra 2 phần tử chẵn hoặc 2 phần tử lẻ từ 2 tập c và l.
  
• Xét riêng từng tập c và l, ví dụ tập c có 5 phần tử, khi thêm một phần tử nữa vào tập thì ta sẽ có thêm 5 cách ghép phần tử thứ 6 đó với 5 phần tử kia. Tức tổng quát, với n phần tử, ta sẽ có 1+2+.. +n-1 cách chọn 2 phần tử bất kỳ.

Code:

#include <bits/stdc++.h>
using namespace std;

long long int a, n, anschan, ansle, chan, le, fn;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("xoso.inp", "r", stdin);
    //freopen("xoso.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a;
        if (!(a%2)) chan++; else le++;
        fn = (fn+a)%2;
    }
    if (fn) cout << chan*le; else{
        for (int i = 1; i < chan; i++) anschan += i;
        for (int i = 1; i < le; i++) ansle += i;
        cout << anschan + ansle;
    }
    //cout << " " << fn;

    return 0;
}