C/C++教程

【题解】CF1408I Bitwise Magic

本文主要是介绍【题解】CF1408I Bitwise Magic，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

求最后修正的异或和就行，考虑每个位置最后被操作的次数：

\[F(x,y)=\prod_{i=1}^{n}\left(\sum_{j=0}^{k}\frac{x^j}{j!}y^{a_i\oplus (a_{i}-j)}\right) \]

这里从 \(a_i\oplus (a_i-j)\) 考虑。具体地考虑 \(\left\{x\oplus (x-1),x\oplus (x-2),\cdots, x\oplus (x-k)\right\}\) 的数量，记 \(t\) 为最低位。

  • \(t> \log k\)：那么第一次引发进位，剩下的都是一样的，个数是 \(O(c)\) 的。
  • \(t\leq \log k\)：前半部分跑完没进到 \(k\) 后的，然后找到 \(k\) 后第一个为 \(1\) 的位置，进位后后半部分是一样的，个数为 \(O(ck)\) 。

那么个数就是 \(O(ck)\) 的，\(n\) 个 \(a_i\) 都可以对应到其中的一个去。接着就需要求出 \(G_i(x,y)\) 表示第 \(i\) 个方案的多项式，\(a_{i,j}\) 表示第 \(i\) 个方案的第 \(j\) 个值，\(r_i\) 表示第 \(i\) 个方案的出现次数。考虑将 \(G_i(x,y)\) 求 \(\ln\) 加和后求 \(\exp\) 。

\[G_i(x,y)=\sum_{j=0}^{k}\frac{x^j}{j!}y^{a_{i,j}} \]

再继续讨论 \(G_i(x,y)\) 怎么做之前，先来讨论一下怎么做 \(\ln\)（边界为 \(B_0=0\)）：

\[B(x)=\ln A(x)\Rightarrow B'(x)A(x)=A'(x)\\ B_{n}=\frac{A_{n}}{A_{0}}-\frac{1}{nA_{0}}\sum_{i=1}^{n-1}iB_{i}A_{n-i} \]

后面是异或卷积，考虑先将 \(G_i(x,y)\) 给 FWT，这样的话枚举 \(y^t\)，然后做 \(\ln\) 就行。做完后再 IFWT 回来，就得到了我们想要的结果，也就是 \(\ln G_i(x,y)\) 。

最后的 \(\exp\) 也同理（边界为 \(B_0=1\)）：

\[B(x)=\exp A(x)\Rightarrow B'(x)=B(x)A'(x)\\ B_{n}=\frac{1}{n}\sum_{i=0}^{n-1}B_i(n-i)A_{n-i} \]

后面的是异或卷积，做法和上面的一样。那么现在需要对 \(O(ck)\) 个方案做 \(k\) 次 FWT，复杂度是 \(O(c^2k^22^c+ck^4)\) 的，不太能通过。

考虑到不同的 \(A\) 只有 \(2^k\) 种，只需要对每种求 \(\ln\) 就行。此时复杂度为 \(O(ck^k2^c+k^22^k)\)，可以通过。

代码：Submission #130984817 - Codeforces

这篇关于【题解】CF1408I Bitwise Magic的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航