"Hello 2018" 题解

liu_cheng_ao 于 2018-01-03 16:55:31 发表,2018-01-10 13:47:03 最后更新

A. 奴隶主的游戏

By liu125008 & CommonAnts & qmqmqm & fengchanghn,题解 By fengchanghn

  • 考察选手的基础博弈知识及构造和分类讨论以及猜结论的能力(雾
  • 思维难度:提高
  • 实现难度:普及-

其实你会发现前面两个(所有)的数据范围都是假的,朴素搜索是无法通过 n≥4n\ge 4n4 的 ……

所以下面都以特殊情况来考虑。

情况一

k=0k=0k=0

注意到数独游戏对称性很强,考虑填对称的方法:

  • 如果 nnn 为偶数,直接在中心对称位置填相同元素。由于两个中心对称的位置必定不在同行同列或同区域,故二者填入时所在行、列及区域的元素必定相同,从而先手可填时后手必定可填,由于格子大小有限,游戏必定在有限步内结束,从而后手必胜。
  • 如果 nnn 为奇数,那么与之类似地,先手先在中间填上 n2n^2n2,然后每次在后手所填位置的对称位置填上与其所填数相对的数(iiin2−in^2-in2i 相对,n2n^2n2n2n^2n2 相对)即可。故先手必胜。

情况二

nnn 为偶数,k≤1k\leq 1k1

k=0k=0k=0 的情况相同,只不过交换了先后手,故先手必胜。

然而没有这一点的分

情况三

nnn 为奇数,k≤1k\leq 1k1

延续情况二的思路,但此时不能直接填中心对称了,因为一开始的数不一定在中间。

但可以发现如果两行或两列均在同一区域那么他们是可以互换位置的,且两个由区域组成的行或列也是可以互换位置的,故可以构造一个置换把初始填的格子换到中间。至于数值,由于我们只关注是否像等,故可以随意置换。

也可以理解为每个点重新找到了一个对称(匹配)点,每个数也如此。

情况三

k≤2k\leq 2k2

如果 nnn 为奇数,和情况三同样讨论将任意一个填过的格子换到中间即可。

如果 nnn 为偶数,情况要复杂一些:我们仍然考虑为每个点重新找一个对称(匹配)点,为每个数重新找一个相对的数字。

可以分类构造:

  • 当两格所属区域不在同行或同列时,可以中心对称。

  • 当两格所属区域在同一行(列)但两格不在同一区域且两格属于同行或同列时,可以轴对称。

  • 当两格所属区域在同一行(列)但两格不在同一区域且两格不属于同行或同列时,可以在区域组成的列内中心对称。

  • 当两格在同一区域且两格不属于同行或同列时,可以在区域内中心对称。

  • 当两格在同一区域且两格属于同行或同列时,可以在区域内轴对称。

这样,不管怎么填答案只与 nnnkkk 的奇偶性有关。

扩展?

这个结论在 kkk 更大时成立吗?遗憾的是它在 kkk 很大时是错误的。但 kkk 似乎可以比 222 大一些,比如 n=2n=2n=2 时最小的反例出现在 k=6k=6k=6。有想法的同学欢迎交流。

B. Array Poisonous Suffix Problem

By qmqmqm,题解 By CommonAnts & fengchanghn

  • 考察选手对后缀数组性质的了解和构造。
  • 思维难度:提高+
  • 实现难度:普及/提高-

算法一

枚举长度再枚举所有合法字符串验证。

此处长度只用枚举到 k+1k+1k+1,后文证明。

时间复杂度:O((k+1)k+1)O((k+1)^{k+1})O((k+1)k+1)
期望得分:777

算法二

我们枚举后缀排名数组(以下也称名次数组,记作 rank\mathrm{rank}rank,后缀数组记作 sa\mathrm{sa}sa)。

注意到,对于 1≤i<n1\le i<n1i<n ,位置 sa[i]\mathrm{sa}[i]sa[i] 可以等于 sa[i+1]\mathrm{sa}[i+1]sa[i+1] 的充要条件是 rank[sa[i]+1]<rank[sa[i+1]+1]\mathrm{rank}[\mathrm{sa}[i]+1]< \mathrm{rank}[\mathrm{sa}[i+1]+1]rank[sa[i]+1]<rank[sa[i+1]+1](设 rank[n+1]=0rank[n+1]=0rank[n+1]=0)。故我们贪心地填即可取得最小的字符集。

时间复杂度:O((k+1)!)O((k+1)!)O((k+1)!)
期望得分:777

算法三

其实答案不仅一定是 k+1k+1k+1,方案也是唯一的。

显然,任意一个长为 nnnrank[]\mathrm{rank}[]rank[] 最多需要的字符集大小为 nnn(只需要对应 rank[]\mathrm{rank}[]rank[] 位置填对应字符)。我们尝试构造一个字符集恰好为 nnn 的串。

考虑 rank[]\mathrm{rank}[]rank[] 未填的最后一个位置,它必定是尚未用过的 rank\mathrm{rank}rank 值中最大的(nnn),因为若该位置不是最大的,设为 vvv,由于 rank[]\mathrm{rank}[]rank[] 未填的最后一个位置的后一个位置比剩余的任何值都小,rank[sa[v+1]+1]\mathrm{rank}[\mathrm{sa}[v+1]+1]rank[sa[v+1]+1] 必定比该位置大,那么 sa[v]\mathrm{sa}[v]sa[v]sa[v+1]\mathrm{sa}[v+1]sa[v+1] 可以填相等字符,字符集大小小于 nnn

接下来,所填的必定是最小的。因为此时它的后一个位置是最大的,故可以用类似的证明方法证得。

归纳即得唯一可能的最小字符集为 nnn 的串如下:从最后一个位置向前,倒数奇数位置填当前最大值,偶数位置填当前最小值。

验证可知其字符集恰为 nnn。故我们解决了该问题。

时间复杂度:O(k)O(k)O(k)
期望得分:100100100

只推出部分性质而使用复杂度较高的方法可以得到部分分。

C. 小埋与游乐场

By Snakes,题解 By Snakes

  • 贪心或网络流
  • 思维难度 NOI-
  • 代码难度 NOI-

算法一

枚举每个在集合 AAA 中的数与 BBB 中的哪个数配对或不配对,计算并更新答案。

可通过子任务 111

时间复杂度:O(nm+1)O(n^{m+1})O(nm+1)
预计得分:666

算法二

对于子任务 222BBB 中元素均不在 AAA 中且 k=1k=1k=1,那挑一对异或之后 lowbit\mathrm{lowbit}lowbit 减少值最大的异或就可以啦!

但是时间复杂度O(nm)O(nm)O(nm),超时。

性质一a≠ba\neq baba,b≠0a,b\neq 0a,b0,考虑 lowbit(a⊕b)\mathrm{lowbit}(a\oplus b)lowbit(ab),当 lowbit(b)<lowbit(a)\mathrm{lowbit}(b)<\mathrm{lowbit}(a)lowbit(b)<lowbit(a)lowbit(a⊕b)=lowbit(b)\mathrm{lowbit}(a\oplus b)=\mathrm{lowbit}(b)lowbit(ab)=lowbit(b),否则 lowbit(a⊕b)≥lowbit(a)\mathrm{lowbit}(a\oplus b)\geq\mathrm{lowbit}(a)lowbit(ab)lowbit(a)

lowbit\mathrm{lowbit}lowbit 的定义可知,当 lowbit(a)≠lowbit(b)\mathrm{lowbit}(a)\neq\mathrm{lowbit}(b)lowbit(a)lowbit(b) 时,lowbit(a⊕b)=min(lowbit(a),lowbit(b))\mathrm{lowbit}(a\oplus b)=\min(\mathrm{lowbit}(a),\mathrm{lowbit}(b))lowbit(ab)=min(lowbit(a),lowbit(b))。当 lowbit(a)=lowbit(b)\mathrm{lowbit}(a)=\mathrm{lowbit}(b)lowbit(a)=lowbit(b)a≠ba\neq bab 时,则 aaa 的最低位在异或 bbb 之后变为 000,所以lowbit(a⊕b)>lowbit(a)\mathrm{lowbit}(a\oplus b)>\mathrm{lowbit}(a)lowbit(ab)>lowbit(a)。对于 lowbit(a)<lowbit(b)\mathrm{lowbit}(a)<\mathrm{lowbit}(b)lowbit(a)<lowbit(b) 的情况同理。

所以我们只需要分别对集合 AAA 与集合 BBB 中的元素分别计算其 lowbit\mathrm{lowbit}lowbit,当取集合 AAAlowbit\mathrm{lowbit}lowbit 最大的元素与集合 BBBlowbit\mathrm{lowbit}lowbit 最小的元素异或后,能使解更优时,对其进行操作并更新答案即可。

可通过子任务 222

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

算法三

对于子任务 333,在算法二的基础上考虑 a=ba=ba=b 的情况。显然当 a=ba=ba=b 时,lowbit(a⊕b)\mathrm{lowbit}(a\oplus b)lowbit(ab) 的值为 000。所以只需要判断集合 AAA 与集合 BBBlowbit\mathrm{lowbit}lowbit 最大的相等元素对答案的贡献,并将其与算法二的答案取最优解即可。

可通过子任务 2,32,32,3

时间复杂度:O(nlogn+n+m)O(n \log n+n+m)O(nlogn+n+m)
预计得分:181818

结合算法一可得 242424 分。

算法四

对于子任务 444,集合 AAA 与集合 BBB 无相等元素,考虑贪心。

性质二 答案中不存在 a≠ba\neq bablowbit(b)≥lowbit(a)\mathrm{lowbit}(b)\geq\mathrm{lowbit}(a)lowbit(b)lowbit(a) 的操作。
否则直接去掉该操作答案不会变劣。

性质三 在最优解中不存在两对 aaacccbbbddd 的操作,使得 a≠b,c≠d,lowbit(b)≥lowbit(c)a\neq b,c\neq d,\mathrm{lowbit}(b)\geq\mathrm{lowbit}(c)ab,cd,lowbit(b)lowbit(c)

否则将 aaaddd 操作会更优。二者答案相差 lowbit(b)−lowbit(c)\mathrm{lowbit}(b)-\mathrm{lowbit}(c)lowbit(b)lowbit(c),即使其为 000,在操作次数上也会更优。

lowbit(a)lowbit(d)=lowbit(a)lowbit(b)+lowbit(b)lowbit(c)+lowbit(c)lowbit(d)

性质四 在最优解中满足 a≠ba\neq bab 的操作,在 aaa 中每个元素只与 bbblowbit\mathrm{lowbit}lowbit 比它小的元素操作的前提下,与配对方法无关。

证明 不论操作顺序如何,答案均比无操作时答案减少 ∑a∈A′a−∑b∈B′b\sum_{a\in A'}a-\sum_{b\in B'}baAabBb,其中 A′,B′A',B'A,BA,BA,BA,B 中被操作的子集。

根据性质二至四,我们可以得出以下算法。

每次在 nmnmnm 对数中找到一组没有被操作过的 (a,b)(a,b)(a,b),使得 lowbit(a)−lowbit(a⊕b)\mathrm{lowbit}(a)-\mathrm{lowbit}(a\oplus b)lowbit(a)lowbit(ab) 最大,对其进行操作。重复此过程至无剩余操作次数或该操作对答案无贡献。

一个小技巧:找一个 2 的指数(即模意义下满足 2i=12^i=12i=1 的最小正整数 iii)不小于 32 的模数即可直接利用对 2x2^x2x 取模算出 xxx。最小的合法模数是 373737

可通过子任务 444

时间复杂度:O(nmk)O(nmk)O(nmk)
预计得分:999

结合上述算法可得 333333 分。

算法五

对于子任务 555,在算法四的基础上考虑出现集合 AAABBB 存在相等元素的情况。

假定存在元素 a∈Aa\in AaA,元素 b∈Bb\in BbB,且满足 a=ba=ba=b。若 aaabbb 操作为当前对答案贡献最大的一组操作,则不会存在问题。若 aaa 已被操作,且 BBB 中有剩余 lowbit\mathrm{lowbit}lowbitbbb 相等的元素未被操作,则可继续操作,否则不可操作,跳过该组操作。

在算法四的实现基础上,新增对 BBB 集合 lowbit\mathrm{lowbit}lowbit 分类的元素个数即可。

可通过子任务 4,54,54,5

时间复杂度:O(nmk)O(nmk)O(nmk)
预计得分:111111

结合上述算法可得 444444 分。

算法六

对于子任务 666,集合 BBB 中元素相等,直接计算集合 AAA 中的每个数对 BBB 中的数操作对答案的贡献,从大到小排序后取前 kkk 个贡献为正的操作即可。

可通过子任务 666

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

结合上述算法可得 535353 分。

也即,一个四合一的程序可以拿到本题一半的分数。

子任务 2,3,4,52,3,4,52,3,4,5 一直在提示正解,但是似乎的确有选手没发现。(其实能过子任务 555 的选手已经可以AC了)

算法七

对于子任务 777,考虑暴力最大权匹配。有 kkk 次操作的限制,不考虑 KM 算法,考虑用费用流实现。将集合 AAA 中元素视为二分图的一边,BBB 中元素视为另一边,两两之间连一条从 AAABBB 的边,费用为其操作对答案的贡献,流量为 111AAA 侧与 BBB 侧均向对应的源点与超级汇点连一条费用为 000,容量为 111 的边。超级源点与源点连一条费用为 000,流量为 kkk 的边。在构成的二分图上跑最大费用最大流即可。

优化连边,除去贡献为 000 或负数的边,可降低常数。

可通过子任务 1,4,5,71,4,5,71,4,5,7

最坏时间复杂度:O(kn3)O(kn^3)O(kn3)
预计得分:393939

结合上述算法可得 666666 分。

算法八

对于子任务 888,考虑使用数据结构维护集合并且贪心。

性质五 在集合 A,BA,BA,B 存在相等元素的情况下,若存在 a∈A,b∈Ba\in A,b\in BaA,bBa=ba=ba=b,存在 c∈Ac\in AcAlowbit(c)>lowbit(a)\mathrm{lowbit}(c)>\mathrm{lowbit}(a)lowbit(c)>lowbit(a),则 cccbbb 操作比 aaabbb 操作更优。
lowbit(c)−lowbit(b)≤lowbit(b)=lowbit(a)−lowbit(a⊕b)\mathrm{lowbit}(c)-\mathrm{lowbit}(b)\leq\mathrm{lowbit}(b)=\mathrm{lowbit}(a)-\mathrm{lowbit}(a\oplus b)lowbit(c)lowbit(b)lowbit(b)=lowbit(a)lowbit(ab)

性质六 在集合 A,BA,BA,B 存在相等元素的情况下,若存在 a∈A,b,c∈Ba\in A,b,c\in BaA,b,cB 满足 a=ba=ba=blowbit(c)<lowbit(a)\mathrm{lowbit}(c)<\mathrm{lowbit}(a)lowbit(c)<lowbit(a),则 aaabbb 操作比 aaaccc 操作更优。

性质七 在集合 A,BA,BA,B 存在相等元素的情况下,根据性质四可得若存在 a,c∈A,b,d∈Ba,c\in A,b,d\in Ba,cA,b,dB 满足 a=b,b≠d,lowbit(b)=lowbit(d),lowbit(a)<lowbit(c)a=b,b\neq d,\mathrm{lowbit}(b)=\mathrm{lowbit}(d),\mathrm{lowbit}(a)<\mathrm{lowbit}(c)a=b,bd,lowbit(b)=lowbit(d),lowbit(a)<lowbit(c),且 cccbbb 匹配,则可修改操作方案使 aaabbb 操作,cccddd 操作,答案更优。

证明 根据性质四,可得若与 ccc 匹配的 BBB 中元素交换的元素 lowbit\mathrm{lowbit}lowbit 不变,对当前答案不造成影响,交换后新增一组可操作元素对,答案更优。

性质八 集合 A,BA,BA,B 中的 000 不对答案造成任何影响。

证明 对于集合 AAA000lowbit\mathrm{lowbit}lowbit000;对于集合 BBB000 与任何数操作得到的数依旧为原数,贡献 000

由性质一至八可得以下贪心方案:

删除集合 A,BA,BA,B 中所有 000 后,每次在集合 AAA 中选择一个 lowbit\mathrm{lowbit}lowbit 最大的元素,与集合 BBBlowbit\mathrm{lowbit}lowbit 最小的元素操作,若在 AAAlowbit\mathrm{lowbit}lowbit 最大的元素有多个,则优先考虑在 BBB 中有相等元素的操作方案。若相等元素已被操作,但还有未操作的与其 lowbit\mathrm{lowbit}lowbit 相等的元素,则按照性质六交换操作方案。直到 kkk 次操作机会用完或最大贡献为负。正确性显然。

对于相等元素的查询有多种方法,可使用数据结构维护集合 A,BA,BA,B。可使用 std::setstd::map 或手写平衡树等数据结构维护,但常数过大。

可通过子任务 1,2,3,4,5,7,81,2,3,4,5,7,81,2,3,4,5,7,8

时间复杂度:O(n+klogn)O(n+k\log n)O(n+klogn),常数大
预计得分:727272

算法九

对于子任务 999,将算法八中的数据结构更换为哈希表、其它数据结构或排序即可。

可通过所有子任务。

时间复杂度:O(n+k)O(n+k)O(n+k)(期望)到 O(n+klogn)O(n+k\log n)O(n+klogn)
预计得分:100100100

算法十

优化匹配做法。在算法七基础上,考虑优化连边。根据性质四,我们关注的重点在于其 lowbit\mathrm{lowbit}lowbit,而非其值本身。考虑对 lowbit\mathrm{lowbit}lowbit 相同的点分类并记录个数,对集合 A,BA,BA,B 均建立 logai\log a_ilogailogbi\log b_ilogbi 个点并连边,对于相等的情况排序后统计连边或数据结构维护即可。logai\log a_ilogailogbi\log b_ilogbi 的最大值为 313131

可通过所有子任务。

时间复杂度:O(MaxcostMaxflow+nlogn)O(\mathrm{MaxcostMaxflow}+n\log n)O(MaxcostMaxflow+nlogn)
预计得分:100100100

D. 网格图

By spj,题解 By spj

  • 考察选手的图论建图能力以及优化建图的知识点。
  • 思维难度 NOI
  • 实现难度 NOI

算法一

对于第 1 个子任务,n,m≤5n,m\le 5n,m5,数据范围极小,暴力 DFS 以及一些随机/贪心或者写错的高分算法可能均可通过。

期望得分:000666

算法二(一)

对于前 4 个子任务,n,m≤2000n,m\le 2000n,m2000,意味着网格图不会很大,可以建出整个网格图。记 (x,y)(x,y)(x,y) 为第 xxx 行第 yyy 列的格子。

对每个非障碍格子 (x,y)(x,y)(x,y) 建立 444 个结点 (x,y,d)(x,y,d)(x,y,d),其中 ddd 为上、下、左、右之一,表示当前机器人位于格子 (x,y)(x,y)(x,y) 且方向为 ddd 的状态。

对每个结点 (x,y,d)(x,y,d)(x,y,d),如果 (x,y)(x,y)(x,y) 沿 ddd 方向的下一格 (x′,y′)(x',y')(x,y) 在网格图内且不是障碍,则 (x,y,d)→(x′,y′,d)(x,y,d)\rightarrow(x',y',d)(x,y,d)(x,y,d) 连一条长度为 000 的边;设 ddd 方向往左、右转 90° 得到的方向分别为 d1,d2d_1,d_2d1,d2,则 (x,y,d)→(x,y,d1)(x,y,d)\rightarrow(x,y,d_1)(x,y,d)(x,y,d1)(x,y,d)→(x,y,d2)(x,y,d)\rightarrow(x,y,d_2)(x,y,d)(x,y,d2) 各连一条长度为 111 的边。

以所有方向 ddd(xs,ys,d)(x_s,y_s,d)(xs,ys,d) 结点为源点集,求一遍单源最短路,那么结点 (x,y,d)(x,y,d)(x,y,d) 的最短路值 D(x,y,d)D(x,y,d)D(x,y,d) 就是到达状态 D(x,y,d)D(x,y,d)D(x,y,d) 的最小转向次数,于是每个询问 (xt,yt)(x_t,y_t)(xt,yt) 的答案就是 mind{D(xt,yt,d)}\min_d\{D(x_t,y_t,d)\}mind{D(xt,yt,d)}

时间复杂度:O(nmlognm)O(nm\log nm)O(nmlognm)

期望得分:242424

算法二(二)

不难发现 ddd 这一维只要记两种:水平和竖直。可以减少一半结点数。

注意到边长只有 000111,因此可以用 BFS 求最短路,实现时每层先扩展 000 边,再扩展 111 边。

实现时,并不需要把边显式地建出来。

时间复杂度:O(nm)O(nm)O(nm)

期望得分:292929

算法三

对于第 5 个子任务,k≤1k\le 1k1,可以通过分类讨论得到答案。

如果起点 (xs,ys)(x_s,y_s)(xs,ys) 和终点 (xt,yt)(x_t,y_t)(xt,yt) 在同一水平线或竖直线上:

  1. 若两者之间无障碍,答案为 000
  2. 否则,若 n=1n=1n=1m=1m=1m=1,则起点和终点不连通,答案为 −1-11
  3. 否则,必可以从起点绕到另一行/列再绕到终点,答案为 222

否则 (xs,ys)−(xs,yt)−(xt,yt)(x_s,y_s)-(x_s,y_t)-(x_t,y_t)(xs,ys)(xs,yt)(xt,yt)(xs,ys)−(xt,ys)−(xt,yt)(x_s,y_s)-(x_t,y_s)-(x_t,y_t)(xs,ys)(xt,ys)(xt,yt) 两条路径至少有一条无障碍,答案为 111

时间复杂度 O(q)O(q)O(q)

期望得分:777,结合算法二期望得分 363636

算法四

对于第 5-8 个子任务,k≤1000k\le 1000k1000,即网格图较大而障碍点较少。

不难发现一个性质:

性质 如果有若干连续的行(列)上均没有障碍及起点,则这一段连续的行(列)可以被换成一行(列)。

证明 不妨设第 lll 列至第 rrr 列均没有障碍和起点,设将当前图 GGG 的第 lll 列至第 rrr 列缩成一列(记为 lll)后的图为 G′G'G,注意终点可能被缩到第 lll 列。

以下证明对于任意起点和终点 s,ts,ts,t,在 GGGG′G'G 中的最小转弯次数相等,即 DG(s,t)=DG′(s,t)D_G(s,t)=D_{G'}(s,t)DG(s,t)=DG(s,t)

1、对于 GGGs→ts\rightarrow tst 最小转弯次数路径 PPP,当 PPP 每次进入列区间 [l,r][l,r][l,r] 时,设进入 [l,r][l,r][l,r] 的格子为 (x1,l)(x_1,l)(x1,l),离开 [l,r][l,r][l,r] 前或结束的格子为 (x2,y2)(x_2,y_2)(x2,y2)(可能是终点),则 (x1,l)→(x1,y2)→(x2,y2)(x_1,l)\rightarrow(x_1,y_2)\rightarrow(x_2,y_2)(x1,l)(x1,y2)(x2,y2) 为最小转弯次数走法。

将该路径段改成 G′G'G 中的 (x1,l)→(x2,l)(x_1,l)\rightarrow(x_2,l)(x1,l)(x2,l) 转弯次数相同。于是 DG′(s,t)≤DG(s,t)D_{G'}(s,t)\le D_G(s,t)DG(s,t)DG(s,t)

2、对于 G′G'G 中的 s→ts\rightarrow tst 最小转弯次数路径 PPP,当 PPP 每次进入列 lll 时,设进入 lll 的格子为 (x1,l)(x_1,l)(x1,l),离开 lll 或结束的格子为 (x2,l)(x_2,l)(x2,l),则 (x1,l)→(x2,l)(x_1,l)\rightarrow(x_2,l)(x1,l)(x2,l) 为最小转弯次数走法。

  • PPP(x2,l)(x_2,l)(x2,l) 为终点,令 $y_2=y_t;
  • 否则,若 PPP(x2,l)(x_2,l)(x2,l) 的下一格为 (x2,l−1)(x_2,l-1)(x2,l1),令 y2=ly_2=ly2=l
  • 否则,令 y2=ry_2=ry2=r

将路径段改成 GGG 中的 (x1,l)→(x1,y2)→(x2,y2)(x_1,l)\rightarrow(x_1,y_2)\rightarrow(x_2,y_2)(x1,l)(x1,y2)(x2,y2) 转弯次数相同。于是 DG(s,t)≤DG′(s,t)D_G(s,t)\le D_{G'}(s,t)DG(s,t)DG(s,t)

以上 a→ba\rightarrow bab 表示走 aaabbb 的最小转弯次数路径。

因此 DG(s,t)=DG′(s,t)D_G(s,t)=D_{G'}(s,t)DG(s,t)=DG(s,t),对于另一方向同理。证完。

这样我们可以用障碍将网格进行离散化,即将起点障碍一起按 xxx 排序,将连续的空行缩成一行,再按 yyy 排序,将连续的空列缩成一列。这样,新的网格图行数和列数均不超过 2k+12k+12k+1

可以套用算法二计算 sss 出发的最短路,对于每个询问通过二分查找可以得到终点所在的行列,从而完成询问。

和之前一样,实现时,并不需要把边显式地建出来。

如果使用 Dijkstra 求最短路:

时间复杂度 O(k2logk)O(k^2\log k)O(k2logk)

期望得分:484848

如果使用 BFS 求最短路:

时间复杂度为 O(k2)O(k^2)O(k2)

期望得分:595959

算法五

首先按算法四的方法离散化,在此基础上进一步优化。

H\mathrm{H}HV\mathrm{V}V 表示水平和竖直方向,则当格子 (x,y1)(x,y_1)(x,y1)(x,y2)(x,y_2)(x,y2)y1≤y2y_1\le y_2y1y2)之间不存在障碍 (x,y)(x,y)(x,y)y1<y<y2y_1 < y < y_2y1<y<y2)时,结点 (x,y1,H)(x,y_1,\mathrm{H})(x,y1,H)(x,y2,H)(x,y_2,\mathrm{H})(x,y2,H) 不需要代价。竖直方向类似。

也就是说,可以把每行每列的极长连续段提取出来建点,也就是说,把每行的障碍按 yyy 排序,将连续的空格段缩成一个新点,再将每列的障碍按 xxx 排序,将连续的空格缩成一个新点。

这样就缩掉了大量的点——每个连续段或者是一个空行或空列,或者与至少一个障碍点相邻,而在算法四的离散化之后最多只有 k+1k+1k+1 个空行和 k+1k+1k+1 个空列,且每个障碍点最多与 444 个极长连续段相邻,因此新点最多 6k+26k+26k+2 个。

同时也缩掉了所有长度为 000 的边。也就是说,新点构成的图只有一种边:如果水平连续段 vHv_HvH 和竖直连续段 vVv_VvV 在网格图中交于一点,则 vHv_HvHvVv_VvV 之间连一条长度为 111 的边。

现在边数仍然是 O(k2)O(k^2)O(k2) 的,考虑优化连边。

定义序列 SxS_xSx,其中 Sx[y]S_x[y]Sx[y] 为过 (x,y)(x,y)(x,y) 格的竖直连续段(若不存在,则 Sx[y]S_x[y]Sx[y] 的值可以任意),则对于水平连续段 (x1,y1)−(x1,y2)(x_1,y_1)-(x_1,y_2)(x1,y1)(x1,y2)y1≤y2y_1\le y_2y1y2),需要从该段往所有 y∈[y1,y2]y\in[y_1,y_2]y[y1,y2]Sx[y]S_x[y]Sx[y] 连一条长度为 111 的边。

注意到 SxS_xSx 是由 Sx−1S_{x-1}Sx1 修改了位于第 xxx 行的障碍 (x,y)(x,y)(x,y) 对应的 Sx−1[y]S_{x-1}[y]Sx1[y] 位置的值得到的序列(为了方便可以直接改成 (x,y)(x,y)(x,y) 下方的连续段),这样从 S1S_1S1SnS_nSn 最多修改了 kkk 次。

故可以用可持久化线段树处理出序列 S1,S2,⋯,SnS_1,S_2,\cdots,S_nS1,S2,,Sn。对于线段树上每个非叶结点,向其两个子结点连长度为 000 的有向边。之后对于每个水平连续段 (x1,y1)−(x1,y2)(x_1,y_1)-(x_1,y_2)(x1,y1)(x1,y2)y1≤y2y_1\le y_2y1y2),向 Sx[y1,y2]S_x[y_1,y_2]Sx[y1,y2] 在线段树上定位到的每个结点连一条长度为 111 的有向边。

这样就完成了水平连续段向竖直连续段的连边,竖直连续段向水平连续段的连边同理。

现在的结点数和边数都优化到了 O(klogk)O(k\log k)O(klogk) 级别,再用 BFS 求一遍最短路即可。时间复杂度和空间复杂度均为 O(klogk)O(k\log k)O(klogk)

和之前一样,实现时,并不需要把边显式地建出来。

时间复杂度:O(klogk)O(k\log k)O(klogk)
期望得分:100100100

另一种实现是不使用可持久化而直接在线段树每个节点上存插入到这个节点的所有段的集合,最短路时直接在节点上二分。

时间复杂度:O(klog2k)O(k\log^2 k)O(klog2k)
期望得分:858585

这个做法可以优化:使用链表来维护这个集合,并利用可持久化来维护每个位置起始的位置,然后访问时对链表使用路径压缩优化(这个复杂度是线性的)即可。

时间复杂度:O(klogk)O(k\log k)O(klogk)
期望得分:100100100

E. 匹配字符串

By spj,题解 By yanQval

  • 考察选手的暴力水平及常数优化能力组合计数知识和按数据规模分类讨论的方法。
  • 按数据规模分类,lucas 定理,线性递推
  • 思维难度 NOI+
  • 实现难度 NOI

算法一

n≤18n\le 18n18

直接暴力搜出所有合法的串。

时间复杂度:O(2n)O(2^n)O(2n)
预计得分:666

算法二

m≤2m\le 2m2

对于 m=1m=1m=1 的部分,显然不能出现字符 1,所以答案为 111

对于 m=2m=2m=2 的部分,不能有连续的字符 1 出现,令 fijf_{ij}fij 表示长度为 iii 的序列,结尾为 jjj 的方案数,使用矩阵快速幂优化。

时间复杂度:O(logn)O(\log n)O(logn)
结合算法一,预计得分:131313

算法三

n≤106n \le 10^6n106

fif_ifi 表示长度为 iii 的序列,以 000 结尾的方案数。通过枚举上一个 000 出现的位置进行转移,可以得到,fi=∑j=i−mi−1fjf_i=\sum_{j=i-m}^{i-1}f_jfi=j=imi1fj

可以通过前缀和等优化。

时间复杂度:O(n)O(n)O(n)
结合算法二,预计得分:282828

算法四

显然这个是一个常系数齐次线性递推,可以使用矩阵优化,或特征多项式优化。

时间复杂度:O(m3logn)O(m^3\log n)O(m3logn)O(m2logn)O(m^2\log n)O(m2logn)O(mlogmlogn)O(m\log m\log n)O(mlogmlogn)
结合算法二,预计得分:525252

算法五

si=∑j=1ifjs_i=\sum_{j=1}^{i}f_jsi=j=1ifj。通过差分可得 si−si−1=si−1−si−1−ms_i-s_{i-1}=s_{i-1}-s_{i-1-m}sisi1=si1si1m,即 si=2si−1−si−1−ms_{i}=2s_{i-1}-s_{i-1-m}si=2si1si1m

可以看成点 iiii+1i+1i+1 连一条权值为 222 的边,向 i+m+1i+m+1i+m+1 连一条权值为 −1-11 的边,答案即为从 000nnn 的路径权值和。

通过枚举走权值 −1-11 的次数可以得到答案为:∑i=0nm+1−1i2n−(m+1)×i(n−i×mi)\sum_{i=0}^{\frac{n}{m+1}}-1^i2^{n-(m+1)\times i}\binom{n-i\times m}{i}i=0m+1n1i2n(m+1)×i(ini×m)

时间复杂度:O(p+n/m)O(p+n/m)O(p+n/m)ppp 表示模数)
结合算法四,预计得分:100100100

矩阵乘法在常数非常优秀时也可以通过,参考zhouyuyang 的程序标准程序在使用同样的常数优化后可以在 78 毫秒内通过此题。

F. 某少女附中的体育课

By CommonAnts,题解 By CommonAnts

  • 考察选手对卷积定理及 DFT 的理解及应用,涉及基础抽象代数知识。
  • 线性变换与反演
  • 思维难度:WC+/CTSC+
  • 实现难度:NOI

考虑到题目定位以及部分分档数过多带来的问题,本题简单暴力得分较少,请见谅 qwq

为了描述方便,以下设 N=mn,G=(S,∘)N=m^n,G=(S,\circ)N=mn,G=(S,)

以下除非特殊说明,空间复杂度全部为输入规模 O(m2+N)O(m^2+N)O(m2+N)

算法一

首先可以设计一个显然的递推:fi(j)f_i(j)fi(j) 表示传球 iii 轮后持球状态为 jjj 的概率乘以 Xi+1X^{i+1}Xi+1 的值,从 fif_ifi 转移到 fi+1f_{i+1}fi+1 时暴力枚举生成的转移数列即可。

时间复杂度:O(m2+kN2)O(m^2+kN^2)O(m2+kN2)
预计得分:777

算法二

我们定义运算 ⋄\diamond 表示两个数在 mmm 进制下每一位分别做 ∘\circ 运算得到的结果,那么我们可以写出 fff 的转移方程:

fi+1(j)=∑k,l[k⋄l=j]fi(k)Pl f_{i+1}(j)=\sum _{k,l}[k\diamond l=j]f_i(k)P_l fi+1(j)=k,l[kl=j]fi(k)Pl

也即,每一层的 fff 是上一层与数列 PPP 关于 ⋄\diamond 运算的卷积

那么,我们用 ∗* 号表示两个序列关于 ⋄\diamond 运算的卷积。由乘法和 ∘\circ 的性质显然可以得到 ⋄\diamond∗* 均满足交换律与结合律。

对于数列 aaa 和正整数 bbb,我们规定 aaabbb 次方即 ab=aaab times

那么答案就是 Pk+1P^{k+1}Pk+1。由结合律,使用快速幂即可将计算卷积的次数降至 O(logk)O(\log k)O(logk)

时间复杂度:O(m2+N2logk)O(m^2+N^2\log k)O(m2+N2logk)
预计得分:777

算法三(一)

可以发现 m=2m=2m=2 时的运算是二进制位运算。子任务 2 中运算为同或,可以使用 FWT 加速计算。

如果你不会同或 FWT,你可以使用异或,运算后将序列翻转即可。另外如果使用的是同或 FWT,可以直接计算点值的 kkk 次方后再求逆变换。

时间复杂度:O(m2+Nnmk)O(m^2+Nnmk)O(m2+Nnmk)O(m2+Nnmlogk)O(m^2+Nnm\log k)O(m2+Nnmlogk)O(m2+Nnm+Nlogk)O(m^2+Nnm+N\log k)O(m2+Nnm+Nlogk)
预计得分:888,结合前述可得 151515

算法三(二)

讨论所有合法的二进制位运算并全部使用 FWT 加速即可解决 m=2m=2m=2 的情况。这时满足条件的 AAA 共有与、或、同或、异或四种。

时间复杂度:O(m2+Nnmlogk)O(m^2+Nnm\log k)O(m2+Nnmlogk)O(m2+Nnm+Nlogk)O(m^2+Nnm+N\log k)O(m2+Nnm+Nlogk)
预计得分:181818,结合前述可得 252525

算法四(一)

子任务 4 中 m=3m=3m=3∘\circ 表示取最大值,故我们可以使用 nnn 维前缀和计算卷积:考虑 a∗ba*bab 中满足每维都不大于 iii 的对应维的所有位置的和,它们恰好是 aaa 中和 bbb 中这些位置的和之积。因此做完高维前缀和后,点值乘法与原序列的卷积等价,于是快速幂后再差分回去即可。

时间复杂度:O(m2+Nnm+Nlogk)O(m^2+Nnm+N\log k)O(m2+Nnm+Nlogk)
预计得分:999,结合前述可得 343434

算法四(二)

子任务 5 中给出了一个奇怪的 AAA,通过人类智慧构造等方法可以发现将 (x,y,z)(x,y,z)(x,y,z) 变换为 (z,x+y+z,x−y+z)(z,x+y+z,x-y+z)(z,x+y+z,xy+z) 即可将卷积变成点值乘法,于是快速幂后再逆变换回去即可。

时间复杂度:O(m2+Nnm+Nlogk)O(m^2+Nnm+N\log k)O(m2+Nnm+Nlogk)
预计得分:999,结合前述可得 434343

算法五

GGG 是循环群时,我们知道有限循环群与整数模意义下的加法群同构,于是可以通过求出每个元素的阶来找出一个生成元。之后我们可以将 GGG 同构映射到模 mmm 加法群,于是原问题变成了高维循环卷积,使用高维 DFT 即可。由于 mmm 很小只要暴力计算 DFT 即可。

时间复杂度:O(m2+Nnm+Nlogk)O(m^2+Nnm+N\log k)O(m2+Nnm+Nlogk)
预计得分:101010,结合前述可得 535353

算法六(一)

注意到,变换(参见算法九)的每个系数要么全部非 0,要么全部为 0(因为它们的 m!m!m! 次幂都相等),显然全部为 0 没有逆,故只能全部非 0。

那么我们对它们取离散对数,就变成了线性方程组,高斯消元求解即可。

时间复杂度:O(m3+Nnm+Nlogk)O(m^3+Nnm+N\log k)O(m3+Nnm+Nlogk)
预计得分:111111,结合前述可得 646464

算法六(二)

GGG 是群时我们也可以利用如下定理:

引理 0(有限交换群基本定理) 有限交换群一定可分解为若干阶为素数幂的循环群的直积(直和),且在同构意义下该分解是唯一的。
证:略。请自行查阅资料。

于是我们考虑分解 GGG 后使用 DFT 计算。我们可以使用如下朴素分解算法:

  1. 首先求出所有元素的阶。
  2. 此时,考虑所有生成的循环子群中元素两两不属于同一等价类的元素。可知最大的因子循环群的阶数就是其中最大的阶为质数幂的元素的阶数,该循环群的生成元必定是某个阶满足条件的元素;反之,凡阶满足条件的元素均可以作为某个分解方案的生成元。故任选一个生成元 ggg
  3. 求出分离 ggg 生成的子群后的等价类及商群。不断迭代直到分解完成(只剩一个等价类)。

分解的时间复杂度为 T(m),T(x)=O(mx)+T(x/ord(g))T(m),T(x)=O(mx)+T(x/\mathrm{ord}(g))T(m),T(x)=O(mx)+T(x/ord(g)),由于 ord(g)≥2\mathrm{ord}(g)\ge 2ord(g)2,可得复杂度为 O(m2)O(m^2)O(m2)。分解完成后使用 DFT 即可。

时间复杂度:O(m2+Nnm+Nlogk)O(m^2+Nnm+N\log k)O(m2+Nnm+Nlogk)
预计得分:111111,结合前述可得 646464

算法七

∀i∈S,i∘i=i\forall i\in S,i\circ i=iiS,ii=iGGG 中元素全部都是幂等元时,我们可以构造如下变换:F(f)i=∑[j∘i=i]fjF(f)_i=\sum [j\circ i=i]f_jF(f)i=[ji=i]fj,那么 FFF 上的对应位置乘积就等价于 fff 上的卷积。类似于高维前缀和的做法。

正确性证明见后文。

时间复杂度:O(m3+Nnm+Nlogk)O(m^3+Nnm+N\log k)O(m3+Nnm+Nlogk)
预计得分:111111,结合前述可得 757575

算法八

一位熟练的 OI 选手如何在 60 分钟内 AC 此题:

  • 5 分钟,看完了题意,写出了递推式。
  • 6 分钟,发现是裸的卷积。
  • 10 分钟,发现模数有 222222 次以内的单位根,且是个质数。
  • 12 分钟,通过类比 DFT 和 FWT,大胆猜想可以通过某种关于单位根的线性变换把卷积变成乘积。
  • 20 分钟,列出了变换矩阵并化简出了系数满足的方程。
  • 25 分钟,观察发现只需要变换矩阵每列是方程组 ∀i,j,xixj=xi∘j\forall i,j,x_ix_j=x_{i\circ j}i,j,xixj=xij 的解且线性无关(有逆)。
  • 30 分钟,由循环律发现每个 xix_ixi 必定是某个 iii 的最小周期次单位根。
  • 40 分钟,写了个 O(mm)O(m^m)O(mm) 的暴搜单位根搜出变换矩阵,发现猜想是对的。
  • 45 分钟,加了点剪枝搜过了 m=22m=22m=22
  • 60 分钟,写了个 O(Nnm+Nlogk)O(Nnm+N\log k)O(Nnm+Nlogk) 的变换 1A。

如果搜的比较差可能就只有 808080878787 分了。

时间复杂度:O(mm+Nnm+Nlogk)O(m^m+Nnm+N\log k)O(mm+Nnm+Nlogk)
预计得分:808080100100100

算法九

受 DFT 和 WT 等的启发,我们尝试构造一个可逆变换来把卷积变成乘积。

首先注意到每一维是独立的,那么我们可以递归进行:先按当前维的值分成 mmm 个部分,每个部分变成乘积,然后每个部分当成一个数运算(运算方式为对应位置运算)。于是只要找到一维的变换即可。

由于要操作的是一个向量,为了保持线性性,我们尝试令这个变换是线性变换。那么设变换矩阵为 T,f(a)=aTT,f(a)=aTT,f(a)=aT。用 ⋅\cdot 表示对应位置相乘,列出方程:

f(a)⋅f(b)=f(a∗b) f(a)\cdot f(b)=f(a*b) f(a)f(b)=f(ab)

化简得,TTT 的每一列 {xi}\{x_i\}{xi} 满足方程组:

∀i,j,xi⋅xj=xi∘j \forall i,j,x_i\cdot x_j=x_{i\circ j} i,j,xixj=xij

那么可逆的 TTT 存在,当且仅当该方程组有 mmm 组线性无关(显然,不能有全 000)的解。

我们考虑循环律。设 iii 的最小周期为 c(i)c(i)c(i),我们可以发现 xix_ixi 要么是 000,要么是 c(i)c(i)c(i) 次单位根。注意到题目给出的标量域 Z/232792561\mathbb{Z}/232792561Z/232792561222222 次以下每种次数的单位根,这也是一个明显的性质。

接下来我们需要研究 GGG 的结构。定义 i0=ic(i)i^0=i^{c(i)}i0=ic(i),我们考虑 GGG 中每个元素 iii 生成的循环子群 Gi={ij:j∈Z/c(i)}G_i=\{i^j:j\in \mathbb{Z}/c(i)\}Gi={ij:jZ/c(i)},可以发现一些性质:

引理 1 ∀i,i0\forall i,i^0i,i0GiG_iGi 中唯一的幂等元。
证:设 iji^jij 是幂等元,则有 kN,jkj(modc(i)),解得 j0(modc(i))

引理 2 ∀i,j\forall i,ji,j 有:(∃x,y s.t. ix=jy)⇒(i0=j0)(\exists x,y \text{ s.t. } i^x=j^y) \Rightarrow (i^0=j^0)(x,y s.t. ix=jy)(i0=j0)
证:两边同时求 c(i)c(j)c(i)c(j)c(i)c(j) 次幂即可。

由这两个引理,我们可以按照 i0i^0i0GGG 进行划分。我们定义等价关系 ∼:i∼i0\sim:i\sim i^0:ii0

引理 3 ∼\sim 的等价类关于 ∘\circ 构成一个交换半群,即 (∀a,b,c,d,a∼b,c∼d)⇒((a∘c)∼(b∘d))(\forall a,b,c,d,a\sim b,c\sim d) \Rightarrow ((a\circ c)\sim (b\circ d))(a,b,c,d,ab,cd)((ac)(bd))
证:由交换律及结合律即得。
由引理 3 我们可以定义等价类间的 ∘\circ 运算。

引理 4 ∼\sim 的等价类都是幂等元,即 (∀a,b,c,a,b∼c)⇒((a∘b)∼c)(\forall a,b,c,a,b\sim c)\Rightarrow ((a\circ b)\sim c)(a,b,c,a,bc)((ab)c)
证:求 c(a)c(b)c(a)c(b)c(a)c(b) 次幂得 (a∘b)c(a)c(b)=a0∘b0∈Ga∘b(a\circ b)^{c(a)c(b)}=a^0\circ b^0\in G_{a\circ b}(ab)c(a)c(b)=a0b0Gab,又因为其为幂等元,再由引理 1 即可得证。

由引理 3 和 4我们发现这个同余类有一些很好的性质(实际上我们已经证明了它是一个半格),我们推导其对 xxx 的影响:

引理 5 ∼\sim 的同一个等价类中,对应的 xxx 要么全部为 000,要么全部非 000
证:由方程组可得,∀i,xi0=(xi)c(i)\forall i,x_{i^0}=(x_i)^{c(i)}i,xi0=(xi)c(i),那么 (xi0=0)⇔(xic(i)=0)(x_{i^0}=0)\Leftrightarrow (x_i^{c(i)}=0)(xi0=0)(xic(i)=0)

我们设 S∼,≥,i={j:j∘i=i}S_{\sim,\ge,i}=\{j:j\circ i=i\}S,,i={j:ji=i}

引理 6 若仅考虑 xix_ixi 是否为 000,一组非平凡(即至少有一个非 000)合法解 {x}\{x\}{x} 中所有非 000 等价类组成的集合一定是某个 S∼,≥,iS_{\sim,\ge,i}S,,i
证:我们考虑合法解中非 000 等价类的集合 SSS,设 iSi=a,根据方程组 aaa 必然非 000
由等价类幂等律,iS,ai=(iSi)i=iSi=a
此外,若 ∃i∘a=a\exists i\circ a=aia=aiii000,由方程组 aaa 必为 000,不可能。那么这组合法解中非 000 元素恰为 S∼,≥,aS_{\sim,\ge,a}S,,a,证毕。

引理 7 S∼,≥,iS_{\sim,\ge,i}S,,i 两两不同。
证:由于 i∈S∼,≥,ii\in S_{\sim,\ge,i}iS,,i,那么若有 i,ji,ji,j 满足 S∼,≥,i=S∼,≥,jS_{\sim,\ge,i}=S_{\sim,\ge,j}S,,i=S,,j,则 i∘j=i,i∘j=j,i=ji\circ j=i,i\circ j=j,i=jij=i,ij=j,i=j

现在我们解决了哪些 xxx000 的问题,需要确定 xxx 的值了。我们发现等价类的性质:

引理 8 ∼\sim 的每个等价类是关于 ∘\circ 的交换群。
证:令幺元为等价类中的幂等元,逆元 i−1=ic(i)−1i^{-1}=i^{c(i)-1}i1=ic(i)1 即可得到。

又由引理 0,我们考虑一个等价类 RRR 的分解:R=iZ/pcii。这时的变换即为一个每维长度分别为 picip_i^{c_i}pici 的高维离散傅里叶变换。这个高维离散傅里叶变换共有 ∣R∣|R|Rxxx 的解。

我们得到一个等价类 RRR 的一组解后,考虑构造出完整的一组解 xxx。设 RRR 的单位元(幂等元)为 eee,有 xe=1x_e=1xe=1∀j s.t. j0∈S∼,≥,R\forall j\text{ s.t. }j^0\in S_{\sim,\ge,R}j s.t. j0S,,R,由 xj⋅xe=xj∘ex_j \cdot x_e=x_{j\circ e}xjxe=xje 可得 xj=xj∘ex_j=x_{j\circ e}xj=xje。故其它等价类中元素对应的 xxx 取值唯一确定。

现在我们证明 {xj=xj∘e}\{x_j=x_{j\circ e}\}{xj=xje} 是合法解。∀i,j\forall i,ji,j 我们分类讨论:

  1. iS,,R,此时 ijS,,R(否则若 i∘j∈S∼,≥,Ri\circ j\in S_{\sim,\ge,R}ijS,,R,有 i∘j∘R=R,i∘R=i∘(i∘j∘R)=i∘j∘R=Ri\circ j\circ R=R,i\circ R=i\circ(i\circ j\circ R)=i\circ j\circ R=RijR=R,iR=i(ijR)=ijR=R,矛盾),对应的方程 0⋅xj=00\cdot x_j=00xj=0 成立。
  2. i,j∈Ri,j\in Ri,jR,由高维离散傅里叶变换一定成立。
  3. 否则,xi∘j=xi∘j∘e=x(i∘e)∘(j∘e)x_{i\circ j}=x_{i\circ j\circ e}=x_{(i\circ e)\circ (j\circ e)}xij=xije=x(ie)(je),由 (i∘e)∈R,(j∘e)∈R(i\circ e)\in R,(j\circ e)\in R(ie)R,(je)R 可得 x(i∘e)∘(j∘e)=xi∘exj∘e=xixjx_{(i\circ e)\circ (j\circ e)}=x_{i\circ e}x_{j\circ e}=x_ix_jx(ie)(je)=xiexje=xixj,证毕。

那么,我们得到了 ∣R∣|R|R 个解。对于每个等价类都求一次即得恰好 ∑∣R∣=m\sum |R|=mR=m 个解。现在我们需要证明它们是线性无关的。

我们将元素重新标号。标号方法如下:每次取出一个满足 S∼,≥,i={i}S_{\sim,\ge,i}=\{i\}S,,i={i} 的等价类 iii,将其中元素以任意顺序标上最小的 ∣i∣|i|i 个编号。然后删去 iii 并重复直到标号完成。
这样标号一定是正确的。一方面,由上述分类讨论的 1 可知删去 iii 后的运算仍封闭,故删去这样的 iii 后得到的是一个子问题。另一方面,非空时这样的 iii 一定存在,因为若不存在,每个 iii 都至少对应一个 jjj 满足 j≠i,j∘i=ij\neq i,j\circ i=iji,ji=i,我们从 iiijjj 连一条有向边,可以发现边数与点数相等,那么必定有环。由于每个等价类都不和自身连边,那么环中至少有两个不同元素。但对于一个环,考虑环中所有元素的 ∘\circ 运算的结果,通过调整运算顺序可得该结果与环上每个元素相等,矛盾。

重新标号后,我们按非零元素对应的等价类从前到后的顺序排列解。可以发现 TTT 是这种形式(设 TiT_iTi 表示第 iii 个等价类的解矩阵,即高维离散傅里叶变换的系数矩阵):

T=[T1⋯⋯⋯⋯0T2⋯⋯⋯00T3⋯⋯⋮⋮⋮⋱⋮000⋯Ttotal] T= \begin{bmatrix} T_1 & \cdots &\cdots &\cdots &\cdots \\ 0 & T_2 &\cdots & \cdots &\cdots\\ 0 & 0 &T_3 &\cdots &\cdots\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & T_{\text{total}} \end{bmatrix} T=T1000T200T30Ttotal

那么有 detT=∏detTi\det T=\prod \det T_idetT=detTi,由高维离散傅里叶变换,detTi≠0\det T_i\neq 0detTi0,故 detT≠0\det T\neq 0detT0。证毕。

那么我们的算法就是:首先找出每个元素生成子群中的幂等元并将 GGG 依此划分为等价类,每个等价类内部使用算法六分解,然后再计算出变换矩阵并变换求解。

时间复杂度:O(m3+Nnm+Nlogk)O(m^3+Nnm+N\log k)O(m3+Nnm+Nlogk)
预计得分:100100100

G. 康普·莱克·西提

By CommonAnts,题解 By CommonAnts

  • 复杂度分析,递推,DP,状态压缩,连通分量,程序实现
  • 思维难度:NOIP Day1 T2 NOI
  • 实现难度:NOIP Day1 T2 WC+/CTSC+

题解包下载

介绍

萌新出题人第一次出提交答案题 qwq,希望大家做得愉快。

请从上方题解包下载链接中下载题解包。

本题模型来源于 NOIP 2017 Day1 T2 时间复杂度,要求计算出一个没有递归的纯循环程序的时间复杂度及最高次项常数。

其实一开始是出题人在 NOIP 考场上看错题了以为循环上下界可以为变量,于是考场手写 SCC 缩点,最后由于多路 return 有些地方没有撤销操作而挂成 80 分。

然而 zjt 大爷看错了也 AC 了,这大概就是实力差距吧。

参考通解程序不能通过的数据只有 4 和 8 两组共 14 分,一个较优秀的通解可以得到 90 ~ 100 分的高分,这是我们所设计的。我们并不希望这道提交答案题变成大量特解堆砌的纯实现题。多数部分分都是数据的规模及特殊边界限制。

通用解法

首先设 f(i,j)f(i,j)f(i,j) 表示函数 iii 以参数 jjj 调用时的复杂度及常数。那么我们可以对 fff 进行记忆化搜索,这部分的状态数至多为函数个数的 101 倍。现在的问题在于求出单个函数的答案。

首先可以对其中每个产生贡献的语句(S 及函数调用)分别求解,再相加。对于一个语句,我们考虑它外层嵌套的所有循环,可以发现每个循环 F i l r 相当于枚举所有 l≤i≤rl\le i\le rliriii,故它被调用的次数就是这些循环组成的不等式组的的合法解的个数。

那么我们用图论建模。若循环中有约束 a≤ba\le bab,则从 bbbaaa 连一条有向边,然后求这个有向图的解。首先每个 SCC(强连通分量)中的取值必定全部相等,只需考虑 SCC 组成的 DAG(有向无环图)。首先可以求出传递闭包来算出每个点的上下界。解的复杂度次数即为下界为常数,上界为 nnn 的点数;解的常数由两部分构成:上下界都为常数的点的解数和下界为常数上界为 nnn 的点的拓扑序个数与次数的阶乘(即它们的全排列数)之比。

这两部分都可以使用状态压缩递推来解决。拓扑序个数是经典问题,设 fw(S)fw(S)fw(S) 表示点集为 SSS 的拓扑序个数即可;对于有界部分可以规定一个拓扑序,然后设 fc(S,i,j)fc(S,i,j)fc(S,i,j) 表示集合为 SSS,当前变量取值 ≤i\le ii 且取值 =i=i=i 的点考虑到拓扑序不超过 jjj 的解数。

另外,为了计算函数调用,我们还必须求出某个变量等于某个值(或者位于某个特定的拓扑序位置)时的解数。只需在上述递推的基础上从拓扑序的反方向再做一次并更新即可。

这样我们就可以在指数级时间内解决这个问题。我们需要加一些优化来获得更好的效果。只需要加入只更新有用状态,以及将图中互不相关的弱连通分量分开考虑的优化即可在数分钟内通过每个数据(主要的瓶颈在于内存使用)。

关于近似算法

有一个近似随机化算法是在计算拓扑序个数和解数时使用随机抽样来估计,依抽样方法好坏可以取得不同的效果。在点数较多时直接让每个变量在范围内均匀随机在每次求解试验次数为 10710^7107 与点数之比时可以得到的近似比约为 222,可以取得 303030404040 分。

另外通解写挂也可以获得部分分。

以下是部分分参数(设正确答案为 VVV):

参数编号 iii li/V,V/ril_i/V,V/r_ili/V,V/ri
333 0.10.10.1
444 0.50.50.5
555 0.90.90.9
666 0.980.980.98
777 1−10−31-10^{-3}1103
888 1−10−61-10^{-6}1106
999 1−10−181-10^{-18}11018
101010 111

特殊性质解法

测试点 444888 分别是长链和两行带附加链的网格图,可以设计出多项式时间的递推算法。

数据

以下是各组测试数据的性质:
(设 DlD_lDl 表示互相约束的上界为 nnn 的变量SCC个数的最大值,dld_ldl 表示互相约束的上界为常数的变量SCC个数的最大值,DsD_sDs 表示上界为 nnn 的变量SCC个数的最大值,dsd_sds 表示上界为常数的变量SCC个数的最大值)

以下时空效率中不计算高精度运算的时间,通解对每个测试点均适用。

编号 分值 数据性质 建议解法 时空效率 实测时间1(秒) 实测时间2(秒)
111 555 LLL 很小,循环上下界只有常数和 nnn,无函数调用 手玩;分别计算每层循环的贡献;模拟+插值; N/A\text{N/A}N/AO(L)O(L)O(L)O(ans)O(\text{ans})O(ans) 0.12 0.03
222 666 LLL 较大,循环上下界只有常数和 nnn,无函数调用 分别计算每层循环的贡献;模拟+插值; O(L)O(L)O(L)O(ans)O(\text{ans})O(ans) 0.14 0.04
333 666 循环上下界及函数调用全为常数 递推; O(L)O(L)O(L) 0.15 0.25
444 666 200200200 层循环嵌套,每层循环下界均为 111,上界为上一层循环变量 计算阶乘; O(L)O(L)O(L) - 3.19*
555 888 程序中常数只有 111,且只在下界中出现,答案复杂度和常数均较小,Dl,Ds≤7D_l,D_s\le 7Dl,Ds7 模拟+插值;状压递推(拓扑序计数); O(ans)O(\text{ans})O(ans)O(L2(2D+maxconst2d))O(L^2(2^D+\text{maxconst}2^d))O(L2(2D+maxconst2d))(以下用 TTT 表示此值); 0.11 0.03
666 888 Ds,ds≤7D_s,d_s\le 7Ds,ds7,无函数调用 搜索/枚举;状压递推; O(L2(D!+dmaxconst))O(L^2(D!+d^\text{maxconst}))O(L2(D!+dmaxconst))TTT 0.15 0.16
777 999 Dl,dl≤8,Ds,ds≤12D_l,d_l\le 8,D_s,d_s\le 12Dl,dl8,Ds,ds12 枚举(分离无关变量)/枚举常数变量的大小顺序+递推;状压递推; O(L2(D!+dmaxconst))O(L^2(D!+d^\text{maxconst}))O(L2(D!+dmaxconst))O(L2(D!+d!maxconst))O(L^2(D!+d!\text{maxconst}))O(L2(D!+d!maxconst))TTT 0.45 4.46
888 888 约束关系形成一个两行并含有附加链的网格图,无函数调用 递推; O(L2)O(L^2)O(L2) - 3.41*
999 888 变量上界全为 nnn,每个函数中 Dl,Ds≤31D_l,D_s\le 31Dl,Ds31,且状压的有效状态数较小 状压递推(拓扑序计数); TTT 0.30 0.53
101010 888 变量上界全为常数,每个函数中 dl,ds≤18d_l,d_s\le 18dl,ds18,且状压的有效状态数较小 状压递推(常数方案数); TTT 240.37 35.69
111111 999 每个函数中 Dl,dl,Ds,ds≤18D_l,d_l,D_s,d_s\le 18Dl,dl,Ds,ds18,且状压的有效状态数较小 状压递推; TTT 245.86 116.57
121212 888 每个函数中 Dl≤9,dl≤6,Ds≤31,ds≤18D_l\le 9,d_l\le 6,D_s\le 31,d_s\le 18Dl9,dl6,Ds31,ds18 状压递推(分离无关变量); TTT 0.13 0.81
131313 111111 每个函数中 Dl,Ds≤31,dl,ds≤18D_l,D_s\le 31,d_l,d_s\le 18Dl,Ds31,dl,ds18 状压递推优化; TTT 128.98 132.24

注:

实测时间 1 是 C++ 程序,实测时间 2 是 Python2 程序,包含数据 4 和 8(标有*)在内均为通解。

感谢 xudyh 提供 Python 通解。

测试结果均在如下条件进行:

  • Intel(R) Core(TM) i5-6500 CPU @ 3.20GHz, 8G RAM, 1T HDD
  • Ubuntu 16.04 + g++ 5.4.0/Python 2.7.12(以上均为 64 位)
  • g++ 开启 -Ofast 优化

C++ 较慢的原因主要在于定长高精度带来的巨大常数。

共 4 条回复

T404

感谢大爷教我如何卡矩乘常数

kczno1

矩乘过500的似乎就我的程序了。。 https://loj.ac/submission/50715

jjikkollp

催更(逃

YueZhengLing

时间都不用pypy测的么QwQ