JOI 2009 春合宿 day1-1 「Sequence」

奇数＝true、偶数＝falseで周期性を見つければ良い。

#include<cstdio>
#include<vector>
#include<algorithm>
#define rep(i,n) for(int i = 0; i < n; i++)
#define pb push_back
using namespace std;

typedef long long ll;


ll n, ki;
vector<bool> s;


ll cnt(ll x){
	ll r = x/n*ki, l = x%n;
	
	rep(i,l){
		if(s[i]) r++;
	}
	
	return r;
}



int main(){
	bool a[25], b[25];
	int m, ina;
	ll p, q;
	
	scanf("%d%lld%lld",&m,&p,&q);
	
	for(int i = 1; i <= m; i++){
		scanf("%d",&ina);
		a[i] = ina%2;
		s.pb(a[i]);
		b[i] = false;
	}
	b[0] = true; n = m;
	
	
	while(1){
		s.pb(s[n-1]^s[n-m]);
		if(s[n]) ki++;
		
		for(int i = m; i >= 1; i--){
			b[i] = (b[i-1] && s[n]==a[i]) ? true : false;
		}
		
		n++;
		
		if(b[m]){
			n -= m;
			break;
		}
	}
	
	
	printf("%lld\n",cnt(q)-cnt(p-1));
	
	return 0;
}