题目
点这里看题目。
有一个长度为 \(n\) 的非负整数序列 \(\{a_i\}_{i=1}^n\)，以此生成一个 \((n+1)\times(n+1)\) 的非负整数矩阵 \(A\)：
-
对于 \(0\le i\le n\)，有 \(A_{i,0}=0\)。
-
对于 \(1\le i\le n\)，有 \(A_{0,i}=a_i\)。
-
对于 \(1\le i,j\le n\)，有 \(A_{i,j}=A_{i-1,j}\oplus A_{i,j-1}\)。
设 \(\{b_{i}=A_{i,n}\}_{i=1}^n\)，现在给出 \(b\)，构造一组可以生成 \(b\) 的 \(a\)，或报告无解。
所有数据满足 \(1\le n\le 5\times 10^5,0\le b_i\le 2^{30}\)。
分析
容易发现，\(a_i\) 对于 \(b_j\) 的贡献系数为 \(\binom{n-i+j-1}{j-1}\)。
然而，在异或的含义下，我们关心的是 \(\binom{n-i+j-1}{j-1}\bmod 2\)，根据 Lucas 定理 \(\binom{n-i+j-1}{j-1}\bmod 2\) 为 \(1\) 当且仅当 \((n-i+j-1)\cap(j-1)=j-1\)（用 \(x\cap y\) 表示二进制下按位与）。
进一步地，我们尝试把 \(n-i+j-1\) 拆开。容易发现，上述条件等价于 \((n-i)\cap (j-1)=0\)，因为如果与非零，则 \((n-i)\cap (j-1)\) 的最低位不会被进位补齐，就会真的变成 \(0\)。
找出 \(U=2^{\lceil\log_2 n\rceil}-1\)，我们把 \(U\) 当作“全集”，则所有 \(x\cap (j-1)=0\) 的 \(x\) 必然是 \(U\oplus(j-1)\) 的“子集”，这样我们就把 \(b\) 的限制变成了 \(n\) 条 \(a\) 的子集异或和的方程。
设 \(\overline{a}_i=\begin{cases}a_{n-i}&0\le i<n&\\0&n\le i\le U\end{cases}\)，也就是先反转再补零的结果。
如果 \(U=n-1\)，那么我们就可以直接执行逆变换算出来 \(\overline a\)，进而得到 \(a\)。
然而实际情况没有这么好。设 \(S_x=\bigoplus_{y\cap x=y}\overline a_y\)，则我们得到的实际上是 \(S_{U-n+1}\) 到 \(S_{U}\) 的准确值。但一个前缀的 \(S\) 的值是丢失的，所以光凭这些信息还不足以帮助我们快速地解出 \(\overline a\)。
我们尝试再建立一点 \(\overline a\) 和 \(S\) 之间的联系。不妨考虑朴素的容斥，我们知道 \(\overline a_y=\sum_{x\cap y=x}(-1)^{\operatorname{popcount}(x\oplus y)}S_x\)，而在按位异或的意义下 \(-1\) 系数毫无作用，所以 \(\overline a_y=\bigoplus_{x\cap y=x}S_x\)！也可以说 \(\overline a\) 和 \(S\) 互为子集异或和！
我们马上注意到 \(\overline a\) 在某些位置上为 \(0\)，所以这又给我们新增了 \(U-n+1\) 条关于 \(S\) 的方程。一共 \(U+1\) 条方程，正好可以解出 \(U+1\) 个变量。然而，未知量集中在前缀上，有效的方程集中在后缀上，我们还需要更多的处理。
不妨再把问题化简，我们消去所有已知的 \(S\) 的贡献，算出 \(T_y=\bigoplus_{0\le x<n,x\cap y=0}S_x\)。现在我们得到的就是纯粹的和前 \(n\) 个 \(S\) 相关的问题了。结合二进制变换的一贯尿性，我们不妨考虑分治方法解决这个问题。
用 \((B,L,R,q)\) 来表示“如果 \(T\) 仅在前 \(B\) 位做前缀和，已知 \(T_{R-q+1}\sim T_{R}\)，且 \(S_{L+q}\sim S_{R}\) 都是 \(0\)，求出 \(S_L\sim S_{L+q-1}\)”。计算过程需要讨论一点情况：
-
如果 \(q=R-L+1\)，则可以直接逆变换算，这是边界。
-
如果 \(q\le 2^{B-1}\)，则 \([L+2^{B-1},R]\) 这一段因为全为 \(0\) 而没有贡献，可以直接递归到 \((B-1,L,\lfloor\frac{L+R}{2}\rfloor,q)\) 计算。
-
否则，我们必须考虑交叉贡献。
两边尝试一下，发现先计算区间 \([L+2^{B-1},R]\) 会容易一点。那么，在递归下去之前，我们需要消除 \([L,L+2^{B-1}-1]\) 的影响。
设 \(r=q-2^{B-1}\)。由于我们只知道 \(T_{R-q+1}\sim T_{L+2^{B-1}-1}\) 的信息，所以我们可以计算出仅在前 \(B-1\) 位做前缀和时的 \(T_{R-r+1}\sim T_{R}\)。好巧不巧，根据对称性，区间 \([L+2^{B-1},R]\) 中也正好只有 \(r\) 个值未确定，递归下去形式已知，正好就是 \((B-1,L+2^{B-1},R,r)\)。
解决完一边之后，我们可以相应地去掉 \([L+2^{B-1},R]\) 的贡献，从而得到仅在前 \(B-1\) 位做前缀和时的 \(T_{L}\sim T_{L+2^{B-1}-1}\)。所以，我们已经到边界了！
容易发现复杂度为 \(O(n\log n)\)，因为每次递归大小折半且实质上只会走向单侧。
Remark.
不知道能写点什么，真正重要的内容全部用黑色加粗了。
不过我想说，tnnd 你谷题解区前三篇写的都是什么东西？正常人怎么会想到“先超集再子集”这种反常思路？
当然很有可能是因为我是一个神必。总之看得我一头雾水。一般来说，思路应当连贯，后来的多多少少要和已有的照应。思考的时候也可以注意一下，如果思路太发散就需要用纸笔辅助，避免忘了自己想过什么东西。
代码
#include <cstdio>
#include <vector>
#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )
const int MAXN = ( 1 << 20 ) + 5;
template<typename _T>
inline void Read( _T &x ) {
x = 0; char s = getchar(); bool f = false;
while( ! ( '0' <= s && s <= '9' ) ) { f = s == '-', s = getchar(); }
while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
if( f ) x = -x;
}
template<typename _T>
inline void Write( _T x ) {
if( x < 0 ) putchar( '-' ), x = -x;
if( 9 < x ) Write( x / 10 );
putchar( x % 10 + '0' );
}
int su[MAXN];
int f[MAXN], tmp[MAXN];
int N, U, K;
inline void Conv( const int &b, int *coe ) {
int n = 1 << b;
for( int i = 0 ; i < b ; i ++ )
for( int j = 0 ; j < n ; j ++ )
if( j >> i & 1 ) coe[j] ^= coe[j ^ ( 1 << i )];
}
void Divide( const int &B, const int &L, const int &R, const int &len, int *val ) {
if( ! len || B < 0 ) return ;
int mid = ( L + R ) >> 1;
if( len == R - L + 1 ) {
rep( i, 0, len - 1 ) tmp[i] = val[i];
Conv( B, tmp );
rep( i, 0, len - 1 ) su[i + L] = tmp[i];
} else if( len <= mid - L + 1 )
Divide( B - 1, L, mid, len, val );
else {
std :: vector<int> old( val, val + len );
int rsd = len - ( R - mid ), hlf = 1 << ( B - 1 );
rep( i, 0, rsd - 1 ) val[i + hlf] ^= val[i];
Divide( B - 1, mid + 1, R, rsd, val + hlf );
rep( i, 0, hlf - 1 )
tmp[i] = i < rsd ? su[i + mid + 1] : 0;
Conv( B - 1, tmp );
rep( i, 0, hlf - 1 ) tmp[i] ^= old[i + rsd];
rep( i, 0, hlf - 1 ) val[i] = tmp[i];
Divide( B - 1, L, mid, hlf, val );
}
}
int main() {
Read( N );
for( U = 1, K = 0 ; U < N ; U <<= 1, K ++ );
rep( i, 0, N - 1 ) {
int b; Read( b );
su[( U - 1 ) ^ i] = b;
}
rep( i, 0, U - 1 ) f[i] = i <= U - 1 - N ? 0 : su[i];
Conv( K, f );
if( U == N ) {
rep( i, 1, N )
Write( f[N - i] ), putchar( " \n"[i == N] );
return 0;
}
Divide( K, 0, U - 1, U - N, f + N );
Conv( K, su );
rep( i, 1, N ) Write( su[N - i] ), putchar( " \n"[i == N] );
return 0;
}