AtCoder Grand Contest 031 题解
A - Colorful Subsequence
题意
给定一个长度为 \(N\) 的字符串 \(S\)，求有多少非空子序列满足该子序列中的字符两两不同。对 \(10^9+7\) 取模。
子序列不要求连续。
\(N\le 10^5\)
题解
令 \(c_i\) 为字符 \(i\) 的出现次数。则答案为所有 \(c_i+1\) 的乘积。
由于子序列非空，答案需要减 \(1\)。
B - Reversi
题意
有 \(N\) 个石子，第 \(i\) 个石子颜色为 \(C_i\)。可以执行若干次以下操作：
- 选择两个颜色相同的石子，将这两个石子之间的石子的颜色都染成这两个石子的颜色。
求可以得到的不同序列数量。对 \(10^9+7\) 取模。
\(N\le 2\times 10^5\)
题解
最后的序列一定是若干段颜色相同的段组成的。
令 \(f_i\) 为以 \(i\) 作为最后一段结尾的序列数量。则有 \[f_i=\sum_{c_j=c_i,c_{j-1}\ne c_j} f_{j-1}\]
简单维护即可。
时间复杂度 \(O(N)\)。
C - Differ by 1 Bit
题意
给定 \(N,A,B\)，求一个 \(0\) 到 \(2^N-1\) 的排列 \(P\)，满足：
- \(P_0=A,P_{2^N-1}=B\)
- 对于任意 \(0\le i < 2^N-1\)，\(P_i\) 和 \(P_{i+1}\) 二进制表示恰好有一位不同。
或输出无解。
\(N\le 17\)
题解
显然 \(A\) 与 \(B\) 在二进制表示下有偶数位不同时一定无解。这是因为共修改了 \(2^N-1\) 次，而 \(2^N-1\) 是奇数，不可能最后有偶数位不同。否则我们可以构造证明有解。
记 \(p\) 为 \(A\) 与 \(B\) 的任意一位不同的二进制位。那么我们可以将第 \(p\) 位与 \(A\) 相同的数放在前半部分，与 \(B\) 相同的数放在后半部分。
我们可以枚举中间分界处的数 \(S\)，注意到一定存在这样的 \(S\) 满足 \(S\) 与 \(A\) 和 \(B\) 分别有奇数位不同。
于是我们可以递归到两个 \(N-1\) 位的子问题。
时间复杂度 \(O(2^NN)\)。
D - A Sequence of Permutations
题意
令 \(p,q\) 为两个 \(1\) 到 \(N\) 的排列，定义 \(f(p,q)\) 为位置 \(p_i\) 为 \(q_i\) 的排列。
给定排列 \(p,q\)，定义序列 \(\{a_n\}\) 如下：
- \(a_1=p,a_2=q\)
- \(a_{n+2}=f(a_n,a_{n+1})\)
给定整数 \(K\)，求 \(a_K\)。
\(N\le 10^5,K\le 10^9\)
题解
根据题意，有 \[ f(p,q)= \begin{pmatrix} p_1 & p_2 & \ldots & p_N \\ q_1 & q_2 & \ldots & q_N \end{pmatrix} \]
根据置换乘法的定义，有 \[ \begin{pmatrix} 1 & 2 & \ldots & N \\ p_1 & p_2 & \ldots & p_N \end{pmatrix} \begin{pmatrix} p_1 & p_2 & \ldots & p_N \\ q_1 & q_2 & \ldots & q_N \end{pmatrix} = \begin{pmatrix} 1 & 2 & \ldots & N \\ q_1 & q_2 & \ldots & q_N \end{pmatrix} \]
即有 \[p\cdot f(p,q)=q\]
即 \[f(p,q)=p^{-1}q\]
另外，置换乘法有性质 \[(ab)^{-1}=b^{-1}a^{-1}\]
于是可以得到 \[ \begin{aligned} a_1 & = p \\ a_2 & = q \\ a_3 & = p^{-1}q \\ a_4 & = q^{-1}p^{-1}q \\ a_5 & = q^{-1}pq^{-1}p^{-1}q \\ a_6 & = q^{-1}p^2q^{-1}p^{-1}q \\ a_7 & = q^{-1}pqpq^{-1}p^{-1}q \\ a_8 & = q^{-1}pqp^{-1}qpq^{-1}p^{-1}q \end{aligned} \]
令 \(r=q^{-1}pqp^{-1}\)，可以归纳证明有 \[a_n=ra_{n-6}r^{-1}\]
求一个置换的幂次可以通过求出该置换的每个循环 \(O(N)\) 实现。
时间复杂度 \(O(N)\)。
E - Snuke the Phantom Thief
题意
平面上有 \(N\) 个点，第 \(i\) 个点在 \((x_i,y_i)\)，价值为 \(v_i\)。
你需要选择若干个点，有 \(M\) 个限制，第 \(i\) 个限制为横坐标/纵坐标小于等于/大于等于 \(a_i\) 的点最多只能选 \(b_i\) 个。
求选择的点的最大价值和。
\(N\le 80,M\le 320,1\le x_i,y_i,a_i\le 100,1\le v_i\le 10^{15}\)
题解
先考虑限制只有小于等于的情况。
考虑建立费用流模型，建立左右两排点。
对于左边第 \(i\) 个点，该点只有唯一一条入边，该入边的流量为横坐标小于等于 \(i\) 的点被选择的数量。
该点有若干出边，其中一条连向第 \(i-1\) 个点，流量表示横坐标小于等于 \(i-1\) 的点被选择的数量，其余边连向右边的点，流量表示是否选择一个横坐标为 \(i\)，纵坐标为右边对应点的编号的点。
另外，源点连向左边最后一个点，流量表示总共被选择的点数。
右边的点同理。
这样子建图相当于原题每个限制会对左边或右边某条边的流量上界产生限制，而每个点对应左边到右边的一条边。
回到原题，考虑枚举总点数 \(s\)，那么相当于每个坐标大于等于某个值的数量的上界限制可以转化为坐标小于等于某个值的数量的下界限制，也即会对左边或右边某条边的流量产生下界限制。
跑上下界费用流即可。
F - Walk on Graph
题意
给定一个 \(N\) 个点 \(M\) 条边的边带权无向连通图 \(G\) 和一个奇数 \(P\)，回答 \(Q\) 次询问，第 \(i\) 个询问为：
- 判断 \(S_i\) 到 \(T_i\) 是否存在一条路径使得该路径的权值在模 \(P\) 意义下与 \(R_i\) 相等。
路径可以经过重复点、重复边。
路径的权值定义为，若一条路径依次经过的边的边权为 \(L_0,L_1,L_2,\ldots,L_{k-1}\)，那么该路径的权值为 \(\sum_{i=0}^{k-1} L_i\times 2^i\)。
\(N,M,Q\le 50000,P\le 10^6\)
题解
若无注明，以下涉及权值有关运算均在模 \(P\) 意义下进行。
将路径反过来，这样相当于每经过一条边权为 \(c\) 的边，权值从 \(x\) 变为 \(2x+c\)。
记状态 \((u,x)\) 为当前在节点 \(u\)，权值为 \(x\)。那么询问相当于判断 \((t,0)\) 是否可以到达 \((s,r)\)。
令 \(f(x)=2x+c\)，由于 \(P\) 是奇数，\(2\) 有逆元，所以 \(f\) 是一个双射，若 \(x\) 向 \(f(x)\) 连边，最终一定会形成若干个环。
考虑一条边 \((u,v,c)\)，状态 \((u,x)\) 一定可以来回通过这条边最终回到 \((u,x)\)。这就意味着 \((u,x)\) 可以到达 \((v,2x+c)\)，\((v,2x+c)\) 也可以到达 \((u,c)\)，也即状态之间的边是双向的。接下来我们称两个状态等价当且仅当他们连通。
若同时存在边 \((u,v,a)\) 和 \((u,w,b)\)，那么有 \((u,x)\to (v,2x+a)\to (u,4x+3a)\) 和 \((u,x)\to (w,2x+b)\to (u,4x+3b)\)，即 \((u,4x+3a)\) 和 \((u,4x+3b)\) 是等价的。
\(4\) 也存在逆元，那么 \(4x+3a\) 可以取到任何值，所以有 \((u,x)\) 和 \((u,x+3(b-a))\) 等价。
我们求出任意两条边边权之差的 \(\gcd\)，记为 \(g\)。由于图是连通的，我们可以从一个状态 \((u,x)\) 出发，走到每个点对 \(x\) 进行若干次变换，最终可以到达状态 \((u,x+3g)\)。也就是说 \((u,x)\) 与 \((u,x+3g)\) 是等价的。
于是我们可以将 \(P\) 置为 \(\gcd(P,3g)\)。
注意到此时所有边边权模 \(g\) 相等，置为 \(z\)。我们可以把所有边边权减 \(z\)，状态中的第二维（即路径权值）增加 \(z\)。这样原来的状态 \((u,x)\) 对应现在的状态 \((u,x+z)\)。这样原来的转移 \((u,x)\to (v,2x+c)\) 对应现在的转移 \((u,x+z)\to (v,2(x+z)+c-z)=(v,2x+c+z)\)，仍然正确。
那么现在从状态 \((u,x)\) 出发能到达的状态一定都能表示成 \((v,2^px+qg)\) 的形式。由于 \((u,x)\) 和 \((u,x+3g)\) 等价，我们可以将 \(q\) 的运算在模 \(3\) 意义下进行而不影响答案。
另外，因为 \((u,x)\to (v,2x+c)\to (u,4x+3c)=(u,4x)\)，我们可以将 \(p\) 的运算在模 \(2\) 意义下进行而不影响答案。
由于是询问 \((t,z)\) 是否能到达 \((s,r+z)\)，那么我们只需要保留能表示成 \((u,2^pz+qg)\) 的状态，连边时将 \(p,q\) 分别在模 \(2\) 和模 \(3\) 意义下进行即可。
对于每个询问，我们可以通过预处理快速得到 \(r+z\) 对应的所有 \(p,q\) 分别在模 \(2\) 和模 \(3\) 意义下两两不同的二元组 \((p,q)\)，判断是否在同一连通块内即可。
连边和判断是否连通若用 DFS 和预处理的方法实现，时间复杂度 \(O(N+M+Q+P)\)。
