矩阵 \(b[0 \to N][0 \to N]\)。\(b[i][0] = 0\),\(b[0][i](i > 1) = a[i]\)。\(b[i][j] = b[i - 1][j] \oplus b[i][j - 1]\)。给出 \(c[1 \to N] = b[1 \to N][N]\),求 \(a[1 \to N]\)。
翻转 \(a\) 以及 \(b\) 的每一行,尝试求出 \(b[1][1 \to N]\) 与 \(b[1 \to N][N]\) 之间所夹的对角线的值。找规律发现 \(b[j][N]\) 对 \(b[i][i]\) 的贡献次数为 \(\binom{i}{j - 1}\),而 \(b[1][j]\) 对 \(b[i][i]\) 的贡献次数为 \(\binom{j}{i}\)。
\[\binom{n}{m} \bmod 2 = [m_2 \in n_2] \]于是先对 \(c\) 做一次子集和,再做一次超集和即可。
标签:Lost,CF1713F,FWT,卢卡斯,binom,Array From: https://www.cnblogs.com/Pizza1123/p/16776945.html