P3349:[ZJOI2016]小星星 – 题解

主要思路

怎么毫无头绪啊?(wtcl)不过有一说一,题目是真的挺好。

有一种接近正解的方式是设置 DP,设 \(dp[u][i][stat]\) 为当前在点 \(u\)、编号为 \(i\) 且被用过的编号集合为 \(stat\),然后做一个树形 DP。不难分析出这个东西的复杂度是 \(\Theta(n^3 3^n)\)。

这个肯定过不了的,考虑进行玄学优化。假设转移时能去掉第三个限制就好了。我们考虑抛弃这个第三维。抛弃之后必须要面对的一个问题就是非法状态。我们可以考虑硬点一个点集,使得整个 DP 的时候只能选点集内的编号。发现这样答案的意义是至少有 \(i\) 个重叠选择的点的方案数,所以我们可以愉快的套一个 \((-1)^{n – |S|}\) 系数就可以的出恰好为 \(0\) 个重叠选择的方案数了。

继续阅读P3349:[ZJOI2016]小星星 – 题解

Codeforces 434E:Furukawa Nagisa’s Tree – 题解

主要思路

这个题还蛮神仙的。主要的思路就是算三元组 \( (p_1, p_2, p_3) \),满足 \( G(S(p_1, p_2)) = G(S(p_2, p_3)) = G(S(p_1, p_3)) = x \)。我们先考虑 \(G(S(p_1, p_2)) = x\) 的 \((p_1, p_2)\)。假设我们能把这些路径全部求出来,并把这个仅包含有向边 \( S(p_1, p_2) \) 的有向图的入度、出度算出来。如果能算出这种东西的话,发现直接乘法原理可以算出非法的三元组(合法的三元组是没法搞的,因为你还得算 \( (p_1, p_3) \) 的东西才能搞)。如果规定时间内能搞定这个入度出度之后,我们直接 \(\Theta(n)\) 算掉乘法原理那个。搞入度出度可以直接上点分治。

继续阅读Codeforces 434E:Furukawa Nagisa’s Tree – 题解

LibreOJ#6374. 「SDWC2018 Day1」网格 – 题解

主要思路

容斥好题!

我们先不考虑 \(k\) 个非法向量的事。先考虑分两维做掉那个跳跃限制,再做掉不动的情况。

对于一维的跳跃限制,以 \(x\) 轴为例,可以做成一个组合数的容斥:

\[ \text{设} f(i) \text{为至少有} i \text{步超过了跳跃限制} \\ f(i) = {R \choose i} {T_x – i(Mx + 1) + R – 1 \choose R – 1} \\ ans_x = \sum_{i = 0}^R (-1)^i f(i) \]

继续阅读LibreOJ#6374. 「SDWC2018 Day1」网格 – 题解

BZOJ 4671:异或图题解

主要思路

我们发现,直接算一个连通块非常的困难。这个时候可以尝试容斥。我们发现至少一个的特别好算:划分至少\(i\)个连通块的答案记为\(g(i)\)。\(g(i)\)比较好算,可以考虑 DFS 枚举出每一个点所在的连通块根,然后把连通情况放入线性基中,如果线性基插入失败,那么说明当前的情况不能被表示出,且该状态符合划分,那么计入小答案\(tot\),最后对答案的贡献就是:\(2^{tot}\)。

现在考虑如何用\(g(i)\)算恰好\(i\)个连通块的答案\(f(i)\)。考虑搞下容斥系数,使得\(f(i)\)只被计算一次:

\[ \sum_{i = 1}^n \begin{Bmatrix} n \\ i \end{Bmatrix} coefficient(i) = [n = 1] \]

打表出来就是:

\[ coefficient(i) = (-1)^{i – 1} (i – 1)! \]

继续阅读BZOJ 4671:异或图题解