Code python của em:
n = int(input())
arr = [int(_) for _ in input().split(' ')]
evenOdd = 0
oddEven = 0
oddOdd = 0
evenEven = 0
answer = (1 if (arr[0] + arr[1] + arr[2]) % 2 == 0 else 0)
odd = 0
even = 0
for i in range(3):
if arr[i] % 2 == 0:
even += 1
else:
odd += 1
for i in range(3):
for j in range(i + 1, 3):
if arr[i] % 2 == 0 and arr[j] % 2 == 0:
evenEven += 1
elif arr[i] % 2 == 0 and arr[j] % 2 == 1:
evenOdd += 1
elif arr[i] % 2 == 1 and arr[j] % 2 == 0:
oddEven += 1
else:
oddOdd += 1
if (arr[0] + arr[1] + arr[2]) % 2 == 0:
if arr[1] % 2 == 0 and arr[2] % 2 == 0:
evenEven += 1
elif arr[1] % 2 == 0 and arr[2] % 2 == 1:
evenOdd += 1
elif arr[1] % 2 == 1 and arr[2] % 2 == 0:
oddEven += 1
else:
oddOdd += 1
for i in range(3, n):
if arr[i] % 2 == 0:
answer = (answer + oddOdd + evenEven) % 998244353
oddEven += (oddOdd + odd) % 998244353
evenEven += (evenEven + even) % 998244353
even += 1
else:
answer = (answer + oddEven + evenOdd) % 998244353
evenOdd += (oddEven + even) % 998244353
oddOdd += (evenOdd + odd) % 998244353
odd += 1
print(answer)
Đối với input
11
3 1 4 1 5 9 2 6 5 3 6
Kết quả đúng là 386, trong khi của em là 686. Không biết em đếm dư ở đâu nhỉ? Ý tưởng của em là giữ số đếm của các subsequence kết thúc bằng chẵn-lẻ, chẵn-chẵn, lẻ-lẻ, lẻ-chẵn có độ dài >= 2 và số đếm số lượng chẵn lẻ để update tụi nó.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?