посчитать количество продуктов всех возможных подмассивов, где продукт должен делиться на четыре или это нечетное

Question

Я пытался подсчитать количество продуктов, которые нечетны или делятся на 4, сгенерированные всеми возможными подмассивами, но моя реализация получила O (n ^ 2) .... мне нужно в O (n) время. Я также пытался получить какой-то шаблон, но не могу найти его здесь, мой код

#include<bits/stdc++.h>
#define lli long long int
using namespace std;
int main()
{
    lli testcases,x,M=1000000007;
    cin>>testcases;
    for(x=0;x<testcases;x++){
        lli n,i,j,temp,count1=0;
        cin>>n;
        vector<lli>v;
        for(i=0;i<n;i++){
            cin>>temp;
            v.push_back(temp);
        }
        for(i=0;i<n-1;i++){
            if(v[i]%2!=0 || v[i]%4==0){
                ++count1;
            }
            temp=v[i];
            for(j=i+1;j<v.size();j++){
                temp*=v[j];
                if(temp%2!=0 || temp%4==0){
                    ++count1;
                }
            }
        }
        if(v[n-1]%2!=0 || v[n-1]%4==0){
            ++count1;
        }
        cout<<count1<<"\n";
        count1=0;
    }
    return 0;
}

заранее спасибо!

Answer 1

Вопрос состоит в том, чтобы задать количество подмассивов, произведение которых нечетно (нулевые коэффициенты в два) или кратно четырем (как минимум два фактора в два). Мы также можем инвертировать это: взять число подмассивов (2 ** N) и вычесть количество подмассивов, которые имеют ровно один коэффициент два.

Итак, сначала выполните предварительную обработку массива и замените каждое число его коэффициентами двух (ie 7 становится 0, 8 становится 3, et c). Тогда возникает вопрос «сколько подмассивов суммируется ровно в одно», что имеет известное решение.

Answer 2

этот вопрос напрямую связан с (длинным вызовом) от codechef. Я не думаю, что это хорошая идея, чтобы спросить прямо здесь до закрытия конкурса (15:00, 13/04/2020). Пожалуйста, соблюдайте правила кодекса. Вы можете проверить по этой ссылке, если вы не верите моим словам.
https://www.codechef.com/APRIL20B/problems/SQRDSUB или непосредственно посетите вызов Codechef в апреле (подпоследовательность в квадрате).