{"problem":{"name":"[EC Final 2022] Binary String","description":{"content":"You are given a binary string $a_0a_1a_2\\dots a_{n-1}$ arranged on a cycle. Each second, you will change every $01$ to $10$ simultaneously. In other words, if $a_i = 0$ and $a_{(i+1) \\bmod n} = 1$, yo","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9717"},"statements":[{"statement_type":"Markdown","content":"You are given a binary string $a_0a_1a_2\\dots a_{n-1}$ arranged on a cycle. Each second, you will change every $01$ to $10$ simultaneously. In other words, if $a_i = 0$ and $a_{(i+1) \\bmod n} = 1$, you swap $a_i$ and $a_{(i+1)\\bmod n}$. For example, we will change $\\texttt{100101110}$ to $\\texttt{001010111}$.\n\nYou need to answer how many different strings will occur in infinite seconds, modulo $998244353$.\n\nNote: Two strings $a_0a_1\\dots a_{n-1}$ and $b_0b_1\\dots b_{n-1}$ are different if there exists an integer $i\\in \\{0,1,\\ldots, n-1\\}$ such that $a_i\\neq b_i$. Thus, the cyclic shifts of a string may be different from the original string.\n\n## Input\n\nThe first line contains an integer $T$ $(1\\leq T\\leq 10^6)$ $-$ the number of test cases.\n\nFor each test case, the first line contains a binary string $a_0 a_1 \\dots a_{n-1}$ $(a_i \\in \\{0, 1\\})$.\n\nIt is guaranteed that the sum of lengths of strings over all test cases does not exceed $10^7$.\n\n## Output\n\nFor each test case, output one integer representing the answer in one line.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9717","tags":["2022","O2优化","KMP 算法","ICPC","EC Final"],"sample_group":[["3\n1\n001001\n0001111","1\n3\n9"]],"created_at":"2026-03-03 11:09:25"}}