{"problem":{"name":"Split and Square","description":{"content":"For a set $X$ of non-negative integers, let $f(X)$ denote the set of non-negative integers that can be represented as the bitwise $\\mathrm{XOR}$ of two integers (possibly the same) in $X$. As an examp","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc155_e"},"statements":[{"statement_type":"Markdown","content":"For a set $X$ of non-negative integers, let $f(X)$ denote the set of non-negative integers that can be represented as the bitwise $\\mathrm{XOR}$ of two integers (possibly the same) in $X$. As an example, for $X=\\lbrace 1, 2, 4\\rbrace$, we have $f(X)=\\lbrace 0, 3, 5, 6\\rbrace$.\nYou are given a set of $N$ non-negative integers less than $2^M$: $S=\\lbrace A_1, A_2, \\dots, A_N\\rbrace$.\nYou may perform the following operation any number of times.\n\n*   Divide $S$ into two sets $T_1$ and $T_2$ (one of them may be empty). Then, replace $S$ with the union of $f(T_1)$ and $f(T_2)$.\n\nFind the minimum number of operations needed to make $S=\\lbrace 0\\rbrace$.\nWhat is bitwise $\\mathrm{XOR}$?The bitwise $\\mathrm{XOR}$ of non-negative integers $A$ and $B$, $A \\oplus B$, is defined as follows.\n\n*   When $A \\oplus B$ is written in binary, the $k$\\-th lowest bit ($k \\geq 0$) is $1$ if exactly one of the $k$\\-th lowest bits of $A$ and $B$ is $1$, and $0$ otherwise.\n\nFor instance, $3 \\oplus 5 = 6$ (in binary: $011 \\oplus 101 = 110$).  \nGenerally, the bitwise $\\mathrm{XOR}$ of $k$ non-negative integers $p_1, p_2, p_3, \\dots, p_k$ is defined as $(\\dots ((p_1 \\oplus p_2) \\oplus p_3) \\oplus \\dots \\oplus p_k)$, which can be proved to be independent of the order of $p_1, p_2, p_3, \\dots, p_k$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 300$\n*   $1 \\leq M \\leq 300$\n*   $0 \\leq A_i < 2^{M}$\n*   $A_i\\ (1\\leq i \\leq N)$ are pairwise distinct.\n*   Each $A_i$ is given with exactly $M$ digits in binary (possibly with leading zeros).\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$\n$A_2$\n$\\vdots$\n$A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc155_e","tags":[],"sample_group":[["4 2\n00\n01\n10\n11","2\n\nIn the first operation, you can divide $S$ into $T_1=\\lbrace 0, 1\\rbrace, T_2=\\lbrace 2, 3\\rbrace$, for which $f(T_1) =\\lbrace 0, 1\\rbrace, f(T_2) =\\lbrace 0, 1\\rbrace$, replacing $S$ with $\\lbrace 0, 1\\rbrace$.\nIn the second operation, you can divide $S$ into $T_1=\\lbrace 0\\rbrace, T_2=\\lbrace 1\\rbrace$, making $S=\\lbrace 0\\rbrace$.\nThere is no way to make $S=\\lbrace 0\\rbrace$ in fewer than two operations, so the answer is $2$."],["1 8\n10011011","1\n\nIn the first operation, you can divide $S$ into $T_1=\\lbrace 155\\rbrace, T_2=\\lbrace \\rbrace$, making $S=\\lbrace 0\\rbrace$. Note that $T_1$ or $T_2$ may be empty."],["1 2\n00","0\n\nWe have $S=\\lbrace 0\\rbrace$ from the beginning; no operation is needed."],["20 20\n10011011111101101111\n10100111100001111100\n10100111100110001111\n10011011100011011111\n11001000001110011010\n10100111111011000101\n11110100001001110010\n10011011100010111001\n11110100001000011010\n01010011101011010011\n11110100010000111100\n01010011101101101111\n10011011100010110111\n01101111101110001110\n00111100000101111010\n01010011101111010100\n10011011100010110100\n01010011110010010011\n10100111111111000001\n10100111111000010101","10"]],"created_at":"2026-03-03 11:01:13"}}