奇数=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; }