Codeforces Round #752 (Div. 2) B. XOR Specia-LIS-t

思路

• 异或的性质
  • $0\oplus1=1$，$0\oplus0=0$，结论：0异或任何数都不改变这个数
  • 一个位上，有奇数个1，这一位的结果是1；有偶数个1，这一位的结果是0
• 如果n是偶数，取所有的子序列为单个元素，则所有的子序列中最长严格递增子序列的长度都为1，偶数个1异或结果为0
• 如果n是奇数
  • 如果数列a中存在$a[i+1] <= a[i]$, 将这两个元素取为子序列，则这个子序列中LIS长度为1，而其余n-2个元素取成n-2个子序列。共n-1个子序列，这些子序列的LIS长度均为1。n-1个1异或结果为0(因为n-1为偶数)

  • 如果数列a中不存在$a[i+1]<=a[i]$，即数列a是严格单调增加序列，则无论子序列如何划分，子序列的长度就是LIS的长度。从而原问题是否输出”YES”可以转化为
    $$ b_1+b_2+…+b_k=n……(1); b_1 \ xor \ b_2\ xor…xor\ b_k=0……(2) $$
    是否有正整数解。

    若(2)式成立，则所有的b的最右边一位上的1的个数为偶数，从而$\sum b=偶数$，与(1)式矛盾所以该方程组没有解，这个情况输出NO