How to find all the contiguous subsequence of an array is less than O(N^2) time complexity?
A contiguous subsequence satisfies your conditions if either it consists only of odd elements, or it contains one number which is a multiple or 4, or it contains two numbers which are multiples of 2. This suggests computing the following quantities:


$X$: Number of contiguous subsequences consisting only of odd elements.
$Y$: Number of contiguous subsequences containing an even element.
$Z$: Number of contiguous subsequences containing no element which is a multiple of 4, and exactly one even element which is not a multiple of 4.


You are interested in $X+Y-Z$.

To determine $X,Y$, it suffices to partition the elements into odd (O) and even (E). If your sequence is of the form
$$
O^{\ell_1} E O^{\ell_2} E \cdots O^{\ell_r} E O^{\ell_{r+1}},
$$
then
$$
X = \sum_{i=1}^{r+1} \binom{\ell_i+1}{2}, \\
Y = \sum_{1 \leq i &lt; j \leq r+1} (\ell_i+1) (\ell_j+1).
$$
In order to compute $Y$ quickly, note that
$$
2Y = \left(\sum_{i=1}^{r+1} (\ell_i+1)\right)^2 - \sum_{i=1}^{r+1} (\ell_i+1)^2.
$$

In order to compute $Z$, we first separate our sequence by breaking at every element which is a multiple of 4. If $Z_j$ is the number of $Z$-type contiguous subsequences in the $j$th subsequence, then $Z = Z_j$. We can write the $j$th subsequence as
$$
O^{\ell_1} E O^{\ell_2} E \cdots O^{\ell_r} E O^{\ell_{r+1}},
$$
just as before. We then have
$$
Z_j = \sum_{i=1}^r (\ell_i+1) (\ell_{i+1}+1).
$$
In total, the algorithm runs in linear time.

Disclaimer: Verify that the formulas work – they might be slightly off, but the general idea should work.