\(\texttt{「CF1713F」Lost Array}\)
\(\text{Link}\)
\(\texttt{Solution}\)
考虑将前缀贡献转换为路径计数，为方便，将列编号从右向左依次编号为 \(0\sim n\)。考虑 \((0,i)\) 到 \((j,0)\) 的贡献次数其实是 \(\binom{i+j}{i}\)，因为是异或，那么可以考虑 \(\binom{i+j}{i}\mod 2\)，根据 \(\text{Lucas}\) 定理这其实是 \([i\sub i+j]\).
\[b_i=\bigoplus_{i\ \text{and}\ (i+j)=i}a_j \]在 \(n=2^k\) 时可以用 \(\text{IFWT}\) 直接做。
我们发现 \((0,0),(1,1),\cdots,(n,n)\) 这些对角线上的元素可以简化我们的式子，具体的
所以我们可以通过对 \(a\) 做一次超集和再做一次子集和得到 \(b\)，同理通过对 \(b\) 做一次逆子集和再做一次逆超集和得到 \(a\)，因为在异或下，集合容斥的 \((-1)^k\) 系数可以忽略，那么此时超集和等价与逆超集和，子集和等价与逆子集和，所以直接对 \(b\) 做一次子集和再做一次超集和可以得到 \(a\).
\(\texttt{Code}\)
点击查看代码
#include<bits/stdc++.h>
#define MAXN (1000005)
#define MAXT (22)
#define MAXS (1124292)
#define ll long long
using namespace std;
void File()
{
freopen("/home/noi/A/IO/in.txt","r",stdin);
freopen("/home/noi/A/IO/out.txt","w",stdout);
}
template<typename type>
void read(type &x)
{
x=0;char ch=0;bool ff=0;
while(ch<'0'||ch>'9'){ff|=!(ch^'-');ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x=ff?-x:x;
}
int n,LG;
int a[MAXN];
int main()
{
File();
read(n);
--n;
LG=__lg(n);
for(int i=0;i<=n;i++)
read(a[i]);
for(int i=0;i<=LG;i++)
for(int S=n;S>=0;S--)
if((S>>i)&1)
a[S]^=a[S^(1<<i)];
for(int i=0;i<=LG;i++)
for(int S=0;S<=n;S++)
if(((S>>i)&1)^1)
a[S]^=a[S^(1<<i)];
for(int i=n;i>=0;i--)
printf("%d ",a[i]);
}