[题解]异或三角形|2021蓝桥杯国赛|xor triangle

此文使用了mathjax，请等待公式加载
这是2021年蓝桥杯国赛A组C++的一道题目。

当时没有来得及写暴力对拍，只是测了示例过了，也就是说不确定是否正确。

　　首先考虑异或操作的特性，可以交换，所以不妨考虑 $a \geq b \geq c$的情况。随后根据三个数字异或为0，不难看出每一位的异或结果都是0。这也就是说每一位的三个数字只有两种可能，2个1一个0或三个0。不难知道a的首位一定是1，所以另外两个数字在此处必为一1一0。可由此用反证法证明3个数必不相等：
　　如果三个数相等，二进制下首位必相等，与首位一1一0矛盾。如果只有两个数相等，那么这两个数在2进制下必定同1同0。为了满足三个数异或为0，第三个数每一位都只能为0，得出第三数为0，无法形成三角形。

　　这样一来三个数的排列组合就确定了，直接乘以6即可。
　　第一位数已经确定，接下来考虑第二位数，若a为0，则另外2数也只能为0（若都为1则b大于a）。同理从第2位开始的连续的0不会增加可能性。一直递推到（最高位起）第2个1（第一个1为首位，以分析过）。显然另外2数在此处一1一0，因为a为1，所以两种0和1的排列均不会超过a（最多等于）。但是如果所有的1对应的10排列都是b取1，则$a=b$相等，与之前的分析不符，也就是说这么多的排列里面有一种是不可行的。（限制1）再分析0，因为要保证$a>b$，只有在前面已经有a与b不等的情况下才有$a=0,b=1$的可能（c少一位，所以不存在相等的可能）并且不能全为$a=0,b=0$（c为0也不符合条件），即可能情况最多为$2^n-1$（假设有a在这种条件下的1有$n$个）。（限制2）
　　另外再分析三角形的条件，若a为1，b与c为0和1，相加不会大于1，若三数均为0，也不会大于a，也就是说至少有一个地方是a为0，另外2数为1。考虑以上条件不难发现需要考虑a的0和1的不同情况进行排列组合。所以不妨从最低位计算到第2高位的1，并且以1作为主要考虑（0依赖与1的情况）。在a为1的位置，为了a为0的方便，不妨假设在这一位b为0，c为1，那么低位的0有$2^n-1$种，低位的1有$2^n$种（n对应各自在低位中的个数）。然后累加一直到第二高位的1。
　　在这个过程中一种假设了一个位为$a=1,b=0,c=1$，所以限制1满足，而限制2通过减一也满足了。最后将答案乘以6，即为最大数为a的组合数。
　　考虑到输入有多种可能，不妨先根据最大数的大小排序计算，再根据输入顺序排序输出。
代码略（没有复制）。