\(A_i = A_{i - 1} + A_{i - m}\) から、ある整数 \(\alpha\) について、 \(i = 1,\,2,\,\ldots,\,m\) について \(A_{i + \alpha} = A_i\) であれば、任意の \(j \geq \alpha\) について \(A_j = A_{j - \alpha}\) であることがわかります。
また、題を解くためには、各 \(A_i\) について、その奇偶がわかっていれば良いので、 \(\text{mod}\, 2\) 上で \(A_i\) を計算しても問題ありません。

よって、\(\text{mod} \,2\) 上では \(A_i\) についてある整数 \(a,\, b\) が存在して、任意の非負整数 \(k\) に対して \(A_{a + kb} = A_a \) が成り立ちます。
また、\(\text{mod}\,2\) 上では \(\{A_{i + 1},\,A_{i + 2},\,\ldots,\,A_{i + m}\}\) のとりうる値は高々 \(2^m\) 通りなので、\(a ,\,b \leq 2^m\) です。

第 \(1\) 項から第 \(x\) 項までの奇数の個数を \(N_x\) とすると、求める値は \(N_q - N_{p - 1}\) です。また、上の \(a, \,b\) や第 \(a\) 項から第 \(a + b - 1\) 項までの奇数の個数を前もって計算しておくことで、\(N_x\) は \(O(a + b)\) で計算できます。

以上から、この問題を \(O(a + b) = O(2^m)\) で計算することができました。
実際には \(a,\,b\) の値は \(2^m\) よりもかなり小さいので、この解法で十分制限時間内に計算することができます。

実装例

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int M;
ll calc(vector<int>& vc, int s, int fl, ll x, ll a) {
    ll ret = 0;
    if (a < vc.size()) {
        for (int i = 0; i < a; i ++) {
            ret += s % 2;
            s = (s >> 1) + (((s & 1) ^ ((s >> (M - 1)) & 1)) << (M - 1));
        }
        return ret;
    }
    for (int i = 0; i < fl; i ++) {
        ret += s % 2;
        s = (s >> 1) + (((s & 1) ^ ((s >> (M - 1)) & 1)) << (M - 1));
    }
    ret += x * ((a - fl) / (vc.size() - fl));
    for (int i = 0; i < ((a - fl) % (vc.size() - fl)); i ++) {
        ret += s % 2;
        s = (s >> 1) + (((s & 1) ^ ((s >> (M - 1)) & 1)) << (M - 1));
    }
    return ret;
}
int main () {
    ll p, q;
    cin >> M >> p >> q;
    int s = 0;
    for (int i = 0; i < M; i ++) {
        int a;
        cin >> a;
        s += ((a & 1) << i);
    }
    vector<int> vc;
    vector<bool> usd(1 << M);
    for (int i = 0; i < (1 << M); i ++) {
        usd[i] = false;
    }
    int x = s;
    ll sum = 0;
    while (!usd[x]) {
        usd[x] = true;
        vc.push_back(x);
        sum += x % 2;
        x = (x >> 1) + (((x & 1) ^ ((x >> (M - 1)) & 1)) << (M - 1));
    }
    int fl = 0;
    while (vc[fl] != x) {
        sum -= vc[fl] % 2;
        fl ++;
    }
    cout << calc(vc, s, fl, sum, q) - calc(vc, s, fl, sum, p - 1) << endl;
}