#include "brperm.h" #include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") //#define int long long #define pii pair<int,int> #define vi vector<int> #define ff first #define ss second #define sp << " " << #define all(x) x.begin(),x.end() #define big(x) ((int)(x.size())) using namespace std; const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9,N = 5e5+1; int revbits(int x,int k) { int ans = 0; for (int j = 0;j<k;j++) { if (x&(1LL<<(k-j-1))) ans+=(1LL<<j); } return ans; } string t; vi prefa,prefb; vi apos,bpos; int go[17][N]; void init(int n, const char s[]) { while (big(t) != n) t+='0'; prefa.assign(n,0),prefb.assign(n,0); for (int j = 0;j<n;j++){ if (j) prefa[j] = prefa[j-1],prefb[j] = prefb[j-1]; t[j] = s[j]; if (t[j] == 'a') prefa[j]++,apos.push_back(j); else prefb[j]++,bpos.push_back(j); } for (int k = 0;k<=16;k++) { for (int j = 0;j<n;j++) go[k][j] = revbits(j,k); } } int query(int p, int k) { int r = p+(1LL<<k)-1; if (r >= big(t)) return 0; if (big(t) <= 1000) { for (int j = 0;j<(1LL<<k);j++) { if (t[p+j] != t[p+go[k][j]]) return 0; } return 1; } int as = prefa[r]-(p?(prefa[p-1]):0ll); int bs = prefb[r]-(p?(prefb[p-1]):0ll); if (min(as,bs) > 100) return 0; int cur = p-1; if (as <= bs) { while (1) { auto it = upper_bound(all(apos),cur); if (it == apos.end() || *it > r) break; if (t[p+revbits(*it-p,k)] != t[*it]) return 0; cur = *it; } } else { while (1) { auto it = upper_bound(all(bpos),cur); if (it == bpos.end() || *it > r) break; if (t[p+go[k][*it-p]] != t[*it]) return 0; cur = *it; } } return 1; }