主要思路
首先先把 \(y\) 除掉一个 \(x\)，并且我们发现可以用 \(2^{t – 1}\) 来算这个和为 \(y\) 的数列的个数。
知道这个之后，我们发现可以枚举 \(\frac{y}{x}\) 的质因子情况进行容斥。
Continue reading →首先先把 \(y\) 除掉一个 \(x\)，并且我们发现可以用 \(2^{t – 1}\) 来算这个和为 \(y\) 的数列的个数。
知道这个之后，我们发现可以枚举 \(\frac{y}{x}\) 的质因子情况进行容斥。
Continue reading →怎么毫无头绪啊？（wtcl）不过有一说一，题目是真的挺好。
有一种接近正解的方式是设置 DP，设 \(dp[u][i][stat]\) 为当前在点 \(u\)、编号为 \(i\) 且被用过的编号集合为 \(stat\)，然后做一个树形 DP。不难分析出这个东西的复杂度是 \(\Theta(n^3 3^n)\)。
这个肯定过不了的，考虑进行玄学优化。假设转移时能去掉第三个限制就好了。我们考虑抛弃这个第三维。抛弃之后必须要面对的一个问题就是非法状态。我们可以考虑硬点一个点集，使得整个 DP 的时候只能选点集内的编号。发现这样答案的意义是至少有 \(i\) 个重叠选择的点的方案数，所以我们可以愉快的套一个 \((-1)^{n – |S|}\) 系数就可以的出恰好为 \(0\) 个重叠选择的方案数了。
Continue reading →这个题还蛮神仙的。主要的思路就是算三元组 \( (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)\) 算掉乘法原理那个。搞入度出度可以直接上点分治。
容斥好题！
我们先不考虑 \(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) \]
我们发现，直接算一个连通块非常的困难。这个时候可以尝试容斥。我们发现至少一个的特别好算：划分至少\(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)! \]