一个套路题...但还是得写一下这个套路避免以后忘了

题目中的运算$f(i,j)=(i|j)\text^i$对单位二进制满足$f(0,0)=f(1,0)=f(1,1)=1,f(0,1)=0$

先考虑求正变换，即是求$b_i=\sum\limits_{j=0}^{n-1}\left[2|\text{bit}(f(i,j))\right]a_j$

用类似FWT的过程求$b$

假设我们已经对$l\leq i\leq mid$求出$b_i=\sum\limits_{j=l}^{mid}[2|\text{bit}(f(i,j))]a_j$，已经对$mid+1\leq i\leq r$求出$b_i=\sum\limits_{j=mid+1}^r[2|\text{bit}(f(i,j))]a_j$，现在我们想对$l\leq i\leq r$求$b_i=\sum\limits_{j=l}^r[2|\text{bit}(f(i,j))]a_j$

①对$l\leq i\leq mid$，$\sum\limits_{j=mid+1}^r[2|\text{bit}(f(i,j))]a_j=\sum\limits_{j=mid+1}^ra_j-b_{i+\frac{len}2}$（因为$b_{i+\frac{len}2}$的最高位是$f(1,1)=1$，我们要求的东西的最高位是$f(0,1)=0$，所以$\text{bit}(f(i,j))$奇偶性变化）

②对$mid+1\leq i\leq r$，$\sum\limits_{j=l}^{mid}[2|\text{bit}(f(i,j))]=b_{i-\frac{len}2}$（因为$b_{i-\frac{len}2}$的最高位是$f(0,0)=1$，我们要求的东西的最高位是$f(1,0)=1$，所以$\text{bit}(f(i,j))$奇偶性不变）

写成FWT的格式是$\begin{cases}a_{[0]}'=s_{[1]}-a_{[1]}+a_{[0]}\\a_{[1]}'=a_{[1]}+a_{[0]}\end{cases}$，立得逆变换$\begin{cases}a_{[0]}=\frac{a_{[1]}'+a_{[0]}'-s_{[1]}}2\\a_{[1]}=\frac{a_{[1]}'-a_{[0]}'+s_{[1]}}2\end{cases}$

这种类型的题目大部分可以这样推导出来

剩下一个小问题就是求$s_{[1]}$，一般题目中给的这个运算能让你快速求它，比如这道题中$s_{[1]}=b_{r}-b_{mid}$

时间复杂度$O(n\log_2n)$

#include
     
      typedef long long ll;#define NUM(x) ('0'<=x&&x<='9')char c[40000010];int ns;inline ll rd(){	while(!NUM(c[ns]))ns++;	ll x=0;	while(NUM(c[ns]))x=(x<<3)+(x<<1)+c[ns++]-'0';	return x;}ll a[1048576];int n;void trans(ll*a){	int i,j,k;	ll s,u,v;	for(i=n;i>1;i>>=1){		for(j=0;j
      
       >1;k++){				u=a[j+k];				v=a[i/2+j+k];				a[j+k]=(u+v-s)/2;				a[i/2+j+k]=(-u+v+s)/2;			}		}	}}int main(){	c[fread(c,1,40000010,stdin)]=0;	int i;	n=rd();	for(i=0;i