暂时离开了，qoj，呜呜呜。希望尽快再见。拜拜ヾ(•ω•`)o

NOI 2024 即将来临，Public Round #13 将在 2024 年 6 月 30 日 8:30 举行！比赛将进行 5 小时，共 3 道题，OI 赛制。

本次比赛的题目难度约为 NOI 难度，方便选手调整状态，所有题目都有部分分。

本次模拟赛的组题人为 Lynkcat，搬题人为 p_b_p_b, Crysfly, Lynkcat，验题人为 cmll02 。

赛后会公开原题链接和题解链接。

特别提醒：本次比赛的题目均为原题，但为了比赛的公平性，请勿在比赛时尝试查找原题地址。如不幸见过原题，请向管理员报告。

时代边哥团我们喜欢你

我们喜欢你啊我们喜欢你

你是最帅最帅的，最帅的

我们喜欢你啊我们喜欢你

CF1149D

一张 $n$ 个点 $m$ 条边的无向图，只有 $a,b$ 两种边权 $(a < b)$，对于每个 $i$，求图中所有的最小生成树中，从 $1$ 到 $i$ 距离的最小值。

$n\leq 70,m\leq min(300,n\times (n-1)/2)$。

很喜欢这种幽默到我不会做的题

我先来说一下我写的假做法，在 NOI 模拟赛赛时通过了所有数据。

先有一些很基本的观察：一条合法的路径不能重复经过一个 $a$ 边连通块。然后我啥也不会做了。编了一个锤子东西：

记 $f_{x,y,i,j}$ 为当经过了 $x$ 条 $a$ 边与 $y$ 条 $b$ 边时，到达 $i$ 点是否必须要经过 $j$ 号连通块。

然后转移，碰到不必须经过的就转移过去，形式是 bitset 的与操作，时间复杂度 $O(\frac{n^4m}{w})$。

为什么错了呢，因为当我 $f_{x,y,i,j}$ 为 $0$ 时，转移过去的 mask 实际上有一些位置应该要改为 $1$（换句话说，当我钦定一个某个不必须经过的点需要经过的时候，有些点会从不必须经过变成需要必须经过）

正解是一个简单至极的观察：连通块数 $\leq 3$ 的时候往外走一定不优，所以只要状压记大小 $>3$ 的连通块即可。

哈哈

Zoo Management

一张 $n$ 个点 $m$ 条边的图跟两个长度为 $n$ 的序列 $a,b$，每次可以把一个置换环上的 $a$ 同时顺时针/逆时针旋转一下，问能不能变成 $b$。

$n,m\leq 4\times 10^5$。

把这题出 OI 赛时比赛是不是多少有点歹毒。

首先有显然的观察：环的时候要做 kmp，不同边双的是割裂的

然后有简单的猜测：当边双不是环的时候可以取遍所有状态。

可以通过所有样例，并且 $n\leq 8$ 拍一万组也拍不出来。

但是你只要稍微注意力集中一点或者写个暴力试一下，会发现，是排列情况下且只有奇环的时候，并不能取满所有状态，而是只能取一半。

为什么呢，考虑排列情况下置换环个数的奇偶性，会发现 rotate 一个奇环不会改变置换环个数的奇偶性。。。

于是你需要判断边双之内存不存在偶环：具体地，抠出边双内的每个点双，若大小为偶数则一定存在偶环，否则大小为奇数时，若点双不为环，那么也一定有偶环。

然后你可以写完整个题的代码，但是在赛时最好别写挂，因为根本没法拍。。。

VietnamTeamSelectionTest-D1P2

给定一个长度 $m$ 不超过 20 的 01 串 $S$，求能选出多少长度为 $n$ 的 01 串满足两两不循环同构且不把其中一个翻转后做到循环同构，对 $10^9+7$ 取模。

$n\leq 10^9$。

出这个题的是变态吧？？

套用一下带权 Burnside 引理，问题可以转化成求 $n$ 个循环置换以及 $n$ 个翻转循环置换之后，满足 $S$ 或者 $S^R$ 在串中出现（一个后缀拼一个前缀也算出现）的长度为 $n$ 的串的个数。

先解决一下翻转循环置换，手模一下情况就会发现等价于枚举对称轴，因此当 $n$ 是偶数的时候只要算两种情况的答案，而 $n$ 是奇数的时候只要算一种即可。

讨论其中一个情况，其他情况类似，问题变成数串 $T$满足是回文串且满足 $S$ 或者 $S^R$ 在串中出现。

容斥一下先算不出现的方案数，减一下即可得到原问题答案。

将 $S$ 跟 $S^R$ 建 KMP 自动机，设 $T=X+X^R$，其中 $+$ 是字符串拼接，首先枚举 $X$ 的前 $m$ 位然后判断是否能走一段 $X^R$ 的后缀然后走一段 $X$ 的前缀使得走到任意一个 $m$ 的状态，如果不可以，设当前 $X$ 的前 $m$ 位在两个自动机上的状态是 $(x,y)$，先把 $cnt_{x,y}$ 加一。然后对于不同的 $(x,y)$ 继续转移 $\frac{n}{2}-m$ 步，每次是 $(x,y)$ 转移到走 $0$ 或者走 $1$，这里可以矩阵快速幂优化。最后把每个最终状态 $(X,Y)$ 中能拼成 $m$ 的去掉，这个可以预处理。

接下来解决循环置换，设 $F(k)$ 为长度为 $k$ 的串满足 $S$ 或者 $S^R$ 在串中出现。$k\leq m$ 的情况显然可以暴力枚举每个串。$>m$ 的情况可以矩阵快速幂，因此不难发现 $F$ 在 $>m$ 时的答案应当是一个长度为 $O(m^2)$ 的整式递推。设常数 $B=500$。

设 $(x,y)$ 为一个串 $T$ 在自动机上的最终状态，如果 $T$ 不包含 $S$ 或者 $S^R$ 显然在初始状态是 $(x,y)$ 的情况下，每一步都不能走到任意一个自动机的 $m$。枚举 $(x,y)$ 然后求出长度 $\leq B$ 的所有答案，然后 BM 求一下递推式然后多项式取模随便算一下每个 $k|n$ 时的 $F(k)$ 即可。

总结：

边哥锐评：太不牛了。

回文路径

枚举回文中心在哪一行的哪个位置，那么在这一行的回文串一定是取的越长越好，可以直接二分哈希。

正方形计数

枚举一条 $(x,y)$ 向量表示第二个点与第一个点之间的位移，满足 $x+y>0$，计算包含这个向量的合法正方形的个数。

把其他三个点相对于第一个点的位移都求出来，关于 $n$ 个半平面可以得到新的 $n$ 个半平面。

求出半平面交之后，可以得到若干 $ax+by+c\geq 0$ 的限制，使用一些差分的手段后可以转化成求一个 $[0,MAX]\times [0,MAX]$ 的矩形与一个半平面的交形成一个三角形，求这个三角形中的整点个数，由于斜率只有 $n$ 种，进行 $n$ 遍前缀和即可。

独立

树上最大权独立集的经典做法是设 $dp_{k,0/1}$ 表示 $k$ 这个位置是否被选中，不难发现有 $\max(dp_{k,0},dp_{k,1})-dp_{k,0}\leq V$。

考虑设 $siz_k$ 表示 $k$ 子树的大小，设 $f_{k,i}$ 表示 $k$ 子树内，$\max(dp_{k,0},dp_{k,1})-dp_{k,0}=i$ 的方案数。那么有答案为 $\sum_k\sum_i f_{k,i}\times i \times m^{n-siz_k}$。

可以证明 $f_{k,i}$ 在当 $i\not = 0$ 的时候是关于 $i$ 的一个 $siz$ 次多项式，因此考虑拉格朗日插值。

考虑 $u$ 转移到 $k$ 的时候是个减法卷积，因此我们试图求出 $f_{k,m-siz_k...m}$，这可以直接减法卷积。这部分复杂度是 $\sum siz_k\log siz_k$ 的。

接着我们直接使用 $f_{k,m-siz_k...m}$ 点值平移出 $f_{k,1...siz_k}$。这样就能够继续转移到 $k$ 的父亲了。求答案就用 $f_{k,i}\times i \times m^{n-siz_k}$ 的前缀和插一下就行了。同样的 $f_{k,0}$ 的处理也可以拉插，当 $u$ 转移到 $k$ 时（$f'_k\otimes f_u\rightarrow f_k$），把 $\{f'_{k,i}\times (\sum_{j=i}f_{u,j})\}$ 弄几个能算的出来拉插就能转移到新的 $f_{k,0}$ 了，当然还要加上 $f'_{k,0}$ 的贡献，不过处理方式是一样的。

因此整个题可以做到 $O(n^2\log n)$ 的时间复杂度。

分流器

二分答案 $ans$，设 $f_i$ 表示 $i$ 被访问到的次数，那么接下来一定两条出边会各被访问一半，也就是 $f_{out_{i,0}}+=\frac{f_i}{2}$，$f_{out_{i,1}}+=\frac{f_i}{2}$。在过程中判一下是否满足每个点是奇数即可，用 ull 压位高精时间复杂度 $O(\frac{n^3}{w})$。

注意到 $ans$ 只有 lowbit 有用，所以答案一定是 $2$ 的某个次幂，二分指数即可做到时间复杂度 $O(\frac{n^2\log n}{w})$，可以通过。

upd：也可以不需要二分，直接求 $ans$ 为 $2^n$ 的时候每个点的 lowbit 的最小值即可。

排队

扫描线，每个询问在左端点处插入，右端点处查询。

因为询问初始给的初值均为 $0$，因此先插入的询问在同一个右端点处的答案不会比后插入的要小。

因此，将询问按左端点排序，每次的操作形如找到一个区间满足区间内的值都在 $[l,r]$ 内，然后集体 $+1$，可以在树状数组上二分实现。

时间复杂度 $O(n\log n)$。

最短路径

？