// head of mylib.h #include using ll = long long; using ull = unsigned long long; using pi = std::pair; #define chmin(x, a) ((x) = std::min({(x), (a)}) #define chmax(x, a) ((x) = std::max({(x), (a)}) template class V : public std::vector { typedef std::vector vector; public: using vector::begin; using vector::end; using vector::operator[]; using vector::back; using vector::clear; using vector::const_iterator; using vector::empty; using vector::erase; using vector::front; using vector::insert; using vector::iterator; using vector::pop_back; using vector::push_back; using vector::rbegin; using vector::rend; using vector::resize; using vector::size; using vector::vector; ll sum() const { ll x = 0; std::cout << "sum()" << std::endl; return x; } ll max() const { ll x = std::numeric_limits::min(); std::cout << "max()" << std::endl; return x; } ll min() const { ll x = std::numeric_limits::max(); std::cout << "min()" << std::endl; return x; } }; template using VV = V>; template std::ostream& operator<<(std::ostream& os, const V& v) { for (auto itr = v.begin(); itr != v.end();++itr) os << (itr != v.begin() ? " " : "") << *itr; os << std::endl; return os; } template std::istream& operator>>(std::istream& is, V& v) { for (auto& i : v) is >> i; return is; } void fin(const char* str){ std::cout << str << std::endl; exit(0); } // end of mylib.h using namespace std; #define MAX_LEN 2000 using bs = bitset; V prod(const V& A, const V& B, bool counted = false) { int v = A.size(); V X(v); for (int i = 0; i < v; ++i) { for (int j = A[i]._Find_first(); j < v; j = A[i]._Find_next(j)) { X[i] |= B[j]; } } // if (!counted) { // int na = 0, nb = 0; // for (int i = 0; i < v; ++i) { // na += A[i].count(); // nb += B[i].count(); // if (na > nb) return prod(B, A, true); // } // } // for (int i = 0; i < v; ++i) { // for (int j = 0; j < v; ++j) { // for (int k = A[i]._Find_first(); k < v; k = A[i]._Find_next(k)) { // if(B[k][j]){ // X[i].set(j); // break; // } // } // } // } return X; }; int doubling() { ll v, d; cin >> v >> d; d = min(d, v * 2ll); V E(v); for (auto& i : E) { string str; cin >> str; reverse(str.begin(), str.end()); i = bs(str); } const int pwrdp = 12; // 2^12 > 2V > 2^11 VV dp(pwrdp, V(v)); dp[0] = E; for (int i = 1; i < pwrdp; ++i) { dp[i] = prod(dp[i - 1], dp[i - 1]); } V Rchbl(v); for (int i = 0; i < v; ++i) Rchbl[i].set(i); for (int di = 0, dd = d; dd > 0; ++di, dd /= 2) { if (dd & 1) Rchbl = prod(Rchbl, dp[di]); } for (int i = 0; i < v; ++i) if ((ll)Rchbl[i].count() < v) return cout << "No" << endl, 0; cout << "Yes" << endl; return 0; } int normal() { int v, d; cin >> v >> d; d = min(d, v * 2); using bs = bitset; V E(v); for (auto& i : E) { string str; cin >> str; reverse(str.begin(), str.end()); i = bs(str); } for (int i = 0; i < v; ++i) { bs reachable = E[i], back1, back2; back1[i] = true; // already consumed 1 turn for reachable for (int j = 0; j < d - 1; ++j) { bs diff = reachable ^ back2; // back1 ^ back2 if (diff.none()) break; back2 = back1; for (int k = diff._Find_first(); k < v; k = diff._Find_next(k)) back1 |= E[k]; swap(reachable, back1); } if ((ll)reachable.count() < v) return cout << "No" << endl, 0; } cout << "Yes" << endl; return 0; } int main(){ doubling(); }