#P14963. [2026年重庆省队集训]不动点

[2026年重庆省队集训]不动点

题目描述

对于非负整数 zz 和一个非负整数集合 SS ,设 fz(S)={x⊕z∣x∈S}f_z(S)=\{x\oplus z\mid x\in S\} ,即 fz(S)f_z(S) 为 SS 中所有元素异或上 zz 得到的集合。若 S=fz(S)S=f_z(S) ,则称 zz 是 SS 的不动点。

给定非负整数集合 SS ,求 SS 的所有不动点。

输入格式

输入的第一行包含一个非负整数 cc ,表示子任务编号。c=0c = 0 表示该测试点为样例。

第二行有一个整数 nn ,表示集合大小 ∣S∣|S| 。

第三行有 nn 个正整数 a1,a2,…,ana_1,a_2,\dots,a_n ,满足 S={a1,a2,…,an}S=\{a_1,a_2,\dots,a_n\} 。

输出格式

第一行输出一个整数 kk ,表示 SS 的不动点的个数。保证不动点个数不超过 10610^6 。

第二行输出 kk 个整数,升序输出所有 SS 的不动点。

样例 1 输入

0
6
0 1 2 4 5 6

样例 1 输出

2
0 4

样例 1 解释

S0={ 0,1,2,4,5,6 }=SS_0=\set{0,1,2,4,5,6}=S ,故 00 是 SS 的不动点。

S1={ 0,1,3,4,5,7 }≠SS_1=\set{0,1,3,4,5,7}\not=S ,故 11 不是 SS 的不动点。

S2={ 0,2,3,4,6,7 }≠SS_2=\set{0,2,3,4,6,7}\not=S ,故 22 不是 SS 的不动点。

S3={ 1,2,3,5,6,7 }≠SS_3=\set{1,2,3,5,6,7}\not=S ,故 33 不是 SS 的不动点。

S4={ 0,1,2,4,5,6 }=SS_4=\set{0,1,2,4,5,6}=S ,故 44 是 SS 的不动点。

数据范围

1≤n≤6×105,0≤ai<2631\le n\le 6\times 10^5,0\le a_i< 2^{63} ,对于 i≠ji\not=j ,ai≠aja_i\not=a_j 。

设 m=max⁡i=1n{ai}m=\max\limits_{i=1}^n\{a_i\} 。

本题使用捆绑测试。

子任务编号 分数 nn mm 特殊性质
11 55 是奇数 <263<2^{63} 否
22 1515 ≤1500\le 1500
33 ≤6×105\le 6\times 10^5 是
44 2525 <220<2^{20} 否
55 1515 ≤2×105\le 2\times 10^5 <263<2^{63}
66 2525 ≤6×105\le 6\times 10^5

特殊性质:设 kk 为 SS 的不动点个数,则 SS 在所有大小为 nn ,所有数小于 2632^{63} 且不动点个数为 kk 的集合中等概率选取。

时间限制:1s\text{1s}

空间限制:1024 MiB\text{1024 MiB}