{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003ch3\u003e\u003ca href\u003d\"/contest/1630/problem/A\" title\u003d\"Codeforces Round 768 (Div. 1)\"\u003e1630A - И-сопоставление\u003c/a\u003e\u003c/h3\u003e\u003cp\u003eAuthor: \u003ca class\u003d\"rated-user user-orange\" href\u003d\"/profile/humbertoyusta\" title\u003d\"Мастер humbertoyusta\"\u003ehumbertoyusta\u003c/a\u003e\u003c/p\u003e \u003cdiv class\u003d\"spoiler\"\u003e\u003cb class\u003d\"spoiler-title\"\u003eGợi Ý 1\u003c/b\u003e\u003cdiv class\u003d\"spoiler-content\" style\u003d\"display: none;\"\u003e\u003cp\u003eThử tìm cặp số sao cho $$$\\sum\\limits_1^{n/2}{a_i\\\u0026{b_i}}\u003d0$$$\u003c/p\u003e\u003c/div\u003e\u003c/div\u003e \u003cdiv class\u003d\"spoiler\"\u003e\u003cb class\u003d\"spoiler-title\"\u003eGợi Ý 2\u003c/b\u003e\u003cdiv class\u003d\"spoiler-content\" style\u003d\"display: none;\"\u003e\u003cp\u003eThử tìm cặp số cho $$$k\u0026gt;0$$$ bằng cách thay đổi chỉ một vài phần tử so với cặp trước đó.\u003c/p\u003e\u003c/div\u003e\u003c/div\u003e \u003cdiv class\u003d\"spoiler\"\u003e\u003cb class\u003d\"spoiler-title\"\u003eGiải Pháp\u003c/b\u003e\u003cdiv class\u003d\"spoiler-content\" style\u003d\"display: none;\"\u003e\u003cdiv class\u003d\"spoiler\"\u003e\u003cb class\u003d\"spoiler-title\"\u003ePhương pháp xây dựng (dễ dàng hơn)\u003c/b\u003e\u003cdiv class\u003d\"spoiler-content\" style\u003d\"display: none;\"\u003e\u003cp\u003eHãy định nghĩa $$$c(x)$$$, sự bù của $$$x$$$, là số $$$x$$$ sau khi thay đổi tất cả các bit 0 thành 1 và ngược lại, ví dụ $$$c(110010_2) \u003d 001101_2$$$.\u003c/p\u003e\u003cp\u003eCó thể chứng minh rằng $$$c(x) \u003d x\\oplus{(n-1)}$$$. Hãy nhớ rằng $$$n-1 \u003d 11...11_2$$$ vì $$$n$$$ là một lũy thừa của $$$2$$$.\u003c/p\u003e\u003cp\u003eChúng ta sẽ chia bài toán thành ba trường hợp.\u003c/p\u003e \u003cul\u003e \u003cli\u003e\u003cp\u003e\u003cstrong\u003eTrường hợp $$$k \u003d 0$$$:\u003c/strong\u003e\u003c/p\u003e\u003cp\u003eTrong trường hợp này, có thể ghép cặp số $$$x$$$ với $$$c(x)$$$ cho $$$0\\leq{x}\u0026lt;{\\frac{n}{2}}$$$, nhận được $$$\\sum\\limits_{x\u003d0}^{\\frac{n}{2}-1} {x\\\u0026{c(x)}} \u003d 0$$$.\u003c/p\u003e\u003c/li\u003e \u003cli\u003e\u003cp\u003e\u003cstrong\u003eTrường hợp $$$0 \u0026lt; k \u0026lt; n-1$$$:\u003c/strong\u003e\u003c/p\u003e\u003cp\u003eTrong trường hợp này, có thể ghép mỗi phần tử với số bù của nó trừ những số $$$0$$$, $$$k$$$, $$$c(k)$$$ và $$$n-1$$$, sau đó ghép $$$0$$$ với $$$c(k)$$$ và $$$k$$$ với $$$n-1$$$, $$$0\\\u0026 c(k) \u003d 0$$$ và $$$k\\\u0026 (n-1) \u003d k$$$.\u003c/p\u003e\u003c/li\u003e \u003cli\u003e\u003cp\u003e\u003cstrong\u003eTrường hợp $$$k \u003d n-1$$$:\u003c/strong\u003e\u003c/p\u003e\u003cp\u003eCó nhiều cách xây dựng hoạt động trong trường hợp này, nếu $$$n\u003d4$$$ không có giải pháp, nếu $$$n \\geq8$$$ có thể xây dựng câu trả lời như sau:\u003c/p\u003e\u003cp\u003eCó thể ghép $$$n-1$$$ với $$$n-2$$$, $$$n-3$$$ với $$$1$$$, $$$0$$$ với $$$2$$$ và tất cả các phần tử khác với số bù của chúng.\u003c/p\u003e \u003cul\u003e \u003cli\u003e$$$(n-1)\\\u0026{(n-2)}\u003dn-2$$$, ví dụ $$$1111_2\\\u0026{1110_2}\u003d1110_2$$$\u003c/li\u003e \u003c/ul\u003e \u003cul\u003e \u003cli\u003e$$$(n-3)\\\u0026{1}\u003d1$$$, ví dụ $$$1101_2\\\u0026{0001_2}\u003d0001_2$$$\u003c/li\u003e \u003c/ul\u003e \u003cul\u003e \u003cli\u003e$$$0\\\u0026{2}\u003d0$$$, ví dụ $$$0000_2\\\u0026{0010_2}\u003d0000_2$$$\u003c/li\u003e \u003c/ul\u003e \u003cul\u003e \u003cli\u003eTất cả các phần tử khác có thể được ghép với số bù của chúng và $$$x\\\u0026{c(x)}\u003d0$$$\u003c/li\u003e \u003c/ul\u003e\u003cp\u003eChú ý rằng $$$(n-2)+1+0+0+ ... +0\u003dn-1$$$.\u003c/p\u003e\u003c/li\u003e \u003c/ul\u003e\u003cp\u003eMỗi trường hợp có thể được thực hiện trong $$$O(n)$$$.\u003c/p\u003e \u003cdiv class\u003d\"spoiler\"\u003e\u003cb class\u003d\"spoiler-title\"\u003eCode\u003c/b\u003e\u003cdiv class\u003d\"spoiler-content\" style\u003d\"display: none;\"\u003e\u003cpre\u003e"}}]}