#include int ri() { int n; scanf("%d", &n); return n; } std::string solve(int n, int x, const std::vector &a_) { auto a = a_; if (n == 1) { std::string s(x, '0'); if (a[0] <= x) s[a[0] - 1] = '1'; return s; } std::sort(a.begin(), a.end()); int64_t prod = 1; for (int i = 0; i < n; i++) { prod *= a[i] + 1; if (prod > x + 1) return std::string(x, '0'); } if (std::count(a.begin(), a.end(), 1)) { std::string res(x, '0'); for (int i = prod - 1; i <= x; i++) res[i - 1] = '1'; return res; } std::map nums; for (auto i : a) nums[i]++; std::vector > all; for (auto i : nums) all.push_back(i); std::map, std::vector > dp; int m = nums.size(); for (int i = 0; i < m; i++) { std::vector num(all.size()); num[i] = 1; int size = x + 1; for (int j = 0; j < m; j++) for (int k = 0; k < all[j].second - num[j]; k++) size /= all[j].first; std::vector val(size); assert(all[i].first < size); val[all[i].first] = true; dp[num] = val; } for (auto &i : dp) { /* std::cerr << "key:"; for (auto j : i.first) std::cerr << j << " "; std::cerr << std::endl << "val:"; for (auto j : i.second) std::cerr << j << " "; std::cerr << std::endl;*/ for(auto &j : dp) { bool cont = true; std::vector new_num(m); for (int k = 0; k < m; k++) if ((new_num[k] = i.first[k] + j.first[k]) > all[k].second) { cont = false; break; } if (!cont) continue; int new_size = x + 1; for (int k = 0; k < m; k++) for (int l = 0; l < all[k].second - new_num[k]; l++) new_size /= all[k].first; std::vector new_val(new_size); for (int k = 1; k < (int) i.second.size(); k++) { if (!i.second[k]) continue; std::vector tmp(new_size); for (int l = 1; l < (int) j.second.size(); l++) { if (!j.second[l]) continue; int64_t base = (int64_t) (k + 1) * (l + 1) - 1; if (base < new_size) tmp[base] = true; } for (int l = 0; l < new_size - k; l++) if (tmp[l]) tmp[l + k] = true; for (int l = 0; l < new_size; l++) if (tmp[l]) new_val[l] = true; } auto itr = dp.find(new_num); if (itr != dp.end()) { for (int k = 0; k < new_size; k++) if (new_val[k]) itr->second[k] = true; } else dp[new_num] = new_val; } } std::vector final(m); for (int i = 0; i < m; i++) final[i] = all[i].second; assert(dp.count(final)); auto res = dp[final]; assert((int) res.size() == x + 1); std::string ans; for (int i = 1; i <= x; i++) ans.push_back(res[i] ? '1' : '0'); return ans; } int main() { int n = ri(), x = ri(); assert(1 <= n && n <= 100); assert(1 <= x && x <= 500000); std::vector a(n); for (int i = 0; i < n; i++) a[i] = ri(), assert(1 <= a[i] && a[i] <= x); clock_t r0 = clock(); std::cout << solve(n, x, a) << std::endl; clock_t r1 = clock(); std::cerr << (double)(r1 - r0) * 1000 / CLOCKS_PER_SEC << "ms" << std::endl; return 0; }