LibreOJ Anniversary Cup 题解

liu_cheng_ao 2018-06-17 22:21:21 2018-11-23 13:26:56

Day 1

A. ZQC 的迷宫

By Snakes,题解 By Snakes

  • 送分
  • 思维难度:普及
  • 实现难度:普及-

这位同学,您就没有听说过,手摸着墙壁走一定能走出传统迷宫吗?

不妨冷静分析,若迷宫为 n\times m ,则两两相邻方格之间与边界边数总共为 2nm+n+m ,方格之间联通且形成一棵树,删去边数为 nm-1 ,也即包含边界情况下,一个合法的迷宫边数为 nm+n+m-1 。边界其中至多一半会经过一次,其余则不会经过,内部边可能经过两次,因此摸着墙壁前进的步数上限为 2(nm+n+m-1)-3(n+m) ,即 2nm-n-m-2 。题目数据范围中 l\geq 2nm\geq 2nm-n-m-2 ,因此摸着墙壁走这种做法是可行的。初始时你面向右侧,因此你左侧一定有墙,所以你只需要一直沿着左侧墙壁走即可。

由于墙都是联通的,墙的表面必然形成了一个长度不超过 2nm-2 的环,所以这题就是:

给你一个环,你可以前进一步,可以后退一步,可以检查是否在目标点,让你走到目标点。

这都不会,退群吧。

通过上述分析,我们设计出了一个时间复杂度非常优秀的 O(nm) 算法:

while(!reach_dest())move_left();

时间复杂度: O(nm)
预计得分: 100

B. Menci 的序列

By CommonAnts,题解 By CommonAnts

  • 构造
  • 思维难度:提高+
  • 实现难度:提高

算法一

可能的答案只有 2^k 种,直接 f[i][j] 记录下前 i 位的子序列能否得到 j ,递推即可。

时间复杂度: O(n2^k)
预计得分: 15

算法二

可以发现,超过 2^k 的部分是没有意义的,且这部分可以通过删除所选序列中的一些 + 来消除。这样,我们限定序列的值域是 [0,2^k)

这样,每个 + 的贡献就是 2^c ,其中 c 表示这个 + 后面 * 的个数。

我们从后往前考虑。可以注意到,如果当前已经有 x *,那么后面的操作不会影响到答案的后 x 位。这样,我们可以设计一个位背包 DP: f[i][j][k] 表示考虑后 i 位,用了 j *,当前值整除 2^j 的结果为 k 的情况下后 j 位的最大值。如果加上一个 *,那么 f[i+1][j][k]+(k\bmod 2)\cdot 2^j 转移到 f[i][j+1][\lfloor k/2\rfloor] ;如果加上一个 + 那么 f[i+1][j][k] 转移到 f[i][j][k+1]

三维状态数分别是 n,k,n ,加上高精度的复杂度 O(\frac{k}{w}) w 表示位长度,LibreOJ 为 64 ),总复杂度 O(\frac{n^2k^2}{w})

时间复杂度: O(\frac{n^2k^2}{w})
预计得分: 30

算法三

我们可以发现一个事实:

对于一个数 x ,考虑其经过两次运算生成的集合 F(x,a,b)=\{y:y=(x+i)*2+j,i=0\dots a,j=0\dots b\} ,可以注意到:

引理 1 b>2 时, F(x,a,b)=F(x,a+1,b-2)

那么我们可以以此依据调整序列。具体而言,每个右侧有大于 2 +*,都可以把右侧的两个 + 换成左侧的一个 +

如此处理之后,我们可以得到一个与原序列等价的序列,从右到左计算并记录当前 + 的个数即可。为了方便我们在原序列开头补充分多个 *,显然这不会影响答案,因为操作序列开头的 * 0 无效。于是我们也可以删去最后得到的序列开头多余的 *

这样,我们得到了一个序列 s' ,它的开头是 +(或整个序列为空,那么答案为 0 ),且每段连续的 + 不超过 2 个。注意到这样的序列长度是 O(k) 的,因为当 + 段数不少于 k 时答案一定是 2^k-1 ,只需交错地取 +* 即可。

这样上面 DP 的时间复杂度就是 O(n+\frac{k^4}{w}) 了。当然它还不够优秀,继续优化:

引理 2 s' 中存在一种最优方案使得除最后一段外,每段 * 至少选了一个。

证:考虑调整法。对于一段 *,如果最优解中前面没有选择任何 +,直接选上 * 不影响答案;
否则,如果前面还有另一个 *,我们将前面最近的 * 替换为这一个,增加的值为中间的若干个 +,设为 c 个,那么我们将这些 + 保留 \lfloor \frac{c}{2} \rfloor \lceil \frac{c}{2}\rceil 个,必然可以通过调整这段 * 后面紧邻的 +(增加一个或者删除一个)来得到一个相等的答案,且 * 向后移动了一位;
如果前面没有另一个 * 了,只需认为前面一个 * 在无穷远处再调整即可。
这样,我们的 * 只会向后移动,调整法必定会在有限步内结束。证毕。

这时我们再去运行上面的 DP,第三维的大小将是常数 —— 因为每段向前进位都会被整除 2 ,且段长度是常数。于是时间复杂度是 O(\frac{k^3}{w})

时间复杂度: O(n+\frac{k^3}{w})
预计得分: 30 50

算法四

我们需要继续优化。

引理 3 s' 中存在一种最优方案满足引理 2 的条件且每段 + 至少选了一个。

证:考虑一段没选择的 +,如果后面至少选了 k*,那么对答案没有影响,可以选;
否则,如果后面没有进位,直接选一个对前后的位都没有影响,必然更优;
否则,考虑其后最近的一段进位,必定是 *+*+*...+*++ 的形式,在这一段选择一个 + 之后,删去最后两个 +,不会对前面的位造成影响,且答案不变劣,且没有 + 的段向后移动。
这样,我们没有 + 的段只会向后移动,调整法必定会在有限步内结束。证毕。

引理 4 s' 中存在一种最优方案满足引理 3 的条件且存在一个位置,其后两个位置都是 *,后面所有位置全选,前面(不包括这两个 * 所在的一段)每段 * 恰好选了一个。

证:两个 * 足以隔断后面的选择对前面位的影响,则如果后面的 * 个数不足 k ,后面的 + 必然全选,这样答案不会变劣。
并且,考虑最前出现一段选择至少两个 * 且后一段 * 没有全选的位置:令后一段多选一个 *,本段少选一个。如果两段之间选了两个 +,那么改成一个答案不变;否则由于此时后一段至少有两个 *,足以隔断后面的选择对前面位的影响,答案一定不会变劣;
于是,存在一种最优方案使得最早出现连续两个 * 的位置之后全选。证毕。

这样,我们可以枚举这个位置然后计算:前面的部分由于每段恰好选一个 *,如果前后 * 的个数之和不小于 k-1 ,前面的位必然全是 1 ;否则前面必然全选最优,因为不可能超过 2^k

时间复杂度: O(n+\frac{k^2}{w})
预计得分: 50

算法五

我们可以对算法四的方案稍加分析。考虑第一次达到前后 * 的个数不小于 k-1 的时刻:由于连续两个 * 后面的部分不会再改变,此时前面达到全 1 已经是最优解;同样,如果我们选择更少的 *,如果少了两个以上一定更劣;如果只少一位,后面的位不变,前面的全 1 部分不会增加(至多在全为两个 + 的情况下不变),一定不会更优。

于是这就是最优解。注意两种特殊情况,不存在一段 * 中选择不少于 2 个,或者 * 的总数不足 k-1

以及注意引理 2 的例外,最后一段 * 的影响:如果至少选了两个,它满足引理 4 的条件,可以一并计算;否则相当于前面做 k 1 的情况,特判即可。

时间复杂度: O(n)
预计得分: 100

如果没有注意到引理 1 的转化,可以解决子任务 4。

C. CommonAnts 的调和数

By CommonAnts,题解 By CommonAnts

  • 数论递推,埃氏筛法
  • 思维难度:NOI
  • 实现难度:NOI-

算法一

直接模拟。

时间复杂度: O(n(m+q))
预计得分: 15

算法二

合并相同的 p,k 后模拟。

时间复杂度: O(n \log n)
预计得分: 30

算法三

高维前缀和:我们将每个数看做每种质因子为一维的空间中的一个点,坐标是该种质因子的次数。那么我们做一个高维前缀和即可。

所乘的系数只需在高位前缀和递推时乘上与下标之比相同的系数即可。

总时间复杂度为 \sum_{i=1}^n \omega(i) = O(n \log \log n)

时间复杂度: O(n \log \log n)
预计得分: 50

算法四

分别算每个修改对每个询问的贡献,算出它们的最小公倍数再乘系数即可。

时间复杂度:不超过 O(mq\log n)
预计得分: 30 ,结合前述可得 65

算法五

只考虑所给出的 10 种质因子组成的数即可, n 以内这样的数最多只有不足 2\times 10^5 个。于是我们对这样的数计算前缀和。其它数的贡献在它们中这些质因子组成的因数处统计,这样我们要计算每种数的所有与这 10 个质因子互质的数倍中不超过 n 的数之和。我们用一个递推 f[i][j] 表示与前 i 个数互质的不超过 j 的数的和,计算即可。注意到 j 必然是某个 \lfloor \frac{n}{x}\rfloor ,于是只有 O(\sqrt{n}\omega) 种,其中 \omega 表示这些数的质因子个数。

时间复杂度:不超过 O((N+\sqrt{n})\omega) ,其中 N 表示 n 以内只含这些质因子的数的个数。
预计得分: 100

D. Tangjz 的背包

By Tangjz,题解 By Tangjz

  • 动态规划、生成函数、等比数列求和
  • 思维难度:NOI+
  • 实现难度:提高+

10 :暴力
45 :FFT
65 :一段lucas定理
100 :两段lucas定理

—— tangjz 于 LibreOJ 用户群

算法一

注意到 p = n + (n - 1) + \cdots + (n - m + 1) = \frac{m (2 n - m + 1)}{2} ,我们只关心 \sum_{v}{q^v f_{n, m}(v)} 的取值,其中 q \equiv 19190506^{-1} \pmod{998244353}

F(n, m) = \sum_{v}{q^v f_{n, m}(v)} ,则 F(n, 0) = 1 , F(0, m) = [m = 0]

考虑第 n 个物品选或是不选,存在两种转移: f_{n, m}(v) \gets f_{n-1, m-1}(v - n) f_{n, m}(v) \gets f_{n - 1, m}(v)

相应地有 F(n, m) = q^n F(n - 1, m - 1) + F(n - 1, m) 。递推计算即可,时间复杂度 \mathcal{O}(n m)

同理,如果定义 G(n, m) = \sum_{v}{k^{p - v} f_{n, m}(v)} ,则有 G(n, 0) = 1 , G(0, m) = [m = 0] , G(n, m) = G(n - 1, m - 1) + k^m G(n - 1, m)

算法二

对于 n 很少的情况,尝试得到所有 m (1 \leq m \leq n) 的信息。

定义关于 z 的多项式 P_n(z) = \sum_{m}{F(n, m) z^m} ,于是有 P_0(z) = 1 , P_n(z) = (1 + q^n z) P_{n - 1}(z) ,整理得 P_n(z) = \prod_{i = 1}^{n}{(1 + q^i z)}

分治计算这 n 个多项式的乘积即可,对于单个 n 的时间复杂度为 \mathcal{O}(n \log^2 n) ,卷积计算可以使用快速数论变换进行加速。

n 升序处理多组询问,可以做到 \mathcal{O}(N \log^2 N + T' n \log n) ,其中 N 表示 n 的最大值, T' 表示不同 n 的数量。

算法三

P_n(z) = (1 + q z) (1 + q^2 z) \cdots (1 + q^n z) 可得 P_{n - 1}(z) (1 + q^n z) = (1 + q z) P_{n - 1}(q z)

P_n(z) = \sum_{m}{F(n, m) z^m} 带入等式,观察 z^m 的系数可得 F(n - 1, m) + q^n F(n - 1, m - 1) = q^m F(n - 1, m) + q^m F(n - 1, m - 1)

整理得

F(n - 1, m) = q^m \frac{1 - q^{n - m}}{1 - q^m} F(n - 1, m - 1)

F(n, m) = q^{\frac{m (m + 1)}{2}}\frac{(1 - q^n) (1 - q^{n - 1}) \cdots (1 - q^{n - m + 1})}{(1 - q)(1 - q^2) \cdots (1 - q^m)}

[n]_q = \sum_{i = 0}^{n - 1}{q^i} = \frac{1 - q^n}{1 - q}, [n]_q! = [1]_q [2]_q \cdots [n]_q ,则 F(n, m) = q^{\frac{m (m + 1)}{2}} \frac{[n]_q!}{[m]_q! [n - m]_q!}

\alpha 表示最小的正整数使得 q^{\alpha} \equiv 1 \pmod{998244353} ,测试得到 \alpha = 917504

对于 n, m \leq 10^6 的情况, [m]_q 只有 m = \alpha 时会出现无法用模意义下非 0 的整数表示的情况,而此时 n - m 不会取到 \alpha ,因此只需要判断一下分子和分母里是否出现过 [\alpha]_q 即可,其他情况可以通过预处理 [n]_q 解决。时间复杂度 \mathcal{O}(N + T \log n)

算法四

对于 n, m \leq 10^{12} 的情况,需要特殊考虑 [\alpha]_q , [2 \alpha]_q , \cdots

不难发现,它们可以规约到相同的形式: [k \alpha]_q = \frac{1 - q^{k \alpha}}{1 - q} = \frac{1 - q^{k \alpha}}{1 - q^{\alpha}} \frac{1 - q^{\alpha}}{1 - q} = k [\alpha]_q

因此, [n]_q! 可以表示成 {\left \lfloor \frac{n}{\alpha} \right \rfloor}! ([\alpha]_q!)^{\left \lfloor \frac{n}{\alpha} \right \rfloor}[n \bmod \alpha]_q! ,除了 [\alpha]_q 之外,其他内容都可以用模意义下非 0 的整数表示。

显然,当 0 \leq m \leq n 时有 \left \lfloor \frac{n}{\alpha} \right \rfloor \geq \left \lfloor \frac{m}{\alpha} \right \rfloor + \left \lfloor \frac{n - m}{\alpha} \right \rfloor ,所以分母的 [\alpha]_q 都会被消去,只需要判断一下上述不等式是否取到等号即可。

时间复杂度 \mathcal{O}(\alpha + \frac{N}{\alpha} + T \log n)

Day 2

A. Snakes 的 Naïve Graph

By Snakes,题解 By Snakes

  • 数论,线性筛
  • 思维难度:提高
  • 实现难度:提高-

n=O(r) ,以下默认 l,r n 同阶。

算法一

引理一 对于 G(m) 中的任意一点,其度数小于等于 2

证明 对于小于 m 且与 m 的正整数 i ,其模 m 意义下乘法逆元唯一。

引理二 若模 m 意义下乘法逆元非自身的数的个数为 g(m) ,则 f[G(m)]=2^{g(m)/2}

证明 G(m) 可以被划分为若干不联通子图,对于模 m 意义下乘法逆元非自身的数 i i_X, i^{-1}_X, i_Y, i^{-1}_Y 之间两两有边,则选择 i_X\rightarrow i_Y, i^{-1}_X\rightarrow i^{-1}_Y i_X\rightarrow i^{-1}_Y, i^{-1}_X\rightarrow i_Y 中任意一组匹配均不改变其最大匹配数。对于乘法逆元为自身或不存在乘法逆元的数 j j_X 仅与 j_Y 连边,因此在最大匹配中 j_X 只能与 j_Y 匹配。根据乘法原理可得 f[G(m)]=2^{g(m)/2}

每次询问对 l\leq m\leq r m 暴力构造 G(m) 并计数,枚举 m 以及小于 m 的正整数 i ,并枚举其逆元。

时间复杂度: O(qn^3)

期望得分: 10

算法二

预处理 G(m) 并计数,枚举 m 以及小于 m 的正整数 i ,在模 m 意义下若其乘法逆元 i^{-1} 存在则 i^{-1}=i^{\varphi(m)} 。对答案前缀和,查询时相减即可。

时间复杂度: O(n^2\log n+q)

期望得分: 19

算法三

引理三 若在 G(m) 中,对于 1\leq i,j\leq m-1 的正整数 i,j ,若 i_X j_Y 有边,则 (m-i)_X (m-j)_Y 有边。

证明 对于 i=j 情况显然,对于 i\neq j (m-i)(m-j)=m^2-mi-mj+ij ,在模 m 意义下前三项被消去,由于 ij \equiv 1 \pmod m ,因此 (m-i)(m-j) \equiv 1 \pmod m

因此枚举小于 m 的正整数 i 只需枚举至 \frac 2 m 即可。

时间复杂度: O(\frac {n^2\log n} 4 +q)

期望得分: 31

算法四

定义 h(x) 表示在模 m 意义下满足 i^2 \equiv 1 \pmod m 1\leq i\leq m-1 的正整数 i 的个数。

引理四 g(m)=\varphi(m)-h(m) 显然成立,则答案可表示为 2^{\varphi(m)-h(m)\over 2}

结合引理三,枚举 m 以及小于 \frac 2 m 的正整数 i 并判断 i^2 \equiv 1 \pmod m 是否成立即可。

时间复杂度: O(\frac {n^2} 4 +q)

期望得分: 44

算法五

引理五 \omega(m) 表示 m 的不同质因子个数, [P] 表示命题 P 是否成立,若成立则 [P]=1 ,否则 [P]=0 。则有 h(m)=2^{\omega(m)-[2|n]+[4|n]+[8|n]} ,也即答案为:

\scriptsize{f[G(m)]=2^{\varphi(m)-2^{\omega(m)-[2|n]+[4|n]+[8|n]} \over 2}}

\small{f[G(m)]=2^{\varphi(m)-2^{\omega(m)-[2|n]+[4|n]+[8|n]} \over 2}}

\large{f[G(m)]=2^{\varphi(m)-2^{\omega(m)-[2|n]+[4|n]+[8|n]} \over 2}}

\Large{f[G(m)]=2^{\varphi(m)-2^{\omega(m)-[2|n]+[4|n]+[8|n]} \over 2}}

\LARGE{f[G(m)]=2^{\varphi(m)-2^{\omega(m)-[2|n]+[4|n]+[8|n]} \over 2}}

\huge{f[G(m)]=2^{\varphi(m)-2^{\omega(m)-[2|n]+[4|n]+[8|n]} \over 2}}

\Huge{f[G(m)]=2^{\varphi(m)-2^{\omega(m)-[2|n]+[4|n]+[8|n]} \over 2}}

证明 m 分解质因数后, m=\prod_{i=1}^k p_i^{\alpha_i} ,令 y=x^2 y_i=x_i^2 ,可将 x^2 \equiv 1 \pmod m 转化为如下形式的同余方程组:

y \equiv 1\quad (\text{mod} \;\; m) \Leftrightarrow \begin{cases} y \equiv 1\quad (\text{mod} \;\; {p_1^{\alpha_1}}) \\ y \equiv 1\quad (\text{mod} \;\; {p_2^{\alpha_2}}) \\ \quad\quad \vdots \\y \equiv 1\quad (\text{mod} \;\; {p_k^{\alpha_k}}) \end{cases}

右侧同余方程组中 p_i^{\alpha_i} 的最小公倍数为 m ,因此右侧同余方程组显然可以推得左侧同余式。考虑使用中国剩余定理,下式可转化至上式情况,且由于 y_i=x_i^2 ,我们可以通过对每条同余方程计算合法 x_i 的个数以计算 h(m)

\begin{cases} y_1 \equiv 1\quad (\text{mod} \;\; {p_1^{\alpha_1}}) \\ y_2 \equiv 1\quad (\text{mod} \;\; {p_2^{\alpha_2}}) \\ \quad\quad \vdots \\y_k \equiv 1\quad (\text{mod} \;\; {p_k^{\alpha_k}}) \end{cases}

由于 p_i^{\alpha_i} 两两互质,因此该同余方程组必定有解且在 [0,m-1] 范围内仅有一解。

显然地,我们有:

x_i^2 \equiv 1\pmod m \Rightarrow x_i^2-1 \equiv 1\pmod m \Rightarrow (x_i+1)(x_i-1) \equiv 0\pmod m

因此该同余方程组又可化为:

\begin{cases} y_1 \equiv 1\quad (\text{mod} \;\; {p_1^{\alpha_1}}) \\ y_2 \equiv 1\quad (\text{mod} \;\; {p_2^{\alpha_2}}) \\ \quad\quad \vdots \\y_k \equiv 1\quad (\text{mod} \;\; {p_k^{\alpha_k}}) \end{cases} \Leftrightarrow \begin{cases} (x_1+1)(x_1-1) \equiv 0\quad (\text{mod} \;\; {p_1^{\alpha_1}}) \\ (x_2+1)(x_2-1) \equiv 0\quad (\text{mod} \;\; {p_2^{\alpha_2}}) \\ \quad\quad \vdots \\(x_k+1)(x_k-1) \equiv 0\quad (\text{mod} \;\; {p_k^{\alpha_k}}) \end{cases}

我们只需计算每条同余方程合法解 x_i 的个数,并根据乘法原理将其相乘即为 h(m)

考虑 p_i\geq 3 的情况,由于此时 \gcd(x_i+1,x_i-1)=1 ,因此其在模 p_i^{\alpha_i} 的情况下当且仅当 x_i+1 \equiv 0\pmod {p_i^{\alpha_i}} x_i-1 \equiv 0\pmod {p_i^{\alpha_i}} 时满足 (x_i+1)(x_i-1) \equiv 0\pmod {p_i^{\alpha_i}} ,该情况下 x_i 合法解的个数为 2

对于 p_i=2 的情况,由于此时 \gcd(x_i+1,x_i-1) 可能为 2 ,因此需要谨慎地分类讨论:

  • \alpha_i=1 ,此时 p_i^{\alpha_i}=2 ,当且仅当 x_i=1 时满足 (x_i+1)(x_i-1) \equiv 0\pmod {p_i^{\alpha_i}}