主要思路
狗屎状压题。
看到度数不超过 \(10\) 就知道需要状压儿子的信息。考虑处理一个 neck 数组来表示子树内节点到当前子树根下面的节点编号，然后我们每一次往上跳的时候我们都可以对这个数组进行调整，然后 DP 的时候就会比较愉快了。
处理 \(m\) 个请求的时候，我们把对应的 neck 提取出来，然后做标记，按标号小的进行 DP。
Continue reading →狗屎状压题。
看到度数不超过 \(10\) 就知道需要状压儿子的信息。考虑处理一个 neck 数组来表示子树内节点到当前子树根下面的节点编号，然后我们每一次往上跳的时候我们都可以对这个数组进行调整，然后 DP 的时候就会比较愉快了。
处理 \(m\) 个请求的时候，我们把对应的 neck 提取出来，然后做标记，按标号小的进行 DP。
Continue reading →看到这个很小的模数就知道肯定是个 Trick 题，一定不会让你去跑一般图的（估计是 NPC）。
首先，我们可以设颜色未标号的、用了 \(i\) 种颜色的方案数为 \(f_i\)，那么答案就是：
\[ ans = \sum_{i = 1}^k f_i k^{\underline{i}} \]
发现这个东西在 \(i > 2\) 时就直接被模成了 \(0\)。我们只需要算 \(f_1, f_2\) 即可。其中 \(f_1 = [m = 0]\)。\(f_2\) 的方案数等价于二分图的双部染色的方案数。所以，我们跑一边二分图然后算 \(2^b\) 即可，\(b\) 是连通块次数。
Continue reading →神仙题。
发现 \(x_1 \oplus x_2 = xorsum\)，所以我们尽量把 \(xorsum\) 的位分给 \(x_2\)。如果 \(xorsum\) 的某位为 \(1\)，那就直接给 \(x_2\) 就好；如果为 \(0\) ，那么有 \(0, 0\) 和 \(1, 1\) 两种情况。所以，我们构造线性基时，通过优先考虑为更高的 \(0\) 的位可以使得答案更大（我们考虑用线性基求最大异或和的过程，优先插入权更大的位置）。
Continue reading →这场代码都好短啊。
傻逼题，随便搞就行了。
// ARC091A.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
int main()
{
scanf("%d%d", &n, &m);
if (n > m)
swap(n, m);
if (n == 1)
{
if (m == 1)
puts("1");
else
printf("%d\n", max(0, m - 2));
return 0;
}
printf("%lld\n", max(0LL, 1LL * (n - 2) * (m - 2)));
return 0;
}
Continue reading → 其实就是做 \((1 + 2x^{a_i})\) 的异或卷积得组成 \(0\) 的方案。一种想法是做多次 FWT，但是这样铁定超时。我们考虑观察一下性质。
其实考虑 FWT 的变换就是：
\[ b_i = \sum_{j} (-1)^{cnt(i \& j)} a_j \]
Continue reading →