#11 2024.1.2-526互联

504. xsy5330 cake

505. xsy5331 简单数学题(math)

考虑求 \({n \choose m}\) 在模 \(p^k\) 意义下的值。其中 \(p\) 是很小的质数。发现我们只需要把 \(n!\) 写成 \(u \times p^{x}\) 就行了，其中 \(u = n! \bmod p^k\)。

发现 \(n! \leftarrow ({n \over p})! \times \prod_{i \neq kp} i\)，所以递归下去，只需要算后面这个东西。把它写成 \(\prod (ip + j)\)，发现是若干段。把它看作多项式，发现我们只需要 \(p\) 的次数小于 \(k\) 的项。散块可以暴力乘，整块可以进行倍增，只需要实现多项式平移就行了。因为只有 \(k\) 项，所以平移很方便。

506. xsy5332 拯救创界山（mountain）

507. loj3990 「IOI2023」足球场

508. loj3992 「IOI2023」超车

509. xsy5345 killshot

510. xsy5346 game

511. xsy5347 starboy

绝世好题，只是模拟赛的时候想起了非常不好的回忆。

先来点前置知识：

合并两条不交的哈密尔顿链 \(x,y\)：考虑新链 \(z\)，每次取出 \(x,y\) 的链头 \(a,b\)，若 \(a \rightarrow b\)，就把 \(a\) 放进 \(z\) 的链尾。否则把 \(b\) 放链尾。
可以使用上面这东西套个分治，求出一个点集的哈密尔顿链。
利用强连通分量里的哈密尔顿链构造哈密尔顿环：类似强连通分量的耳分解，先随便找个耳，然后不断加最小的耳进去。
我自己 yy 的 \(O(n)\) 求出强连通分量内从 \(x\) 出发的哈密尔顿路：考虑以 \(x\) 为根搞个 dfs 树，按照 dfs 序遍历，如果这条边向下指就无事发生。如果是要先往上走再往下，考虑从这条边的父亲先走到这条边的儿子，然后走完儿子子树之后，再走回原来的边。

先只考虑第二问。答案就是 \(S\) 能走到的点集大小。

拉出原竞赛图上的链，显然只需考虑 \(S\) 的那个连通块。找出这个连通块的哈密尔顿环，那么 ban 掉的点把环分成了 \(k\) 段。显然 \(S\) 能走到的点一定是每一段的一个后缀。一开始只有 \(S\) 这个后缀，尝试不断增广获得所有后缀。先试着增广自己：设这一段是 \([L,R]\)，中间有个 \(S\)。发现如果 \([S,R]\) 有能走到 \([L,S)\) 的边，就可以把这段后缀长度加一。然后增广别人，设另一段是 \([l,r]\)，后缀端点是 \(T\)。发现如果 \([S,R]\) 有能走到 \([l,T)\) 的边，就可以把 \(T\) 的后缀长度加一。只会增广 \(n\) 次，每次复杂度是 \(k\)，所以是 \(O(nk)\) 的。

考虑第一问：事实上和第二问差不多！首先找出所有后缀。那么每个后缀天然就是一条哈密尔顿链，把它们拼起来，再套用刚刚链变环的做法，变成一个 \(\rho\) 状的东西，发现 \(S\) 一定在环上！那就容易了！

512. loj3991 「IOI2023」山毛榉树

513. loj573 「LibreOJ NOI Round #2」单枪匹马

wtf 怎么跟 noi2021d2t2 一模一样。

514. loj574 「LibreOJ NOI Round #2」黄金矿工

515. loj3277 「JOISC 2020 Day3」星座 3

516. loj3278 「JOISC 2020 Day3」收获

有人看错题了，以为是每 \(C\) 秒产出一个苹果，然后对着万能欧几里得自闭了一万年。~~我为什么老是干这种事。~~

考虑让树动，人站着不动。每棵树向它第一个碰到的人连边。每个人向它逆时针 \(C\) 步之后遇到的第一个人连边，表示这次吃果子之后的下一个人。

那么树就会沿着这个图一直运动，发现这个图是基环树。答案就是在指定时间内树经过某个点的总次数。

考虑把基环树的一条边 \(u \rightarrow v\) 断掉，这就变成了以 \(u\) 为根的树。先统计树到 \(u\) 之前的答案，这是容易的。考虑树经过 \(u\) 之后的答案，发现树 \(i\) 对点 \(x\) 的询问 \(T\) 的贡献是 \({T - t_i - d_x \over L} + 1\)。大概按照 \(T\) 排个序，简单处理一下余数就行了。

517. uoj509 【JOISC2020】迷路的猫

感觉是很厉害的题！

考虑 \(A \geq 3\) 的情况：建出 bfs 树，然后每套边编号 \(\min(dep_x ,dep_y) \bmod 3\)。

考虑 \(A = 2\) 的链的情况：把链染成 BBWBWW 这个东西一直循环，那么至多走错 3 步就知道正确方向是啥了。

考虑到树上：设当前要给点 \(u\) 的儿子们染色，记 \(faw_u = x\)。如果 \(u\) 有大于 1 个儿子，就全都染 \(1 -x\)。否则把深度最浅的有超过一个儿子的子树内的点 \(v\) 找出来，在 \((fa_u,v)\) 的链上施以链的情况。可以根据 \(x\) 来决定是以 \(BBW\) 开头还是 \(WWBB\) 开头。如果这个链过于短，那也可以找到方向。