Description：

有两个数组 $a$ 和 $b$ ，已知： $$ b_i=\sum_{0\leqslant j<n}\bigg(\Big(bitcount((i\text{ or }j)\text{ xor i})+1\Big)\bmod2\bigg)a[j] $$ 给出 $b$ ，求 $a$ 。

$1\leqslant n\leqslant 1500000$

Solution：

首先有 $$ (i\text{ or }j)\text{ xor i}=\lnot i\text{ and }j $$

设 $f[i][j]=\bigg(\Big(bitcount(\lnot i\text{ and }j)+1\Big)\bmod2\bigg)$ ，那么有 $f[0][0]=1$ ，对最高位讨论可以得到： $$ \begin{align} f[0i][0j]&=\bigg(\Big(bitcount(\lnot(0i)\text{ and }(0j))+1\Big)\bmod2\bigg)=\bigg(\Big(bitcount(\lnot i\text{ and }j)+1\Big)\bmod2\bigg)=f[i][j]\\ f[1i][0j]&=\bigg(\Big(bitcount(\lnot(1i)\text{ and }(0j))+1\Big)\bmod2\bigg)=\bigg(\Big(bitcount(\lnot i\text{ and }j)+1\Big)\bmod2\bigg)=f[i][j]\\ f[0i][1j]&=\bigg(\Big(bitcount(\lnot(0i)\text{ and }(1j))+1\Big)\bmod2\bigg)=\bigg(\Big(bitcount(\lnot i\text{ and }j)+2\Big)\bmod2\bigg)=\lnot f[i][j]\\ f[1i][1j]&=\bigg(\Big(bitcount(\lnot(1i)\text{ and }(1j))+1\Big)\bmod2\bigg)=\bigg(\Big(bitcount(\lnot i\text{ and }j)+1\Big)\bmod2\bigg)=f[i][j]\\ \end{align} $$ 如果把 $f$ 写成矩阵的话就是： $$ \begin{align} F_1&= \begin{bmatrix} 1 & 0\\ 1 & 1 \end{bmatrix} \\ F_i&= \begin{bmatrix} F_{i-1} & \lnot F_{i-1}\\ F_{i-1}&F_{i-1} \end{bmatrix} \end{align} $$ 然后有一个结论是设矩阵 $G_i$ 为： $$ \begin{align} G_1&= \begin{bmatrix} 1 & 1\\ -1 & 1 \end{bmatrix} \\ G_i&= \begin{bmatrix} G_{i-1} & G_{i-1}\\ -G_{i-1} & G_{i-1} \end{bmatrix} \end{align} $$ 那么 $F^{-1}_n$ 就是 $G_n\times \frac1{2^{n-1}}$ 最右上角元素减一得到的矩阵。

那么我们可以用这种方法求出 $F$ 的逆矩阵然后用 $b$ 乘即可。

但是这样时间复杂度是 $O(n^2)$ 的，我们把 $b$ 看成一个向量，那最后答案就是 $G\times b$ ，考虑有没有什么快速的方法计算这个乘法，我们把它拆开： $$ \begin{align} G_i\times b&=\begin{bmatrix}G_{i-1} & G_{i-1}\\-G_{i-1} & G_{i-1}\end{bmatrix}\times \begin{bmatrix}b_0\\b_1\end{bmatrix}\\ &=\begin{bmatrix}G_{i-1}b_0+G_{i-1}b_1\\-G_{i-1}b_0+G_{i-1}b_1\end{bmatrix} \end{align} $$ 即： $$ \hat b_0=G_{i-1}b_0+G_{i-1}b_1\\ \hat b_1=-G_{i-1}b_0+G_{i-1}b_1 $$ 不难发现这个和 $FFT$ 的式子非常像，因此我们用类似 $FFT$ 的方法做就行了。

Solution：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n;

#define MAXN 1500010

typedef long long ll;

ll b[MAXN],a[MAXN];

int main()

{

	scanf("%d",&n);

	for(int i = 0;i < n;++i)scanf("%lld",&b[i]);

	if(n == 1)

	{

		printf("%lld\n",b[0]);

		return 0;

	}

	int v = n >> 1;

	a[0] -= b[n - 1] * v;

	for(int i = 2;i <= n;i = i << 1)

	{

		for(int j = 0;j < n;j += i)

		{

			for(int k = j;k < j + i / 2;++k)

			{

				ll u = b[k],t = b[k + i / 2];

				b[k] = t + u;

				b[k + i / 2] = t - u;

			}

		}

	}

	for(int i = 0;i < n;++i)a[i] += b[i];

	for(int i = 0;i < n;++i)a[i] /= v;

	for(int i = 0;i < n;++i)printf("%lld ",a[i]);

	cout << endl;

	return 0;

}