1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <vector>
#include <map>
#include <stack>

int mop = 1000000007;

using namespace std;

bool debug = false;

vector<int> findRanges(vector<int> &a, int start)
{
    vector<int> result;
    int sum = 0;
    for (int i = start; i < a.size(); i++)
    {
        sum = (sum + a[i]) % mop;
        if (sum % 2 == 0)
            result.push_back(i + 1);
    }
    return result;
}

int main()
{
    int n;
    cin >> n;

    vector<int> input;
    input.reserve(n);

    for (int i = 0; i < n; i++)
    {
        int k;
        cin >> k;
        input.push_back(k);
    }

    map<int, vector<int>> ranges;

    for (int i = 0; i < n; i++)
    {
        ranges[i] = findRanges(input, i);
    }

    if (debug)
    {
        for (int i = 0; i < n; i++)
        {
            cout << i << " (" << ranges[i].size() << "): ";
            for (auto elem : ranges[i])
            {
                cout << elem << " ";
            }
            cout << endl;
        }
    }

    int successes = 0;

    for (int i = 0; i < ranges[0].size(); i++)
    {
        stack<int> st;
        vector<bool> discovered;
        discovered.reserve(n);
        st.push(ranges[0][i]);
        while (!st.empty())
        {
            int p = st.top();
            st.pop();
            if (debug)
                cout << "current " << p << ", stack_size: " << st.size() << endl;
            if (p == n)
                successes = (successes + 1) % mop;
            if (!discovered[p])
            {
                discovered[p] = true;
                if (debug)
                    cout << "ranges[p].size " << ranges[p].size() << endl;
                for (int i = 0; i < ranges[p].size(); i++)
                {
                    st.push(ranges[p][i]);
                }
            }
        }
    }

    cout << successes;
}