\u7ed9\u5b9a\u4e00\u4e2a n \u4e2a\u5143\u7d20\u7684\u6570\u7ec4 {ai}, \u95ee\u5b58\u5728\u591a\u5c11\u7ec4 {xi, xi <= ai && \u6240\u6709 xi \u7684 xor \u548c \u7b49\u4e8e 0}\u3002\u3002\u3002\n( n <= 50 .. )\n<\/p>\n
\u4ea6\u6216\u548c\u7b49\u4e8e 0 \u548c\u7b49\u4e8e k \u7684\u7248\u672c\u51e0\u4e4e\u6ca1\u6709\u533a\u522b\uff0c\u8ba8\u8bba\u524d\u8005\u3002<\/p>\n
\u8fd9\u7c7b\u9898\u76ee\u7684\u89e3\u6cd5\u662f\u4ece\u9ad8\u5230\u4f4e\u6309\u4f4d\u5206\u9636\u6bb5\u7ec4\u5408 DP .. .
\n\u6211\u4eec\u7684\u76ee\u7684\u662f\uff0c\u5728\u6bcf\u8f6e\u7684 DP \u8fc7\u540e\uff0c\u8fd9\u4e00\u4f4d\u4e0a\u6240\u6709\u81f3\u5c11 Skip \u4e00\u4f4d\u7684\u7ec4\u5408\uff0c\u5168\u90e8\u88ab\u8ba1\u6570\uff0c\u8fd9\u6837\u505a\u4e4b\u540e\uff0c\u5269\u4e0b\u7684\u6240\u6709\u8fd8\u6ca1\u6709\u88ab\u8ba1\u6570\u7684\u60c5\u51b5\uff08\u6ca1\u6709\u53d1\u751f Skip\uff09\u5c31\u4f1a\u5f62\u6210\u4e00\u4e2a\u7ed3\u6784\u76f8\u540c\u7684\u5b50\u95ee\u9898 …<\/p>\n
\u989d\uff0c\u8fd8\u6ca1\u6709\u5b9a\u4e49 Skip …<\/p>\n
\u6211\u4eec\u8ba8\u8bba\u5f53\u524d\u626b\u63cf\u7684\u662f\u6700\u9ad8\u4f4d … \u5bf9\u4e8e\u90a3\u4e9b\u5728\u8fd9\u4e00\u4f4d\u4e0a\u662f 1 \u7684\u5143\u7d20\uff0c\u8fd9\u4e9b\u5143\u7d20\u6709\u4e24\u79cd\u51b3\u7b56\uff1a
\n\u5206\u522b \u662f\u53d6 1 \u548c\u53d6 0\uff0c\u6211\u4eec\u79f0\u90a3\u4e9b\u542b\u6709 1 \u7684\u5143\u7d20\uff0c\u53d6 0 \u7684\u51b3\u7b56\u4e3a \u6298\u8d8a (Skip) …<\/p>\n
\u90a3\u4e48\u5bf9\u4e8e\u5f53\u524d\u7b2c i \u4f4d\uff0c\u626b\u63cf\u4e86 j \u4e2a\u6570\u5b57\uff0c\u6211\u4eec\u8bbe\u8ba1\u72b6\u6001 f[0], f[1], f[2] \u5206\u522b\u4e3a
\n\u4ece\u672a\u53d1\u751f\u8fc7 \u6298\u8d8a \u3001\u53d1\u751f\u8fc7\u5947\u6570\u6b21 \u6298\u8d8a\u3001\u548c\u53d1\u751f\u8fc7\u5076\u6570\u6b21 \u6298\u8d8a \u4e14\u4e0d\u5305\u62ec f[0]\u3002<\/p>\n
\u5206\u7c7b\u8ba8\u8bba dp \u3002\u3002\u3002<\/p>\n
\r\n#define c ((a[j] & _U(i)) + 1)\r\n#define g (1 << i)\r\n \r\n\u2026\r\n \r\n REP(j, n){\r\n if (_1(a[j], i)) {\r\n int w1 = sum(f[0], pdt(f[2], g)), w2 = pdt(f[1], g); t ^= 1;\r\n MUL(f[0], c), MUL(f[1], c), MUL(f[2], c);\r\n INC(f[1], w1), INC(f[2], w2);\r\n }\r\n else {\r\n MUL(f[0], c), MUL(f[1], c), MUL(f[2], c);\r\n }\r\n }\r\n \r\n\u2026\r\n<\/pre>\n\u4e4b\u540e\uff0c\u6211\u4eec\u8003\u8651\u542b\u6709 1 \u7684\u4e2a\u6570\u7684\u5947\u5076\u6027\uff0c
\n\u5982\u679c\u542b\u6709\u5947\u6570\u4e2a1\uff0c\u90a3\u4e48\u6211\u4eec\u524d\u9762\u6240\u8bf4\u6ca1\u6709\u53d1\u751f\u8fc7\u4e00\u6b21 \u6298\u8d8a (Skip) \u7684\u60c5\u51b5\u5c31\u4e0d\u4f1a\u51fa\u73b0\u5728\u8ba1\u6570\u65b9\u6848\u4e2d\uff0c\u56e0\u6b64\u76f4\u63a5\u8df3\u51fa\u3002
\n\u6bcf\u4e00\u4f4d\u7684\u590d\u6742\u5ea6\u4e3a O(n) \uff0c\u603b\u7684\u590d\u6742\u5ea6\u4e3a O(nb)\uff0cb \u8868\u5143\u7d20\u7684\u4e8c\u8fdb\u5236\u4f4d\u6570 … (\u6700\u540e\u8fb9\u754c\u5904\u522b\u5fd8\u4e86\u6240\u6709\u5143\u7d20\u90fd\u4e3a 0 \u7684\u8bdd\u4e5f\u662f\u4e00\u7ec4\u89e3 .. .)<\/p>\n
…
\n.
\n.<\/p>\n
\uff08\u53e6\uff0c\u63a8\u516c\u5f0f\u7684\u8fc7\u7a0b\u4e2d\u8fd8\u6709\u4e00\u4e2a\u96be\u70b9\uff0c\u5177\u4f53\u7684\u8bf4\u6765\u662f\u8fd9\u6837\uff0c\u5bf9\u4e8e\u5f53\u524d\u626b\u63cf\u5230\u7b2c i \u4f4d\uff0c\u4e00\u4e2a\u53d1\u751f\u4e86 k \u6b21 \u6298\u8d8a \u7684\u72b6\u6001\uff0c\u662f\u9700\u8981\u4fdd\u8bc1 (i, 0] \u4f4d\u4e0a\u7684\u4ea6\u6216\u548c\u4e3a 0 \u7684\u3002
\n\u56e0\u4e3a\u53d1\u751f \u6298\u8d8a \u7684\u4f4d\u7f6e\u4e4b\u540e\u7684\u4e8c\u8fdb\u5236\u4f4d\u53ef\u4ee5\u4efb\u610f\u7ec4\u5408\uff0c\u6240\u4ee5\u5982\u679c\u56fa\u5b9a\u4e86\u5176\u4e2d\u7684\u4efb\u610f k-1 \u4e2a\u5143\u7d20\u7684\u72b6\u6001\uff0c\u603b\u53ef\u4ee5\u8bbe\u7f6e\u4e00\u79cd\u7b2c k \u4e2a\u5143\u7d20\u7684\u72b6\u6001\uff0c\u4f7f\u5f97 (i, 0] \u4f4d\u4e0a\u7684\u4ea6\u6216\u548c\u4e3a 0\uff0c\u8fd9\u4e5f\u662f\u7ec4\u5408 dp \u53ef\u4ee5\u594f\u6548\u7684\u4f9d\u636e\u3002\uff09<\/p>\n