CF1713F 题解

题意

传送门

给出一个从 \(1\) 到 \(n\) 的数组 \(a\)，有一个从 \(0\) 开始标号的大小为 \((n+1)\times(n+1)\) 的矩阵 \(b\)，通过以下方式生成：

• 对于 \(0\le i\le n\)，\(b_{i,0}=0\)
• 对于 \(1\le i\le n\)，\(b_{0,i}=a_i\)
• 对于 \(1\le i,j\le n\)，\(b_{i,j}=b_{i,j-1}\oplus b_{i-1,j}\)

现在，给出 \(b_{1,n},b_{2,n},\dots,b_{n,n}\)，试还原出一个满足条件的 \(a\) 数组，或报告无解。

\(1\le n\le 5\times10^5\)。

题解

称矩阵第一行为 \(a\)，最后一列为 \(b\)，并将 \(a\) 翻转，从 \(0\) 开始标号。不难看出 \(b_i=\oplus_{i=0}^{n-1}a_i[\binom{i+j}{j}\bmod 2]\)。

对后式用卢卡斯定理，得到 \((i+j)\&j=j\)。即 \(i\&j=0\)。若已知 \(a\)，可以 FWT 求其子集和，各位翻转一下即为 \(b\)；但当 \(n\) 不为 \(2\) 的整数次幂时，不能将 \(b\) 翻转由 \(b\) 求 \(a\)。

翻转是由于 \((i+j)\&j=j\)，若其为 \(i\&j=j\)，就是一个简单的子集和。由此考虑到用对角线作为中转。

从 \(a\) 到 \(b\)，必然经过仅经过一次对角线。从 \(a_i\) 到对角线（从右向左从 \(0\) 开始标号）\(j\) 再到 \(b_k\)，方案为 \(\binom{i}{j}\binom{k}{j}\)。产生贡献的充要条件即为 \(i\&j=j\wedge k\&j=j\)。于是对 \(a\) 求超集和再求子集和即为 \(b\)。这样就规避了翻转。从 \(b\) 到 \(a\) 只需逆着做一遍即可。复杂度 \(O(n\log n)\)。