\(\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_{i,i}=\bigoplus_{i\sub j}a_{0,j}\\ a_{i,0}=\bigoplus_{j\sub i}a_{j,j}\\ \]

所以我们可以通过对 \(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]);
}