首页 > 其他分享 >CF1713F Lost Array(FWT,卢卡斯定理,*)

CF1713F Lost Array(FWT,卢卡斯定理,*)

时间:2022-10-10 19:58:18浏览次数:73  
标签:Lost CF1713F FWT 卢卡斯 binom Array

CF1713F Lost Array

矩阵 \(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]\)。

CODE

翻转 \(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

相关文章