时代边哥团我们喜欢你

我们喜欢你啊我们喜欢你

你是最帅最帅的，最帅的

我们喜欢你啊我们喜欢你

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)$ 即可。

总结：

边哥锐评：太不牛了。