LibreOJ Anniversary Cup 题解

liu_cheng_ao 2018-06-17 22:21:21 2018-09-26 11:46:41

Day 1

A. ZQC 的迷宫

By Snakes,题解 By Snakes

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

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

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

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

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

这都不会,退群吧。

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

while(!reach_dest())move_left();

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

B. Menci 的序列

By CommonAnts,题解 By CommonAnts

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

算法一

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

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

算法二

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

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

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

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

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

算法三

我们可以发现一个事实:

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

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

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

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

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

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

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

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

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

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

算法四

我们需要继续优化。

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

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

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

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

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

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

算法五

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

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

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

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

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

C. CommonAnts 的调和数

By CommonAnts,题解 By CommonAnts

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

算法一

直接模拟。

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

算法二

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

时间复杂度:O(nlog⁡n)O(n \log n)O(nlogn)
预计得分:303030

算法三

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

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

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

时间复杂度:O(nlog⁡log⁡n)O(n \log \log n)O(nloglogn)
预计得分:505050

算法四

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

时间复杂度:不超过 O(mqlog⁡n)O(mq\log n)O(mqlogn)
预计得分:303030,结合前述可得 656565

算法五

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

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

D. Tangjz 的背包

By Tangjz,题解 By Tangjz

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

101010:暴力
454545:FFT
656565:一段lucas定理
100100100:两段lucas定理

—— tangjz 于 LibreOJ 用户群

算法一

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

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

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

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

同理,如果定义 G(n,m)=∑vkp−vfn,m(v)G(n, m) = \sum_{v}{k^{p - v} f_{n, m}(v)}G(n,m)=vkpvfn,m(v),则有 G(n,0)=1G(n, 0) = 1G(n,0)=1, G(0,m)=[m=0]G(0, m) = [m = 0]G(0,m)=[m=0], G(n,m)=G(n−1,m−1)+kmG(n−1,m)G(n, m) = G(n - 1, m - 1) + k^m G(n - 1, m)G(n,m)=G(n1,m1)+kmG(n1,m)

算法二

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

定义关于 zzz 的多项式 Pn(z)=∑mF(n,m)zmP_n(z) = \sum_{m}{F(n, m) z^m}Pn(z)=mF(n,m)zm,于是有 P0(z)=1P_0(z) = 1P0(z)=1, Pn(z)=(1+qnz)Pn−1(z)P_n(z) = (1 + q^n z) P_{n - 1}(z)Pn(z)=(1+qnz)Pn1(z),整理得 Pn(z)=∏i=1n(1+qiz)P_n(z) = \prod_{i = 1}^{n}{(1 + q^i z)}Pn(z)=i=1n(1+qiz)

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

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

算法三

Pn(z)=(1+qz)(1+q2z)⋯(1+qnz)P_n(z) = (1 + q z) (1 + q^2 z) \cdots (1 + q^n z)Pn(z)=(1+qz)(1+q2z)(1+qnz) 可得 Pn−1(z)(1+qnz)=(1+qz)Pn−1(qz)P_{n - 1}(z) (1 + q^n z) = (1 + q z) P_{n - 1}(q z)Pn1(z)(1+qnz)=(1+qz)Pn1(qz)

Pn(z)=∑mF(n,m)zmP_n(z) = \sum_{m}{F(n, m) z^m}Pn(z)=mF(n,m)zm 带入等式,观察 zmz^mzm 的系数可得 F(n−1,m)+qnF(n−1,m−1)=qmF(n−1,m)+qmF(n−1,m−1)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(n1,m)+qnF(n1,m1)=qmF(n1,m)+qmF(n1,m1)

整理得

F(n−1,m)=qm1−qn−m1−qmF(n−1,m−1)F(n - 1, m) = q^m \frac{1 - q^{n - m}}{1 - q^m} F(n - 1, m - 1)F(n1,m)=qm1qm1qnmF(n1,m1)F(n,m)=qm(m+1)2(1−qn)(1−qn−1)⋯(1−qn−m+1)(1−q)(1−q2)⋯(1−qm)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)}F(n,m)=q2m(m+1)(1q)(1q2)(1qm)(1qn)(1qn1)(1qnm+1)

[n]q=∑i=0n−1qi=1−qn1−q,[n]q!=[1]q[2]q⋯[n]q[n]_q = \sum_{i = 0}^{n - 1}{q^i} = \frac{1 - q^n}{1 - q}, [n]_q! = [1]_q [2]_q \cdots [n]_q[n]q=i=0n1qi=1q1qn,[n]q!=[1]q[2]q[n]q,则 F(n,m)=qm(m+1)2[n]q![m]q![n−m]q!F(n, m) = q^{\frac{m (m + 1)}{2}} \frac{[n]_q!}{[m]_q! [n - m]_q!}F(n,m)=q2m(m+1)[m]q![nm]q![n]q!

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

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

算法四

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

不难发现,它们可以规约到相同的形式:[kα]q=1−qkα1−q=1−qkα1−qα1−qα1−q=k[α]q[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[kα]q=1q1qkα=1qα1qkα1q1qα=k[α]q

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

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

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

Day 2

A. Snakes 的 Naïve Graph

By Snakes,题解 By Snakes

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

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

算法一

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

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

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

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

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

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

期望得分:101010

算法二

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

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

期望得分:191919

算法三

引理三 若在 G(m)G(m)G(m) 中,对于 1≤i,j≤m−11\leq i,j\leq m-11i,jm1 的正整数 i,ji,ji,j,若 iXi_XiXjYj_YjY 有边,则 (m−i)X(m-i)_X(mi)X(m−j)Y(m-j)_Y(mj)Y 有边。

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

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

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

期望得分:313131

算法四

定义 h(x)h(x)h(x) 表示在模 mmm 意义下满足 i2≡1(modm)i^2 \equiv 1 \pmod mi21(modm)1≤i≤m−11\leq i\leq m-11im1 的正整数 iii 的个数。

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

结合引理三,枚举 mmm 以及小于 2m\frac 2 mm2 的正整数 iii 并判断 i2≡1(modm)i^2 \equiv 1 \pmod mi21(modm) 是否成立即可。

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

期望得分:444444

算法五

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

f[G(m)]=2φ(m)−2ω(m)−[2∣n]+[4∣n]+[8∣n]2\scriptsize{f[G(m)]=2^{\varphi(m)-2^{\omega(m)-[2|n]+[4|n]+[8|n]} \over 2}}f[G(m)]=22φ(m)2ω(m)[2n]+[4n]+[8n]f[G(m)]=2φ(m)−2ω(m)−[2∣n]+[4∣n]+[8∣n]2\small{f[G(m)]=2^{\varphi(m)-2^{\omega(m)-[2|n]+[4|n]+[8|n]} \over 2}}f[G(m)]=22φ(m)2ω(m)[2n]+[4n]+[8n]f[G(m)]=2φ(m)−2ω(m)−[2∣n]+[4∣n]+[8∣n]2\large{f[G(m)]=2^{\varphi(m)-2^{\omega(m)-[2|n]+[4|n]+[8|n]} \over 2}}f[G(m)]=22φ(m)2ω(m)[2n]+[4n]+[8n]f[G(m)]=2φ(m)−2ω(m)−[2∣n]+[4∣n]+[8∣n]2\Large{f[G(m)]=2^{\varphi(m)-2^{\omega(m)-[2|n]+[4|n]+[8|n]} \over 2}}f[G(m)]=22φ(m)2ω(m)[2n]+[4n]+[8n]f[G(m)]=2φ(m)−2ω(m)−[2∣n]+[4∣n]+[8∣n]2\LARGE{f[G(m)]=2^{\varphi(m)-2^{\omega(m)-[2|n]+[4|n]+[8|n]} \over 2}}f[G(m)]=22φ(m)2ω(m)[2n]+[4n]+[8n]f[G(m)]=2φ(m)−2ω(m)−[2∣n]+[4∣n]+[8∣n]2\huge{f[G(m)]=2^{\varphi(m)-2^{\omega(m)-[2|n]+[4|n]+[8|n]} \over 2}}f[G(m)]=22φ(m)2ω(m)[2n]+[4n]+[8n]f[G(m)]=2φ(m)−2ω(m)−[2∣n]+[4∣n]+[8∣n]2\Huge{f[G(m)]=2^{\varphi(m)-2^{\omega(m)-[2|n]+[4|n]+[8|n]} \over 2}}f[G(m)]=22φ(m)2ω(m)[2n]+[4n]+[8n]

证明mmm 分解质因数后,m=∏i=1kpiαim=\prod_{i=1}^k p_i^{\alpha_i}m=i=1kpiαi,令 y=x2y=x^2y=x2yi=xi2y_i=x_i^2yi=xi2,可将 x2≡1(modm)x^2 \equiv 1 \pmod mx21(modm) 转化为如下形式的同余方程组:

y≡1(mod    m)⇔{y≡1(mod    p1α1)y≡1(mod    p2α2)⋮y≡1(mod    pkαk)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}y1(modm)y1(modp1α1)y1(modp2α2)y1(modpkαk)

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

{y1≡1(mod    p1α1)y2≡1(mod    p2α2)⋮yk≡1(mod    pkαk)\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}y11(modp1α1)y21(modp2α2)yk1(modpkαk)

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

显然地,我们有:

xi2≡1(modm)⇒xi2−1≡1(modm)⇒(xi+1)(xi−1)≡0(modm)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 mxi21(modm)xi211(modm)(xi+1)(xi1)0(modm)

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

{y1≡1(mod    p1α1)y2≡1(mod    p2α2)⋮yk≡1(mod    pkαk)⇔{(x1+1)(x1−1)≡0(mod    p1α1)(x2+1)(x2−1)≡0(mod    p2α2)⋮(xk+1)(xk−1)≡0(mod    pkαk)\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}y11(modp1α1)y21(modp2α2)yk1(modpkαk)(x1+1)(x11)0(modp1α1)(x2+1)(x21)0(modp2α2)(xk+1)(xk1)0(modpkαk)

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

考虑 pi≥3p_i\geq 3pi3 的情况,由于此时 gcd⁡(xi+1,xi−1)=1\gcd(x_i+1,x_i-1)=1gcd(xi+1,xi1)=1,因此其在模 piαip_i^{\alpha_i}piαi 的情况下当且仅当 xi+1≡0(modpiαi)x_i+1 \equiv 0\pmod {p_i^{\alpha_i}}xi+10(modpiαi)xi−1≡0(modpiαi)x_i-1 \equiv 0\pmod {p_i^{\alpha_i}}xi10(modpiαi) 时满足 (xi+1)(xi−1)≡0(modpiαi)(x_i+1)(x_i-1) \equiv 0\pmod {p_i^{\alpha_i}}(xi+1)(xi1)0(modpiαi),该情况下 xix_ixi 合法解的个数为 222

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

  • αi=1\alpha_i=1αi=1,此时 piαi=2p_i^{\alpha_i}=2piαi=2,当且仅当 xi=1x_i=1xi=1 时满足 (xi+1)(xi−1)≡0(modpiαi)(x_i+1)(x_i-1) \equiv 0\pmod {p_i^{\alpha_i}}(xi+1)(xi1)0(modpiαi),该情况下 xix_ixi 合法解的个数为 111

  • αi=2\alpha_i=2αi=2,此时 piαi=4p_i^{\alpha_i}=4piαi=4,当且仅当 xi∈{1,3}x_i\in\{1,3\}xi{1,3} 时满足 (xi+1)(xi−1)≡0(modpiαi)(x_i+1)(x_i-1) \equiv 0\pmod {p_i^{\alpha_i}}(xi+1)(xi1)0(modpiαi),该情况下 xix_ixi 合法解的个数为 222

  • αi≤3\alpha_i\leq 3αi3,此时 piαi≤8p_i^{\alpha_i}\leq 8piαi8,当且仅当 xi∈{1,piαi−1,piαi−12,piαi+12}x_i\in\{1,p_i^{\alpha_i}-1,{p_i^{\alpha_i}-1\over 2},{p_i^{\alpha_i}+1\over 2}\}xi{1,piαi1,2piαi1,2piαi+1} 时满足 (xi+1)(xi−1)≡0(modpiαi)(x_i+1)(x_i-1) \equiv 0\pmod {p_i^{\alpha_i}}(xi+1)(xi1)0(modpiαi),该情况下 xix_ixi 合法解的个数为 444

我们不妨这样考虑,令 L(x)L(x)L(x) 表示 xxx 在分解质因数后 222 的个数,也即 log⁡2lowbit(x)\log_2{\text{lowbit}(x)}log2lowbit(x),则 L(x)L(x)L(x) 的前 151515 项为:

111 222 333 444 555 666 777 888 999 101010 111111 121212 131313 141414 151515
000 111 000 222 000 111 000 333 000 111 000 222 000 111 000

注意到在模 piαip_i^{\alpha_i}piαi 意义下除平凡解 1,piαi−11,p_i^{\alpha_i}-11,piαi1 外,非平凡解 xix_ixi 满足 L(xi−1)+L(xi+1)≤αiL(x_i-1)+L(x_i+1)\leq \alpha_iL(xi1)+L(xi+1)αiL(x)L(x)L(x) 有如下性质:

  • 在前 piαi−1p_i^{\alpha_i}-1piαi1 项中最大值为 αi−1\alpha_i-1αi1 且仅出现一次。

  • 对于正整数 xxx,必定有 L(x−1)L(x-1)L(x1)L(x+1)L(x+1)L(x+1) 中其一值为 111

上述性质读者可自行证明。由上述性质我们可推得非平凡解仅出现在 piαi2p_i^{\alpha_i}\over 22piαi 的两侧,在 2,42,42,4 的特殊情况下解的个数退化至 1,21,21,2

通过整理上述推导,我们即可推得 h(m)h(m)h(m) 表达式:

f[G(m)]=2φ(m)−2ω(m)−[2∣n]+[4∣n]+[8∣n]2f[G(m)]=2^{\varphi(m)-2^{\omega(m)-[2|n]+[4|n]+[8|n]} \over 2}f[G(m)]=22φ(m)2ω(m)[2n]+[4n]+[8n]

暴力计算 f[G(m)]f[G(m)]f[G(m)] 值并回答询问。

时间复杂度:O(nn+q)O(n\sqrt n+q)O(nn+q)

期望得分:595959

算法六

线性筛得到 φ(m)\varphi(m)φ(m)ω(m)\omega(m)ω(m),快速幂计算 f[G(m)]f[G(m)]f[G(m)] 值并回答询问。

时间复杂度:O(nlog⁡n+q)O(n\log n+q)O(nlogn+q)

期望得分:777777

算法七

注意到 311021311021311021 为质数,因此 2x≡2x mod 311020(mod311021)2^x \equiv 2^{x \bmod 311020} \pmod {311021}2x2xmod311020(mod311021),预处理 222 的次幂对 311021311021311021 取模结果即可。注意到 ω(m)\omega(m)ω(m)10710^7107 范围内小于 202020,因此可共用同一表。

一位优秀的 OIer 如何在 15 分钟内 AC 此题:

  • 1 min:发现求模某个数下 111 平方根个数
  • 4 min:手算前几个发现结论并证明完毕
  • 14 min:码完线性筛并样例测试完毕
  • 15 min:提交!AC!

时间复杂度:O(n+q)O(n+q)O(n+q)

期望得分:100100100

B. 613 的天网

By 613,题解 By 613

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

算法一

随便输出一个平面,也即选一个 xxx 输出所有第一维坐标为 xxx 的位置。

时间复杂度:O(n2)O(n^2)O(n2)
摄像头个数:n2n^2n2
预计得分:101010

算法二

考虑如何把这个长方体变小。

可以发现,如果染上一条直线 x=x0,y=y0x=x0,y=y0x=x0,y=y0,原来 x×y×zx\times y\times zx×y×z 的矩形就会恰好变成 (x−1)×(y−1)×z(x-1)\times (y-1)\times z(x1)×(y1)×z 的。

直接用动态规划构造解和方案即可。

时间复杂度:O(n3)O(n^3)O(n3)
摄像头个数:⌈0.75n2⌉\lceil 0.75n^2\rceil0.75n2
预计得分:202020

算法三

算法二的决策实际上不需要动态规划,直接贪心选最短的一边即可。

时间复杂度:O(n2)O(n^2)O(n2)
摄像头个数:⌈0.75n2⌉\lceil 0.75n^2\rceil0.75n2
预计得分:242424

算法四

考虑 n=2n=2n=2 的情况,如何把它推广到任意的 nnn

可以发现,用三个互相垂直的平面(无厚度)把 n×n×nn\times n\times nn×n×n 的矩形分成 888 份,如果选择处于对角的两份,且能构造方案使得这两个区域中每行、列、纵列都有摄像头,即可得一组合法方案。

构造 n×n×nn\times n\times nn×n×n 的矩形中 n×nn\times nn×n 个摄像头使得其每一行列纵都有摄像头做法很多,一种简单的方法为:对于 z=z0z=z0z=z0 的平面,在 y=x+z0y=x+z0y=x+z0 上的点放置摄像头。

至于用平面划分的方法,对于 nnn 为偶数的情况,均分即可;
对于 nnn 为奇数的情况,两对角分别为 ⌈n/2⌉×⌈n/2⌉×⌈n/2⌉\lceil n/2\rceil \times\lceil n/2\rceil \times\lceil n/2\rceiln/2×n/2×n/2⌊n/2⌋×⌊n/2⌋×⌊n/2⌋\lfloor n/2\rfloor \times\lfloor n/2\rfloor \times\lfloor n/2\rfloorn/2×n/2×n/2 的两个正方体。

时间复杂度:O(n2)O(n^2)O(n2)
摄像头个数:⌈0.5n2⌉\lceil 0.5n^2\rceil0.5n2
预计得分:100100100

C. mathematican 的二进制

By mathematican,题解 By mathematican & CommonAnts

  • 期望,NTT
  • 思维难度:NOI-
  • 实现难度:NOI

算法一

由于 n,mn, mn,m 都比较小,可以直接枚举每一个操作是否进行,然后计算代价和答案。

时间复杂度:O(m2m)O(m2^m)O(m2m)
预计得分:555

算法二

可以注意到,最终的答案与操作顺序无关,只与哪些操作被执行过有关,因为每次进位总会让 111 的总个数减少 111,总代价就是所有被执行的操作的总次数的两倍减去最终剩下的数中 111 的个数

对于 ai=0a_i=0ai=0 的情况,我们可以使用一个简单的递推计算出对于任意 iii,第 000 位被加了 iii 次的概率:设 f(j,i)f(j,i)f(j,i) 表示前 jjj 次操作进行完后总共加了 iii 次的概率,有 f(j,i)=f(j−1,i)(1−pj)+f(j−1,i−1)pjf(j,i)=f(j-1,i)(1-p_j)+f(j-1,i-1)p_jf(j,i)=f(j1,i)(1pj)+f(j1,i1)pj。最后对每种情况的代价乘概率求和,就可以算出期望答案。

时间复杂度:O(m2)O(m^2)O(m2)
预计得分:202020

算法三

000 位被加了 iii 次的概率生成函数是 f(x)=∏i=1mpix+1f(x)=\prod_{i=1}^m p_ix+1f(x)=i=1mpix+1。分治 NTT 计算即可。

时间复杂度:O(mlog⁡2m)O(m \log^2 m)O(mlog2m)
预计得分:404040

算法四

我们已经知道操作顺序是无关紧要的。那么根据期望的线性性我们可以逐位计算贡献。考虑另一个递推:f(i,j)f(i,j)f(i,j) 表示从后往前第 iii 位总共被改变 jjj 次的概率,那么我们有两种转移:

  • 进位:f(i−1,j)→f(i,⌊j2⌋)f(i-1,j)\rightarrow f(i,\lfloor \frac{j}{2}\rfloor)f(i1,j)f(i,2j)
  • 操作:对于第 iii 位每个概率为 ppp 的操作,f(i,j−1)p+f(i,j)(1−p)→f(i,j)f(i,j-1)p+f(i,j)(1-p)\rightarrow f(i,j)f(i,j1)p+f(i,j)(1p)f(i,j)

时间复杂度:O(m2)O(m^2)O(m2)
预计得分:404040,结合前述可得 606060

算法五

和算法三类似,这个递推式也可以用分治 NTT 优化。考虑分治 NTT 中每个位置的贡献不超过 O(log⁡2m)O(\log^2m)O(log2m),而每个操作对于分治NTT的长度的贡献可以放缩为一个等比级数:∑i=0∞2−i=2\sum_{i=0}^\infty 2^{-i}=2i=02i=2,故时间复杂度为 O(mlog⁡2m)O(m\log^2 m)O(mlog2m)

时间复杂度:O(mlog⁡2m)O(m\log^2 m)O(mlog2m)
预计得分:100100100

D. yanQval 的生成树

By CommonAnts,题解 By CommonAnts

  • 最大生成树、凸优化
  • 思维难度:NOI
  • 实现难度:NOI

算法一

枚举所有生成树计算答案。基环树需要稍加维护。

时间复杂度:O(nnn!)O(\frac{n^n}{n!})O(n!nn)O(n)O(n)O(n)
预计得分:252525

算法二

我们可以注意到,μ\muμ 的取值实际上是集合的中位数(及其一个邻域),可以等于某条边的值。那么我们可以枚举中位数 MMM。现在边被分成了两部分,需要各取一半。我们不妨设原边权不小于中位数的为黑边(权值为 w−Mw-MwM),其余为白边(权值为 M−wM-wMw),那么我们要求半黑半白(⌈n−12⌉\lceil \frac{n-1}{2} \rceil2n1⌊n−12⌋\lfloor \frac{n-1}{2} \rfloor2n1 条)的最大生成树 TTT

但是上面的做法是有漏洞的。问题来自 nnn 为偶数的情况,这时边数为奇数,那么中间一条边是没有权值的,非黑非白,我们不能给它确定颜色,否则会导致答案变大,且方案也有变化。不过我们可以发现,任意一棵 n−2n-2n2 条边的生成森林总有一棵权值不小于其的生成树,反之任意一棵生成树中也总存在一棵权值相同的生成森林,故我们只要求所有黑白边各含 ⌊n−12⌋\lfloor \frac{n-1}{2} \rfloor2n1 条的最大生成森林即可。

首先,所选的黑边和白边必然来自各自的最大生成森林。否则,不妨设最大生成树选了一条不在最大生成森林中的白边 (u,v)(u,v)(u,v),那么我们将其删去,得到两个联通块。考虑在最大白生成森林中 u,vu,vu,v 间的路径,这条路径上所有边权都大于 (u,v)(u,v)(u,v),且总有某条边跨越了两个联通块,那么我们选取这条边可得一棵更大的生成树,矛盾。

注意到,白联通块间的边必然都是黑边的最大生成树,黑联通块间也必然都是白边的最大生成树。我们只需考虑黑白都联通的联通块。对于这样的联通块,假设我们已经有了一棵 kkk 条白边的最大生成树 TkT_kTk,要求出 k+1k+1k+1 条白边的最大生成树。这必然是一条黑边代替了其两端在当前生成树路径上的一条白边,否则,令最大生成树为 T′T'T,类似于次小生成树,由于黑白生成树各自的拟阵性质总存在一个每次交换一对边的序列将 T′T'T 变为 TkT_kTk,且每次权值增加。总能找到一个位置使得仅替换一条边的生成树更大。这对不超过 n−2n-2n2 条(或者任意常数条)边的森林也适用,因为边数不会超过原来的数量。

那么我们只需要从 k=0k=0k=0 开始做,每次枚举替换的边检查即可。

时间复杂度:O(nm2)O(nm^2)O(nm2)
预计得分:303030

算法三

实际上 kkk 条白边最大生成树的解法可以继续优化:注意到,我们上一步的交换过程中,每条边交换的收益单调不增(kkk 较大时能替换的边是较小时的子集),且每次取的最优边,那么每次的收益也单调不增。答案是其的积分,那么答案必然是凸函数,我们可以通过二分增长率的方法求解:二分增长率 kkk,给所有白边附加 kkk 的权值再求最大生成树即可。

时间复杂度:O(nmlog⁡nα(n))O(nm\log n\alpha(n))O(nmlognα(n))
预计得分:505050

算法四

现在我们的算法是:先枚举中位数 MMM,然后二分增长率 kkk,令原来小于 MMM 的白边边权为 M+k−wM+k-wM+kw,其余黑边的边权为 w−Mw-MwM,注意到所有边同时加减同一个值不影响最大生成树的形态,可以同时减去 −M-MM 变为 2M+k−w2M+k-w2M+kwwww

这样我们有一种想法:令 C=2M+k−wC=2M+k-wC=2M+kw,则黑白边分别为 C−wC-wCwwww,能否放弃枚举中位数直接二分 CCC 求解呢?

那么我们需要建立所有黑边和白边,且需要最大生成树仅含有 w≥Mw\ge MwM 的黑边和 w<Mw<Mw<M 的白边,这是否正确呢?

答案是肯定的。首先对于 MMM 如果最大生成树 T(M)T(M)T(M) 含有黑边 w1−Mw_1-Mw1M 和白边 M−w2M-w_2Mw2w1<w2w_1<w_2w1<w2,显然交换两条边为 w2−M,M−w1w_2-M,M-w_1w2M,Mw1 更优(因为黑白边对应重合,交换总是可行的)。故所有黑边对应的 www 必然大于所有白边。那么如果最大生成树含有 w<Mw< Mw<M 的黑边或 w≥Mw\ge MwM 的白边,必然只含一种,不妨设为黑边。那么设最小黑边原本的权值为 w′w'w,取 M′=w′M'=w'M=w,可以发现其余边的权值之和不变,而这条黑边的权值从 w′−M<0w'-M<0wM<0 变成了 000,增加了,故得到了一棵更大的生成树,所以这一定不是全局最大生成树。又由于方案数有限全局最大生成树(或者 n−2n-2n2 条边生成森林)一定存在,其必然仅含有 w≥Mw\ge MwM 的黑边和 w<Mw<Mw<M 的白边。

那么我们直接二分 CCC 即可。注意 nnn 为偶数的情况。

时间复杂度:O(mlog⁡nα(n))O(m\log n\alpha(n))O(mlognα(n))
预计得分:100100100

算法五

我们对算法四稍加改进。例如,用 Link-Cut Tree 维护出每条边出现对应的 CCC 的范围 —— 一条边存在于最大生成树中当且仅当权值更大的边不能联通这条边的两端。这样可以得到一些更优的算法。

时间复杂度:O(mlog⁡n)O(m\log n)O(mlogn)
预计得分:100100100

Day 3

A. Misaka Network与测试

By cz_xuyixuan ,题解 By cz_xuyixuan

  • 二分图最大匹配
  • 思维难度:普及
  • 实现难度:提高

算法一

注意到子任务 111 中存在限制“队列中不存在 1 ”,也就是说任意一个不包含空的位置的矩形只要包含 3 ,其平均值必然超过 222 ,因此任意一个符合题目条件的矩形必然仅包含 2 ,答案即为队列中 2 的个数。

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

算法二

我们发现如果将矩阵中所有数减去 222 ,问题转化成了选出尽可能多的和为 000 的子矩形。

考虑如何解决 n=1n=1n=1 的情况,记 dpidp_idpi 表示矩阵的前 iii 列中共能选取的合法的子矩形数,sis_isi 表示矩阵第 111 行前 iii 个元素的和。

则有转移 dpi=maxsi=sj{dpi−1,dpj+1}dp_{i}=max_{s_i=s_j}\{dp_{i-1}, dp_j+1\}dpi=maxsi=sj{dpi1,dpj+1}

时间复杂度:O(m2)O(m^2)O(m2)
预计得分:151515,综合前述预计得分:202020

算法三

考虑如何解决 n=2n=2n=2 的情况,观察算法二中 n=1n=1n=1 时的 dpdpdp 我们发现 dpdpdp 数组是单调不降的,因此实际上我们只需要找到最大的使得 si=sjs_i=s_jsi=sjjjj 便可完成转移。换而言之,我们如果确定了一个需要选取的子矩形的上、下、右边界,它的左边界越靠右越好。

由于 n=2n=2n=2 时一个子矩形可能的上、下、右边界只有 O(m)O(m)O(m) 种,我们可以预处理出每一种可能的上、下、右边界对应的最靠右的左边界的位置,记 dpi,jdp_{i,j}dpi,j 表示矩阵第一行前 iii 列、第二行前 jjj 列组成的整体中共能选取的合法的子矩形数,不难得到 O(1)O(1)O(1) 的简单转移。

时间复杂度:O(m2)O(m^2)O(m2)
预计得分:151515,综合前述预计得分:353535

算法四

dpdpdp 的方法似乎已经不能再优化了,那么我们回头看一看算法一吧!

是不是所有的 2 都会被单独选取作为一个子矩形呢?

是的。因为如果在最优方案中存在一个子矩形中包含 2 ,我们可以不选取这个子矩形,而只选取 2 这个位置,这样得到的方案不会变劣。

进一步考虑,我们发现任意一个不包含 2 ,但平均数为 222 的子矩形一定存在一对相邻的 13 ,我们不选取这个子矩形,而只选取这一对相邻的 13 ,得到的方案不会变劣。

因此,我们将矩阵中的 13 看做二分图的两侧,相邻的 13 连边,求解这张图的最大匹配,加上 2 的个数,就是答案。

用一般的增广路算法实现二分图最大匹配,时间复杂度:O(n2m2)O(n^2m^2)O(n2m2)
预计得分:858585

DinicDinicDinic 算法实现二分图最大匹配,时间复杂度:O(nmnm)O(nm\sqrt{nm})O(nmnm)
预计得分:100100100

B. Misaka Network与任务

By cz_xuyixuan ,题解 By cz_xuyixuan

  • 容斥原理,组合计数,FWT∗FWT^{*}FWT
  • 思维难度:提高
  • 实现难度:普及

算法零

“卧槽这不就是一个 FWTFWTFWTkkk 次幂么?”

你一眼看出了本题的做法,并熟练地在 555 分钟内写完了 FWTFWTFWT

提交,ACACAC,大骂出题人又出了一道垃圾题。

时间复杂度:O(2n(n+log k)+m)O(2^n(n+log \ k)+m)O(2n(n+log k)+m)
预计得分:100100100

“我不会 FWTFWTFWT 啊。”

没有关系,本题放在 BBB 题的本意并不需要大家掌握 FWTFWTFWT

算法一

注意到问题本质上要求每次选取的集合在二进制下取 &\&& 运算后不为 000

枚举每一次选取的集合即可。

时间复杂度:O(mk)O(m^k)O(mk)
预计得分:555

算法二

上述过程显然可以用 dpdpdp 加速,令 dpi,jdp_{i,j}dpi,j 表示选取了 iii 次,当前选取的所有集合二进制下取 &\&& 运算的结果为 jjj ,不难得到 O(m)O(m)O(m) 的转移。

时间复杂度:O(2nmk)O(2^nmk)O(2nmk)
预计得分:151515

算法三

注意到算法二中 dpi,∗dp_{i,*}dpi,dpi+1,∗dp_{i+1,*}dpi+1, 的转移可以看做 dpi,∗dp_{i,*}dpi, 这个向量乘上一个转移矩阵后得到向量 dpi+1,∗dp_{i+1,*}dpi+1, 用矩阵快速幂来加速转移即可快速计算出 dpk,∗dp_{k,*}dpk,

时间复杂度:O(m+23nlog k)O(m+2^{3n}log\ k)O(m+23nlog k)
预计得分:303030

算法四

抛开 dpdpdp 的想法,我们换一种方式考虑这个问题。

x&y=xx\&y=xx&y=x ,我们称 xxxyyy 数位包含。我们发现直接计算答案不容易,但计算使得每次选取的集合在二进制下取 &\&& 运算后的结果数位包含 iii 的方案数 valival_ivali 是容易的,我们只需要保证每一次选取的集合都数位包含 iii 即可,记 cnticnt_icnti 表示输入中数位包含 iii 的集合的个数,则 vali=cntikval_i=cnt_i^kvali=cntik

fif_ifi 表示输入的集合中等于 iii 的个数。那么 cnti=∑i&j=ifjcnt_i=\sum_{i\&j=i}f_jcnti=i&j=ifj 。由二项式反演(或者说容斥原理),我们可以得到答案的表达式 Ans=∑i=12n(−1)bitsi+1∗cntikAns=\sum_{i=1}^{2^n}(-1)^{bits_i+1}*cnt_i^kAns=i=12n(1)bitsi+1cntik ,其中 bitsibits_ibitsi 表示 iii 在二进制表示下 111 的个数。

时间复杂度:O(m+22n+2nlog k)O(m+2^{2n}+2^nlog\ k)O(m+22n+2nlog k)
预计得分:454545

算法五

注意到算法四的复杂度瓶颈在于计算 cnticnt_icnti

观察表达式 cnti=∑i&j=ifjcnt_i=\sum_{i\&j=i}f_jcnti=i&j=ifj ,我们发现我们不需要枚举每一个 jjj ,而只需要枚举每一个数位包含 iiijjj ,这一点我们可以通过枚举子集做到。

时间复杂度:O(m+3n+2nlog k)O(m+3^n+2^nlog\ k)O(m+3n+2nlog k)
预计得分:606060

算法六

算法五的复杂度瓶颈依然在于计算 cnticnt_icnti

注意到当 n=20n=20n=202n=1048576≈1062^n=1048576≈10^62n=1048576106,而 m≤105m \le 10^5m105 ,因此 fif_ifi 中只有约 110\frac{1}{10}101 的位置是非 000 的。

观察表达式 cnti=∑i&j=ifjcnt_i=\sum_{i\&j=i}f_jcnti=i&j=ifj ,我们同样可以先枚举每一个 fjf_jfj ,通过枚举子集将其加到每一个满足 i&j=ii\&j=ii&j=icnticnt_icnti 上。若 fj=0f_j=0fj=0 ,我们就可以不必进行这一操作。

由于子任务 666 中保证了数据随机,其期望时间复杂度为:O(m+3n10+2nlog k)O(m+\frac{3^n}{10}+2^nlog\ k)O(m+103n+2nlog k)
预计得分:808080

算法七

如何更加高效地计算 cnticnt_icnti 呢?

考虑 n=1n=1n=1 的情况,显然 cnt0=f0+f1,cnt1=f1cnt_0=f_0+f_1,cnt_1=f_1cnt0=f0+f1,cnt1=f1

考虑 n=2n=2n=2 的情况,我们将所有数按照二进制前 n−1n-1n1 位分组,将同一组中二进制最后一位为 111 的位置上的 cntcntcnt 加到二进制最后一位为 000 的位置上。进行完这个操作后,我们发现所有数中二进制最后一位为 0/10/10/1 的数分别成为了一个 n=1n=1n=1 的子问题,我们可以分开处理。

考虑 n=i(i>1)n=i(i>1)n=i(i>1) 的情况,我们将所有数按照二进制前 n−1n-1n1 位分组,将同一组中二进制最后一位为 111 的位置上的 cntcntcnt 加到二进制最后一位为 000 的位置上。进行完这个操作后,我们发现所有数中二进制最后一位为 0/10/10/1 的数分别成为了一个 n=i−1n=i-1n=i1 的子问题,我们可以分开处理。

分治进行这个过程即可,这个过程实际上就是 FWTFWTFWT (的一半)。

时间复杂度:O(2n(n+log k)+m)O(2^n(n+log \ k)+m)O(2n(n+log k)+m)
预计得分:100100100

C. Misaka Network 与 Accelerator

By tqyaaaaang,题解 By tqyaaaaang

  • 2-SAT,长链剖分,点分治
  • 思维难度:NOI-
  • 实现难度:NOI

算法一

暴力枚举每个点选不选,判一下每个条件是否符合就行了。

复杂度:O(2nnm)O(2^n nm)O(2nnm)

期望得分:15分

算法二

可以发现这是个每个点就是选或者不选,可以考虑2-SAT。直接暴力2-SAT建图,每个点为 111 表示它被选,为 000 表示不被选。

暴力建图,对每个限制都把所有限制的点对连一组边。

复杂度:O(n2+nm)O(n^2+nm)O(n2+nm)

期望得分:30分

算法三

考虑一条链怎么做,可以直接用一个线段树来优化建图,或者按 R−L+1​R-L+1​RL+1 长度分块。

复杂度:O(mlog⁡n)O(m \log n)O(mlogn)O(m)O(m)O(m)

期望得分:10分

算法四

考虑如何优化这个2-SAT建图。按照剧本,可以考虑点分治。考虑只考虑那些经过当前分治中心的那些长度为 [L,R][L,R][L,R] 的路径,可以直接对每个限制,假设这个限制的 aaa 的深度是 ddd,那么你就要和所有不在这个子树内的深度为 [max(L−d,0),min(R−d,maxdist)][max(L-d,0),min(R-d,maxdist)][max(Ld,0),min(Rd,maxdist)] 的点对应的颜色连边。直接用线段树优化建图,就可以做到 O(mlog⁡2n)O(m \log^2 n)O(mlog2n) 了。至于取不在这个子树内的,你可以在加某个子树的时候把这些从主席树里去掉,或者用前缀+后缀都可以。

复杂度:O(mlog⁡2n)O(m \log^2 n)O(mlog2n)

期望得分:65分

结合算法三可以得到75分。

剧本上75分是这么给的,但是好像一个好一点的 O(n2)O(n^2)O(n2) 暴力加一点乱搞就可以搞过75分了……

算法五

我们发现其实不用点分。我们把这棵树长链剖分,每次先跑最长链,再跑短链。假设当前最长链和跑完了的短链的信息存在某些主席树里,那么我们暴力把当前访问的最短链里的每个深度 ddd,和之前那些主席树里的 [max(L−d,0),min(R−d,maxdist)][max(L-d,0),min(R-d,maxdist)][max(Ld,0),min(Rd,maxdist)] 深度对应的那些点连边,然后暴力把这个链里面每个深度的信息合并上去。这样做的话,每个点的信息只会在这个点所在的长链的顶端那里被合并一次,然后就不再产生贡献了,单次合并是 O(log⁡n)O(\log n)O(logn) 的,所以总复杂度就是 O(nlog⁡n)O(n \log n)O(nlogn)

复杂度:O(nlog⁡n)O(n \log n)O(nlogn)

期望得分:100分

算法六

做法 by fizzydavid

其实还是可以点分的……

考虑点分的时候对深度按 R−L+1R-L+1RL+1 分块,那么每次要取的要么是 [1,i][1,i][1,i],要么是 [i,maxdist][i,maxdist][i,maxdist],要么是跨越两块的一个长度为 R−L+1R-L+1RL+1 的区间。那么对每一块维护一个前缀一个后缀,对所有的维护一个前缀一个后缀,就行了。合并是两个子树深度的 maxmaxmax,所以按照子树深度从小到大合并就行了。

复杂度:O(nlog⁡n)O(n \log n)O(nlogn)

期望得分:100分

D. Misaka Network与求和

By cz_xuyixuan ,题解 By cz_xuyixuan

  • 莫比乌斯反演、杜教筛、洲阁筛/Min25Min25Min25
  • 思维难度:NOI
  • 实现难度:NOI

算法一

按照题目给出的式子计算答案。

时间复杂度:O(n2n)O(n^2\sqrt{n})O(n2n)
预计得分:555

算法二

枚举题目给出的式子中的 iii ,以及 iii 的一个因数 ggg 作为 gcdi,jgcd_{i,j}gcdi,j

那么,原式 ∑i=1N∑j=1Nf(gcd(i,j))k\sum_{i=1}^{N}\sum_{j=1}^{N}f(gcd(i,j))^ki=1Nj=1Nf(gcd(i,j))k

=∑i=1N∑g/if(g)k∗ϕ(⌊Ng⌋)=\sum_{i=1}^{N}\sum_{g/i}f(g)^k*\phi(\lfloor\frac{N}{g}\rfloor)=i=1Ng/if(g)kϕ(gN)

预处理欧拉函数,以及 f(i)kf(i)^kf(i)k

时间复杂度:O(nn)O(n\sqrt{n})O(nn)
预计得分:171717

算法三

将原题对 f(x)f(x)f(x) 的定义改为 xxx 次大的质因数的 kkk 次方。

那么原式即为 ∑i=1N∑j=1Nf(gcd(i,j))\sum_{i=1}^{N}\sum_{j=1}^{N}f(gcd(i,j))i=1Nj=1Nf(gcd(i,j))

考虑枚举gcd(i,j)gcd(i,j)gcd(i,j),那么原式

=∑g=1Nf(g)∑i=1⌊Ng⌋∑j=1⌊Ng⌋ϵ(gcd(i,j))=\sum_{g=1}^{N}f(g)\sum_{i=1}^{\lfloor\frac{N}{g}\rfloor}\sum_{j=1}^{\lfloor\frac{N}{g}\rfloor}\epsilon(gcd(i,j))=g=1Nf(g)i=1gNj=1gNϵ(gcd(i,j))

=∑g=1Nf(g)∑i=1⌊Ng⌋∑j=1⌊Ng⌋∑d/i,d/jμ(d)=\sum_{g=1}^{N}f(g)\sum_{i=1}^{\lfloor\frac{N}{g}\rfloor}\sum_{j=1}^{\lfloor\frac{N}{g}\rfloor}\sum_{d/i,d/j}\mu(d)=g=1Nf(g)i=1gNj=1gNd/i,d/jμ(d)

=∑g=1Nf(g)∑d=1⌊Ng⌋μ(d)⌊Ngd⌋2=\sum_{g=1}^{N}f(g)\sum_{d=1}^{\lfloor\frac{N}{g}\rfloor}\mu(d)\lfloor\frac{N}{gd}\rfloor^2=g=1Nf(g)d=1gNμ(d)gdN2

=∑gd=1N(f∗μ)(gd)⌊Ngd⌋2=\sum_{gd=1}^{N}(f*\mu)(gd)\lfloor\frac{N}{gd}\rfloor^2=gd=1N(fμ)(gd)gdN2

预处理莫比乌斯函数,以及 f(i)f(i)f(i) ,暴力计算它们的狄利克雷卷积。

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

算法四

继续考虑算法三中得到的式子 ∑gd=1N(f∗μ)(gd)⌊Ngd⌋2\sum_{gd=1}^{N}(f*\mu)(gd)\lfloor\frac{N}{gd}\rfloor^2gd=1N(fμ)(gd)gdN2

⌊Ngd⌋\lfloor\frac{N}{gd}\rfloorgdN整数分块,我们剩余的工作是计算函数(f∗μ)(f*\mu)(fμ)在每一个⌊Ngd⌋\lfloor\frac{N}{gd}\rfloorgdN处的前缀和。

g(N)=∑i=1N(f∗μ)(i)g(N)=\sum_{i=1}^{N}(f*\mu)(i)g(N)=i=1N(fμ)(i),注意到(f∗μ)∗1=f∗(μ∗1)=f(f*\mu)*1=f*(\mu*1)=f(fμ)1=f(μ1)=f,因此

∑i=1Nf(i)=∑i=1N(f∗μ∗1)(i)=∑i=1Ng(⌊Ni⌋)\sum_{i=1}^{N}f(i)=\sum_{i=1}^{N}(f*\mu*1)(i)=\sum_{i=1}^{N}g(\lfloor\frac{N}{i}\rfloor)i=1Nf(i)=i=1N(fμ1)(i)=i=1Ng(iN)

g(N)=∑i=1Nf(i)−∑i=2Ng(⌊Ni⌋)g(N)=\sum_{i=1}^{N}f(i)-\sum_{i=2}^{N}g(\lfloor\frac{N}{i}\rfloor)g(N)=i=1Nf(i)i=2Ng(iN)

上面的式子可以杜教筛,剩余的唯一问题在于计算函数 fff 在每一个⌊Ni⌋\lfloor\frac{N}{i}\rflooriN处的前缀和。

注意到子任务 444k=1k=1k=1 ,因此函数 fff 的前缀和可以通过分块打表得到。

时间复杂度:O(n34+αβ(n)n)O(n^{\frac{3}{4}}+\alpha\beta(n)\sqrt{n})O(n43+αβ(n)n) 其中 α\alphaα 为块长,β(n)\beta(n)β(n) 表示求解 f(x)f(x)f(x) 的复杂度,程序内需要存入一个 O(nα)O(\frac{n}{\alpha})O(αn) 的常量数组。
预计得分:505050

算法五

考虑如何快速计算函数 fff 在每一个⌊Ni⌋\lfloor\frac{N}{i}\rflooriN处的前缀和。

我们从小到大枚举一个数的每一个质因子,最后第二个被枚举到的质因子的 kkk 次方即为 f(x)f(x)f(x)

类似Min25Min25Min25筛的过程,我们令s(N,i)s(N,i)s(N,i)表示上次选择的质因子为primei−1prime_{i-1}primei1,剩余部分的乘积不超过NNN的数的 f(x)f(x)f(x) 之和。

s(N,i)={0primei>Nprimei−1k∗(∑j=1N[j is a prime]−(i−1))+∑j=iprimej2≤N∑e=1primeje+1≤N(s(⌊Nprimeje⌋,j+1)+primejk)primei≤Ns(N,i)=\left\{\begin{array}{rcl}0 & & {prime_i>N}\\prime_{i-1}^k*(\sum_{j=1}^{N}[j\ is\ a\ prime]-(i-1))\\+\sum_{j=i}^{prime_j^2≤N}\sum_{e=1}^{prime_j^{e+1}≤N}(s(\lfloor\frac{N}{prime_j^e}\rfloor,j+1)+prime_j^k) & & {prime_i≤N}\end{array} \right. s(N,i)=0primei1k(j=1N[j is a prime](i1))+j=iprimej2Ne=1primeje+1N(s(primejeN,j+1)+primejk)primei>NprimeiN

那么 ∑i=1Nf(i)=s(N,1)\sum_{i=1}^{N}f(i)=s(N,1)i=1Nf(i)=s(N,1)

在上述过程中,我们唯一需要使用的量就是 NNN 以内质数的个数,可以用洲阁筛/Min25Min25Min25筛简单计算。

并且,由于我们需要计算 fff 在每一个⌊Ni⌋\lfloor\frac{N}{i}\rflooriN处的前缀和,我们需要对 s(N,i)s(N,i)s(N,i) 进行记忆化。由于题目时间限制较为宽松,使用 std::unordered_mapstd::unordered\_mapstd::unordered_map 实现记忆化即可。

时间复杂度:O(n1−ϵ)O(n^{1-\epsilon})O(n1ϵ)
预计得分:100100100

共 19 条回复

hiuseues2

上述性质读者可自行证明。

咕咕咕

kczno1

题解补完了,day3咕了

kczno1

day3要来了,day2题解还咕着

P1atform

跪求Day2题解

zjp_shadow
跪求 day2 题解啊
Planet6174

催更题解

zjq

求Day2题解

kczno1

day2参赛人数好少啊..

kczno1

貌似有更简单的做法..
https://loj.ac/submission/123172

liu_cheng_ao

@kczno1 求贪心证明 ……