Contest Info

date: 2018.08.11 12:00-17:00

practice link

Solutions

A. Connecting segments

题目大意：

有\(n\le1000\)个非零的二维向量，第\(i\)个向量的颜色为\(c_i\).

对于\(k\in[1,n]\)，询问至多选择\(k\)个向量（相同颜色的向量最多选择一个）时，选择的向量和的模长平方最大是多少？

不保证不存在三点共线，不保证不存在相同的向量。

题解：

这题的核心思想同Large Traiangle：

如果将\(\vec{AB}\)的法向量放在单位圆上，当\(\vec{v}\)与该法向量重合时，\(\vec{OA}.dot(\vec{v})=\vec{OB}.dot(\vec{v})\)，而在法向量的一侧满足\(\vec{OA}.dot(\vec{v})<\vec{OB}.dot(\vec{v})\)，另一侧满足\(\vec{OA}.dot(\vec{v})>\vec{OB}.dot(\vec{v})\)。

假设我已经知道了最优解的方向向量\(\vec{v}\)，因为\((\vec{OA}+\vec{OB})\cdot\vec{v} = \vec{OA}\cdot\vec{v} + \vec{OB}\cdot\vec{v}\)，因此我们取前\(k\)大的向量加起来更新答案即可，不能选择同种颜色就只考虑每种颜色最优的向量即可。

虽然我并不知道最优解的方向向量，但是偏序发生变化的关键方向只有\(O(n^2)\)个，按极角序扫一遍即可。

这题的难点在于数据不保证不存在三点共线，不保证不存在相同的向量。

在Large Traiangle一题中，由于保证了没有这些恶心的情况，可以直接对这些关键法向量排序，当扫到\((i,j)\)的法向量时，他们一定在偏序中相邻。

但在这题中，这种写法就要处理一堆相等的元素无序的黏在一起的情况，当方向改变时，难以正确地将其分开。

因此，我们可以学习出题人优秀的写法，用set维护当前偏序中\(n-1\)对相邻元素的法向量（相邻的相同向量无视）的极角序，这样我们扫到的事件依然是交换两个相邻的元素，是否存在共线都不会影响，并且set中的所有法向量都在当前枚举的法向量的左半平面内。

交换相邻的两个位置时，如果不改变某种颜色的最优向量，那么只会有\(2\)个位置的向量前缀和发生改变，重新计算后更新答案即可。

否则交换了同一颜色的最优与次优向量，需要重新计算一个后缀的前缀和，但这种情况不会超过\(O(n)\)次，不影响复杂度。

时间复杂度\(O(n^2\log{n})\)，空间复杂度\(O(n)\).

C. Count Paths

题目大意：

给出一个\(n\le2\times10^5\)个节点的树，对于树中的一个连通子集\(S\)，定义\(f(S)\)等于不包含\(S\)中的点，且能覆盖所有与\(S\)邻接的点的路径集合（\((u,v)\)和\((v,u)\)算同一条路径，\((x,x)\)合法）。求所有连通子集\(S\)的\(f(S)\)之和。

题解：

方法一：

点分治，强制连通子集包含分治中心

\[ dp[u] = 2^{sz[u](sz[u]+1)/2} - 2^{\sum_{v\in son(u)} sz[v](sz[v] + 1)/2} + \prod_{v\in son(u)} dp[v] \]

之后删去分治中心，给分治中心的邻点加一个虚点代替之后的分治中不会再被访问到的所有点，不允许连通子集包含这个虚点即可。

时间复杂度\(O(n\log{n})\)，常数较小的写法可以通过本题。

方法二：

将路径集合覆盖的点染色，那么这个路径集合对于未被染色的连通块都有合法的贡献。

连通块个数为未被染色的点数减去两个端点都未被染色的边数。

对于每个点求不经过它的路径集合数，对于每条边求不经过它的路径集合数，作差即得到了答案。

树dp（dfs）一次即可，时间复杂度\(O(n)\).

H. Playing games

题目大意：给 \(n\le 5\times10^{5}\) 个数（范围 \(5\times 10^{5}\)），问最多能选多少个使得它们异或和为 \(0\)。

题解：记 \(n\) 个数的和为 \(\text{sum}\)。从反面思考，即为最少选多少个数使得它们的异或和为 \(\text{sum}\)。我们以每个数为一行，构造一个模 \(2\) 意义下的矩阵，易知它有一组大小不超过 \(19\) 的基，也就是说我们可以用不超过 \(19\) 个向量表示 \(\text{sum}\)。

设 \(f(x)=\sum_{i=0}^{2^{19}}\text{cnt}_{i}x^{i}\)，在异或卷积的意义下定义多项式乘法，那么 \([x^{j}]f^{i}(x)\) 就表示用 \(i\) 个数（可能重复）表示 \(j\) 的方案数。于是我们可以依次计算 \([x^{\text{sum}}]f^{0}(x),[x^{\text{sum}}]f^{1}(x),\cdots\)，直到它大于 \(0\) 为止。虽然之前我们说选取的数可以重复，但是最少的能表示出 \(\text{sum}\) 的数肯定是不会重复的，所以这并没有影响。

由于乘了几次以后系数就会变得很大，所以要取模，恰好被模数整除的概率很小，如果实在不放心可以多取几个模数。

如果每次都逆 \(FWT\)，复杂度为 \(\mathcal{O}(n\log^{2} n)\)。但事实上我们没有必要这样做，每次乘法后我们只需要知道 \(x^{\text{sum}}\) 的系数，这一项我们很容易 \(\mathcal{O}(n)\) 求出，而不需要将整个多项式逆 \(FWT\)。

时间复杂度 \(\mathcal{O}(n\log n)\)。

J. Calculating sums

题目大意：给出 \(n\le10^{9},m\le10^{6},k\le10^{9}\)，计算 \(\sum_{i=0}^{n}\sum_{j=0}^{m}{i\choose j}[i\equiv0\pmod{2}][j\equiv0\pmod{2}]\)。

题解：不妨先把 \(n\) 和 \(m\) 向下取到偶数。设 \(\displaystyle{f(x)=(x+1)^{0}+(x+1)^{2}+\cdots+(x+1)^{n}=\frac{(x+1)^{n+2}-1}{(x+1)^{2}-1}}\)，那么答案为 \(\sum_{i=0}^{m}[i\equiv0\pmod{2}][x^{i}]f(x)\)。我们有 \(\displaystyle{f(x)=\frac{\sum_{i=0}^{n+1}{n+2\choose i+1}x^{i}}{x+2}}\)。这个除法很容易计算，我们有 \([x^{i}]f(x)+2[x^{i+1}]f(x)={n+2\choose i+2}\)。

我们将 \(k\) 分解为 \(s\cdot2^{t}\)，其中 \(s\) 是奇数。显然我们可以在模 \(s\) 和 \(2^{t}\) 的意义下分别计算然后 \(CRT\)。模 \(s\) 的时候，\(2\) 存在逆元，可以直接递推，只需要在算组合数时注意单独处理 \(s\) 中的质数即可。这部分的复杂度为 \(\mathcal{O}(m\log s)\)。模 \(2^{t}\) 的时候，我们不能直接递推了（否则要除 \(2\)）。注意到 \([x^{i}]f(x)=\sum_{j=0}^{+\infty}(-2)^{j}{n+2\choose i+j+2}\)，而 \(j\ge t\) 的所有项在模 \(2^{t}\) 意义下就都为 \(0\) 了，所以我们可以计算 \(\sum_{j=0}^{t-1}(-2)^{j}{n+2\choose i+j+2}\)。这部分的复杂度为 \(\mathcal{O}(mt)\)。

总复杂度 \(\mathcal{O}(m\log k)\)。

K. Decoding graphs

题目大意：给出一个 \(n(n\le13)\) 个点的无向图，每个点有一个权值 \(a_{i}\)，求满足下列条件的 \(b_{i}\) 的方案数：

• \(\forall1\le i\le n,0\le b_{i}\le a_{i}\)
• \(\bigoplus_{i=1}^{n}b_{i}=c\)
• 若 \(u,v\) 之间有边相连，\(b_{u}\neq b_{v}\)

题解：设 \(P\) 是 \(V\) 的一个划分，\(f(P)\) 表示 \(P\) 中所有集合内部的 \(b_{i}\) 相等，集合间随意的方案数。考虑计算每一个 \(P\) 的容斥系数。定义 \(g(S)=[S是独立集]-\sum_{P是S的划分,|P|\ge2}\prod_{T\in P}g(T)\)。我们归纳地证明：\(f(P)\) 的容斥系数 \(c(P)=\prod_{S\in P}g(S)\)。

定义 \(P'\) 是 \(P\) 的子划分，当且仅当 \(P'\) 的任意一个元素都是 \(P\) 的某个元素的子集。为了方便记 \(P'\subset P\)。

当 \(P=\{\{1\},\{2\},\cdots,\{n\}\}\) 时，显然有 \(c(P)=1=\prod_{S\in P}g(S)\)。

当 \(|P|<n\) 时 \[ \begin{aligned} c(P)&=\prod_{S\in P}[S是独立集]-\sum_{P'\subset P,P'\neq P}c(P)\\ &=\prod_{S\in P}[S是独立集]-\prod_{S\in P}\sum_{P'是S的划分}g(P')+\prod_{S\in P}g(S)\\ &=\prod_{S\in P}g(S)\Box \end{aligned} \] 我们有 \[ [S是独立集]=\sum_{P是S的划分}\prod_{T\in P}g(T)=\sum_{k=0}^{+\infty}\frac{1}{k!}\sum_{\bigcup_{j=1}^{k}S'_{j}=S,\bigcap_{j=1}^{k}S'_{j}=\emptyset}\prod_{j=1}^{k}g(S'_{j}) \] 设 \(H\) 是一个集合幂级数，其中 \(H^{S}=[S是独立集]\)，\(G\) 是 \(g\) 的集合幂级数，在子集卷积的意义下定义乘法，则有 \(H=e^{G}\)，因此 \(G=\ln H\)。我们可以在 \(\mathcal{O}(n^{3}2^{n})\) 的时间内计算出 \(G\)。

下面考虑 \(f(P)\) 的计算方法：对于 \(P\) 中大小为偶数的集合 \(S\)，它们异或后的值恒为 \(0\)，我们只需要在最后结果中乘上 \(\min S+1\) 即可；对于 \(P\) 中大小为奇数的集合，相当于其中只有一个数。下面我们以对全集 \(V\) 进行计算为例，不妨设 \(a_{n}\) 是其中最大的数：

• 若 \(highbit(a_{n})<highbit(x)\) 那么显然答案为 \(0\)。
• 否则考虑 \(b_{n}\) 是否取 \(a_{n}\) 的最高位
  • 若取，那么答案相当于 \((a_{1},\cdots,a_{n-1},a_{n}\oplus highbit(a_{n}))\) 和 \(c\oplus highbit(a_{n})\) 的答案。递归计算即可。
  • 若不取，那么只要 \(b_{1}\oplus b_{2}\oplus\cdots\oplus b_{n-1}\oplus c\) 的最高位小于 \(highbit(a_{n})\)，就一定可以找到相应的 \(b_{n}\)，这样的方案数很容易 \(dp\) 求出。

时间复杂度 \(\mathcal{O}(bell(n)n)\)。其中 \(bell(n)\) 表示贝尔数。

Dirt Replay

Replay 个屁 慌得一批