#line 2 "library/template/template.hpp" // repo: https://github.com/kumacs/library-cpp // docs: https://kumacs.github.io/library-cpp #include using namespace std; #line 2 "library/template/macro.hpp" #define rep(i, a, b) for (int i = (a); i < (int)(b); i++) #define rrep(i, a, b) for (int i = (int)(b) - 1; i >= (a); i--) #define ALL(v) (v).begin(), (v).end() #define UNIQUE(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end()) #define SZ(v) (int)v.size() #define MIN(v) *min_element(ALL(v)) #define MAX(v) *max_element(ALL(v)) #define LB(v, x) int(lower_bound(ALL(v), (x)) - (v).begin()) #define UB(v, x) int(upper_bound(ALL(v), (x)) - (v).begin()) #define YN(b) cout << ((b) ? "YES" : "NO") << "\n"; #define Yn(b) cout << ((b) ? "Yes" : "No") << "\n"; #define yn(b) cout << ((b) ? "yes" : "no") << "\n"; #line 10 "library/template/template.hpp" #line 2 "library/template/util.hpp" using uint = unsigned int; using ll = long long int; using ull = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; template using priority_queue_asc = priority_queue, greater>; template S SUM(const vector& a) { return accumulate(ALL(a), S(0)); } template inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin_opt(optional& a, T2 b) { if (!a || a > b) { a = b; return true; } return false; } template inline bool chmax_opt(optional& a, T2 b) { if (!a || a < b) { a = b; return true; } return false; } template int popcnt(T x) { return __builtin_popcountll(x); } template int topbit(T x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } template int lowbit(T x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } #line 12 "library/template/template.hpp" #line 2 "library/template/inout.hpp" struct Fast { Fast() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); } } fast; ostream& operator<<(ostream& os, __uint128_t x) { char buf[40]; size_t k = 0; while (x > 0) buf[k++] = (char)(x % 10 + '0'), x /= 10; if (k == 0) buf[k++] = '0'; while (k) os << buf[--k]; return os; } ostream& operator<<(ostream& os, __int128_t x) { return x < 0 ? (os << '-' << (__uint128_t)(-x)) : (os << (__uint128_t)x); } template ostream& operator<<(ostream& os, const array& a); template istream& operator>>(istream& is, pair& p) { return is >> p.first >> p.second; } template ostream& operator<<(ostream& os, const pair& p) { return os << p.first << " " << p.second; } template istream& operator>>(istream& is, vector& a) { for (auto& v : a) is >> v; return is; } template ostream& operator<<(ostream& os, const vector& a) { for (auto it = a.begin(); it != a.end();) { os << *it; if (++it != a.end()) os << " "; } return os; } template ostream& operator<<(ostream& os, const array& a) { for (auto it = a.begin(); it != a.end();) { os << *it; if (++it != a.end()) os << " "; } return os; } template ostream& operator<<(ostream& os, const set& st) { os << "{"; for (auto it = st.begin(); it != st.end();) { os << *it; if (++it != st.end()) os << ","; } os << "}"; return os; } template ostream& operator<<(ostream& os, const map& mp) { os << "{"; for (auto it = mp.begin(); it != mp.end();) { os << it->first << ":" << it->second; if (++it != mp.end()) os << ","; } os << "}"; return os; } void in() {} template void in(T& t, U&... u) { cin >> t; in(u...); } template void in_zip(int n, T&... t) { assert(n >= 0 && ((size(t) >= static_cast(n)) && ...)); for (int i = 0; i < n; i++) in(t[i]...); } void out() { cout << "\n"; } template void out(const T& t, const U&... u) { cout << t; if (sizeof...(u)) cout << sep; out(u...); } template void out_opt(const optional& opt, const U& fallback, ostream& os = cout) { if (opt.has_value()) os << opt.value(); else os << fallback; os << "\n"; } template void out_opt(const vector>& vec, const U& fallback, ostream& os = cout) { for (auto it = vec.begin(); it != vec.end();) { if ((*it).has_value()) os << (*it).value(); else os << fallback; if (++it != vec.end()) os << " "; } os << "\n"; } namespace IO { template T read(U&&... u) { T t = T(forward(u)...); in(t); return t; } namespace Graph { vector> unweighted(int n, int m, bool directed = false, int offset = 1) { vector> g(n); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; u -= offset, v -= offset; g[u].push_back(v); if (!directed) g[v].push_back(u); } return g; } template vector>> weighted(int n, int m, bool directed = false, int offset = 1) { vector>> g(n); for (int i = 0; i < m; i++) { int u, v; T w; cin >> u >> v >> w; u -= offset, v -= offset; g[u].push_back({v, w}); if (!directed) g[v].push_back({u, w}); } return g; } } // namespace Graph namespace Tree { vector> unweighted(int n, bool directed = false, int offset = 1) { return Graph::unweighted(n, n - 1, directed, offset); } template vector>> weighted(int n, bool directed = false, int offset = 1) { return Graph::weighted(n, n - 1, directed, offset); } vector> rooted(int n, bool to_root = true, bool to_leaf = true, int offset = 1) { vector> g(n); for (int i = 1; i < n; i++) { int p; cin >> p; p -= offset; if (to_root) g[i].push_back(p); if (to_leaf) g[p].push_back(i); } return g; } } // namespace Tree } // namespace IO #line 14 "library/template/template.hpp" #line 2 "library/template/debug.hpp" #ifdef LOCAL #define debug 1 #define show(...) _show(0, #__VA_ARGS__, __VA_ARGS__) #else #define debug 0 #define show(...) true #endif template void _show(int, T) { cerr << '\n'; } template void _show(int i, const T1& a, const T2& b, const T3&... c) { for (; a[i] != ',' && a[i] != '\0'; i++) cerr << a[i]; cerr << ":" << b << " "; _show(i + 1, a, c...); } #line 2 "main.cpp" #line 2 "library/automaton/dfa-infer.hpp" #line 2 "library/automaton/dfa.hpp" template class DFA { using t_dfa = DFA; static const int c_size = c_max - c_min + 1; public: DFA() {} DFA(int size, int start) : _size(size), _start(start), _final(size, false), map(size, vector(c_size, -1)) {} DFA(int size, int start, const vector>& map_) : _size(size), _start(start), _final(size, false), map(map_) {} DFA(int size, int start, const vector final_, const vector>& map_) : _size(size), _start(start), _final(final_), map(map_) {} void set(int p, char c, int q) { map[p][c - c_min] = q; } int get(int p, char c) const { return map[p][c - c_min]; } void set_final(int p, bool f) { _final[p] = f; } bool get_final(int p) const { return _final[p]; } template bool run(const S& s) const { int x = _start; for (auto c : s) x = get(x, c); return get_final(x); } t_dfa normalize() { vector seen(_size, false); vector index(_size, -1); vector states; queue qu; qu.push(_start); while (!qu.empty()) { int x = qu.front(); qu.pop(); seen[x] = true; index[x] = states.size(); states.push_back(x); for (int j = 0; j < c_size; j++) { int y = map[x][j]; if (seen[y]) continue; seen[y] = true; qu.push(y); } } int size1 = states.size(); vector final1(size1, false); for (int i = 0; i < size1; i++) final1[i] = _final[states[i]]; vector> map1(size1, vector(c_size, -1)); for (int i = 0; i < size1; i++) for (int j = 0; j < c_size; j++) map1[i][j] = index[map[states[i]][j]]; return t_dfa(size1, index[_start], final1, map1); } t_dfa minimize() { vector partition(_size, -1); { int accept = -1, reject = -1; for (int i = 0; i < _size; i++) if (_final[i]) partition[i] = accept == -1 ? (accept = i) : accept; else partition[i] = reject == -1 ? (reject = i) : reject; } vector partition_new(_size, -1); while (true) { fill(partition_new.begin(), partition_new.end(), -1); for (int i = 0; i < _size; i++) { if (partition_new[i] != -1) continue; partition_new[i] = i; for (int j = i + 1; j < _size; j++) if (partition[i] == partition[j] && equivalent(i, j, partition)) partition_new[j] = i; } if (partition == partition_new) break; swap(partition, partition_new); } int size1 = 0; vector index(_size, -1), leader; vector final1; for (int i = 0; i < _size; i++) if (partition[i] == i) { index[i] = size1++; leader.push_back(i); final1.push_back(_final[i]); } else { index[i] = index[partition[i]]; } vector> map1(size1, vector(c_size, -1)); for (int i = 0; i < size1; i++) for (int j = 0; j < c_size; j++) map1[i][j] = index[map[leader[i]][j]]; return t_dfa(size1, index[_start], final1, map1).normalize(); } bool operator==(const t_dfa& d) const { if (_size != d._size) return false; if (_start != d._start) return false; if (_final != d._final) return false; return map == d.map; } int size() { return _size; } int start() { return _start; } private: int _size, _start; vector _final; vector> map; bool equivalent(int i, int j, const vector& partition) { if (i == j) return true; for (int k = 0; k < c_size; k++) if (partition[map[i][k]] != partition[map[j][k]]) return false; return true; } }; /** * @brief 決定性有限オートマトン(DFA) * @docs docs/automaton/dfa.md */ #line 4 "library/automaton/dfa-infer.hpp" template DFA DFAInfer(int n, const vector& accepted) { static_assert(c_min <= c_max); assert(n >= 0); constexpr int c_size = c_max - c_min + 1; vector> to(1, vector(c_size, -1)); vector final(1, false); for (const auto& s : accepted) { assert(s.size() <= (size_t)n); int p = 0; for (char c : s) { int k = c - c_min; assert(0 <= k && k < c_size); if (to[p][k] == -1) { to[p][k] = to.size(); to.emplace_back(c_size, -1); final.push_back(false); } p = to[p][k]; } final[p] = true; } int sink = to.size(); to.emplace_back(c_size, sink); final.push_back(false); int size = to.size(); for (auto& row : to) for (auto& q : row) if (q == -1) q = sink; vector depth(size, -1), order{0}; depth[0] = 0; for (int i = 0; i < (int)order.size(); i++) for (int q : to[order[i]]) if (depth[q] == -1) { depth[q] = depth[order[i]] + 1; order.push_back(q); } // gap[p][q - p] は受理結果を区別する最短接尾辞長.区別できなければ size. vector> gap(size); for (int p = size - 1; p >= 0; p--) { gap[p].assign(size - p, size); for (int q = p + 1; q < size; q++) { int& d = gap[p][q - p]; if (final[p] != final[q]) { d = 0; } else { for (int c = 0; c < c_size; c++) { int a = to[p][c], b = to[q][c]; if (a > b) swap(a, b); d = min(d, gap[a][b - a] + 1); } } } } vector index(size, -1), states; for (int q : order) { for (int p : states) { int a = min(p, q), b = max(p, q), d = gap[a][b - a]; if (d == size || d > n - depth[q]) { index[q] = index[p]; break; } } if (index[q] == -1) { index[q] = states.size(); states.push_back(q); } } int size1 = states.size(); vector final1(size1); vector> to1(size1, vector(c_size)); for (int i = 0; i < size1; i++) { final1[i] = final[states[i]]; for (int c = 0; c < c_size; c++) to1[i][c] = index[to[states[i]][c]]; } return DFA(size1, 0, final1, to1); } /** * @brief 短い文字列の受理集合からの DFA 推定 */ #line 4 "main.cpp" void solve() { const int N = 10; set ac{"1"}; rep(k, 2, N + 1) { string S(k, '0'); string T(k - 1, '0'); rep(f, 0, 1 << k) { rep(i, 0, k) S[i] = '0' + ((f >> i) & 1); rep(j, 0, k - 1) { if (S[j] != S[j + 1]) continue; rep(i, 0, k) T[i - (i > j)] = S[i]; T[j] ^= 1; if (ac.contains(T)) { ac.insert(S); break; } } } } vector ac_vec(ALL(ac)); auto dfa = DFAInfer<'0', '1'>(N, ac_vec); int T; in(T); rep(_, 0, T) { int N; string S; in(N, S); Yn(dfa.run(S)); } } int main() { int T = 1; // in(T); while (T--) solve(); }