[JOI合宿]2009-Day1:Sequence

循環性に気づくまでが勝負です.

まず, 奇数の数だけを知りたいので, 各数の下位ビットのみに注目します.
すると, それらの数を結合して, 2進数とみなすことができます.
鳩の巣原理っぽく考えると, 2^m個以上の相異なる項を作ることが出来ないのが分かり, かつ, ある2進数を作り出す規則は前の項に依存することより, この2進数列は循環することが分かります.

ゆえに, 実際に循環する2進数を列挙して, (1 ~ q項めの奇数の数) - (1 ~ p - 1項目の奇数の数)を求めてやれば良いです.

#include <cstdio>

using namespace std;

typedef long long ll;

bool pat[1 << 24];
bool count[1 << 24];

ll getSum(ll p)
{
    ll ret;
    ret = 0;
    for (ll i = 0; i < p; i++){
        ret += count[i];
    }
    
    return (ret);
}

int main()
{
    int m;
    ll p, q;
    ll i;
    ll bit;
    ll sum;
    
    scanf("%d", &m);
    scanf("%lld %lld", &p, &q);
    
    bit = 0;
    for (i = 0; i < m; i++){
        int t;
        scanf("%d", &t);
        bit = (bit << 1) | (t & 1);
        count[i] = t & 1;
    }
    
    i--;
    sum = 0;
    do {
        pat[bit] = true;
        count[i] = bit & 1;
        sum += count[i++];
        bit = ((bit << 1) | ((bit >> (m - 1)) ^ (bit & 1))) & ((1 << m) - 1);
    } while (pat[bit] == false);
    i -= (m - 1);
    p--;
    p = (p / i) * sum + getSum(p % i);
    q = (q / i) * sum + getSum(q % i);
    
    printf("%lld\n", q - p);
    
    return (0);
}