{"trustable":false,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"题目介绍","value":{"format":"MD","content":"DreamGrid 刚刚在他的Ubuntu里发现了两个字符串 s 和 t!他想做以下操作恰好两次使得 s 变成 t。\n\n操作是选择两个数字 `l, r` (1 ≤ l ≤ r ≤ n),将 s\u003csub\u003ei\u003c/sub\u003e 变为 1-s\u003csub\u003ei\u003c/sub\u003e 对于所有的 l ≤ i ≤ r。\n\nDreamGrid 想知道有多少种方法来做到。\n\n我们用如下规则来确定两种方式是否不同:\n\n- 令 A \u003d (a\u003csub\u003e1\u003c/sub\u003e, a\u003csub\u003e2\u003c/sub\u003e, a\u003csub\u003e3\u003c/sub\u003e, a\u003csub\u003e4\u003c/sub\u003e),其中 1 ≤ a\u003csub\u003e1\u003c/sub\u003e ≤ a\u003csub\u003e2\u003c/sub\u003e ≤ n, 1 ≤ a\u003csub\u003e3\u003c/sub\u003e ≤ a\u003csub\u003e4\u003c/sub\u003e ≤ n,是 DreamGrid 的一种操作方案。\n- 令 B \u003d (b\u003csub\u003e1\u003c/sub\u003e, b\u003csub\u003e2\u003c/sub\u003e, b\u003csub\u003e3\u003c/sub\u003e, b\u003csub\u003e4\u003c/sub\u003e),其中 1 ≤ b\u003csub\u003e1\u003c/sub\u003e ≤ b\u003csub\u003e2\u003c/sub\u003e ≤ n, 1 ≤ b\u003csub\u003e3\u003c/sub\u003e ≤ b\u003csub\u003e4\u003c/sub\u003e ≤ n,是 DreamGrid 的另一种操作方案。\n- A 和 B 是不同的当且仅当存在 k 满足 a\u003csub\u003ek\u003c/sub\u003e ≠ b\u003csub\u003ek\u003c/sub\u003e。"}},{"title":"输入","value":{"format":"MD","content":"输入有多组测试用例。第一行包含数字 `T` 表示测试用例数目。\n\n对于每个测试用例,第一行包含一个数字 `n` (1 ≤ n ≤ 10\u003csup\u003e6\u003c/sup\u003e),表示两个二进制序列的长度。\n\n第二行包含一个字符串 s\u003csub\u003e1\u003c/sub\u003es\u003csub\u003e2\u003c/sub\u003e...s\u003csub\u003en\u003c/sub\u003e (s\u003csub\u003ei\u003c/sub\u003e ∈ {0,1}),表示第一个二进制串。\n\n第三行包含一个字符串 t\u003csub\u003e1\u003c/sub\u003et\u003csub\u003e2\u003c/sub\u003e...t\u003csub\u003en\u003c/sub\u003e (t\u003csub\u003ei\u003c/sub\u003e ∈ {0,1}),表示第二个二进制串。\n\n保证所有测试用例 `n` 的总和不超过 10\u003csup\u003e7\u003c/sup\u003e。"}},{"title":"输出","value":{"format":"MD","content":"对于每组测试用例,输出一个数字表示答案。"}},{"title":"样例输入","value":{"format":"MD","content":"```\n3\n1\n1\n0\n2\n00\n11\n5\n01010\n00111\n```"}},{"title":"样例输出","value":{"format":"MD","content":"```\n0\n2\n6\n```"}},{"title":"提示","value":{"format":"MD","content":"对于第二个测试样例,有两个合法的操作对 `(1, 1, 2, 2)` 和 `(2, 2, 1, 1)`。\n\n对于第三个测试样例,有六个合法的操作对 `(2, 3, 5, 5)`、`(5, 5, 2, 3)`、`(2, 5, 4, 4)`、`(4, 4, 2, 5)`、`(2, 4, 4, 5)` 和 `(4, 5, 2, 4)`"}}]}