为何1~n拆分为等和两子集的判定条件n*(n+1)/2%2可替换为(n+1)&2

判定条件等价性推导 #

我们的核心判定逻辑是：当1~n的总和 sum = n*(n+1)/2 为奇数时，无法将序列拆分为两个和相等的子序列，需要输出NO。这一逻辑和代码中的 if (++n & 2) 判定完全等价，推导过程如下：

1. 先明确sum为奇数的充要条件
   n*(n+1)/2 % 2 == 1 等价于 n*(n+1) % 4 == 2。
   因为n和n+1是连续整数，必然一奇一偶，仅其中一个数包含因子2。要让除以2之后的结果为奇数，说明原来的乘积只能恰好包含1个因子2，也就是整个乘积是2乘以一个奇数，即模4余2。
2. 枚举所有n模4的情况，筛选不可拆分的场景

• n mod4 = 0：乘积为4k*(4k+1)，模4余0，sum为偶数，可拆分
• n mod4 = 1：乘积为(4k+1)*(4k+2) = 2*(4k+1)*(2k+1)，模4余2，sum为奇数，不可拆分
• n mod4 = 2：乘积为(4k+2)*(4k+3) = 2*(2k+1)*(4k+3)，模4余2，sum为奇数，不可拆分
• n mod4 = 3：乘积为(4k+3)*(4k+4) =4*(4k+3)*(k+1)，模4余0，sum为偶数，可拆分

3. 对应位运算判定的逻辑
   代码中先将原n加1得到m = n+1，再判断m & 2是否非零。按位与2非零等价于m的二进制倒数第二位为1，也就是m mod4 == 2 或 m mod4 == 3，换算回原n恰好对应上面两种不可拆分的场景：

• m mod4=2 → 原n mod4=1，不可拆分
• m mod4=3 → 原n mod4=2，不可拆分
  两种判定条件完全等价，这种位运算写法是竞赛中常见的性能优化，比乘法取模运算速度更快。

内容的提问来源于stack exchange，提问作者Nick Pengyan