I am bike.

ABC465G

简要题意

给你一个整数 $N,M,C,K$ 和一个长度为 $N$ 的整数序列 $A=(A _ 1,A _ 2,\ldots,A _ N)$ 。

给你 $Q$ 个查询，你应该按顺序处理这些查询。在 $q$ -th $(1\le q\le Q)$ 查询中得到了整数 $i _ q,X _ q$ ，在将 $A _ {i _ q}$ 更改为 $X _ q$ 之后，你应该解决下面的问题。

求 $\displaystyle \sum _ {k=0}^{K-1} \mathop{\mathrm{mex}}\limits _ {1 \le i \le N} \lbrace (Ck+A _ i)\bmod M\rbrace$ 的值。这里的 $\displaystyle \mathop{\mathrm{mex}}\limits _ {1 \le i \le N} B _ i$ 表示整数序列 $B=(B _ 1,B _ 2,\ldots,B _ N)$ 中不包含在 $B$ 中的最小非负整数。

• $1\le N\le 2\times 10^5$
• $0\le C < M \le 10^9$
• $1\le K\le 10^9$
• $0\le A_i < M$
• $1\le Q\le 2\times 10^5$
• $1\le i_q \le N$
• $0\le X_q < M$

题解

尝试用抽象思维解读题目这个集合 $S_k=\{(k\times C+a_i)\bmod M|1\leq i \leq n\}$。不妨考虑有一个首尾相连的 $M$ 个点的环，将编号等于某个 $a_i$ 的所有位置打上标记，接着从编号为 $-kC\bmod M$ 的位置开始，$\text{mex}(S_k)$ 即为从这个位置开始走几步能走到没打上标记的位置。

下文部分表述省略对 $M$ 取模。

接着考虑标记一个位置/取消标记一个位置会对答案产生什么影响，假设需要标记 $x$，那么求出从 $x-1$ 开始往左的极长连续标记段和从 $x+1$ 开始往右的极长连续标记段，设最左和最右分别为 $L,R$（当标记 $x$ 后所有位置都被标记时，作为特殊情况特判处理），那么答案会增加 $(R-x+1)\times \text{tot}_{[L,x-1]}$ 其中 $tot_{[l,r]}$ 是 $-kC\bmod M$ 落在区间 $[l,r]$ 内的次数。取消标记则是逆过程。

关于 $L,R$ 的求值与连续段的维护可以使用 std::set 不过多赘述，最关键的问题是 $\text{tot}_{[l,r]}$ 的求法。

不妨令 $0\leq l\leq r< M $，设 $g=\text{gcd}(C,M),c=\frac{C}{g},m=\frac{M}{g}$，那么 $s_k=-kC\bmod M$ 只可能落在 $g$ 的倍数上。将 $l,r$ 压缩至模 $m$ 的完全剩余系中，即令 $l'=\lceil \frac{l}{m}\rceil,r'=\lfloor \frac{r}{m}\rfloor$。问题变成了，从 $s_0=0$ 开始，每次移动 $m-c$ 格，落在 $[l',r']$ 中的次数。这个问题可以用类欧几里得算法解决，具体的，利用 $[(a\times x+b)\bmod c < y] = \lfloor\frac{a\times x+b}{c}\rfloor-\lfloor\frac{a\times x+b-y}{c}\rfloor$ 即可。

总时间复杂度 $O((n+q) \times (\log {n}+\log {10^9}))$。

SEQ2

简要题意

一个由整数 $[1, N]$ 构成的子集被称为好子集，当且仅当存在某个整数 $X$，使得 $X, X + 1, X + 2, \ldots, X + K - 1$ 中的每一个都属于该子集。

例如，当 $K = 3$ 时，$\{1, 2, 3, 5, 6\}$ 是一个好子集，但当 $K = 4$ 时则不是。

对于整数 $[1, N]$ 的一个排列 $P$，定义 $f(P)$ 为使集合 $P[1, i]$ 成为好子集的最短前缀的长度（记该长度为 $i$）。

例如，对于 $K = 3$，以及 $P = [1, 2, 5, 6, 3, 4]$，可以证明 $f(P) = 5$。

求所有 $N!$ 个可能的排列的 $f(P)$ 之和。由于答案可能很大，请输出结果对 $998244353$ 取模后的值。

• $1 \le T \le 1000$
• $2 \le K \le N \le 2 \cdot 10^5$
• 所有测试数据中 $N$ 的总和不超过 $2 \cdot 10^5$。

题解

答案等于 $n!+\sum_{i=1}^{n} f_i$ 其中 $f_i$ 表示前 $i$ 个数构成的集合中不存在长度为 $K$ 的编号连续段的方案数。

令 $p_0=0 < p_1 < p_2 < p_3 < ... < p_{N-i} < N+1=p_{N-i+1}$ 为所有不在前缀 $i$ 内的元素，则有限制 $p_{j+1}-p_j\leq K$ 对所有 $j$ 满足。枚举 $j$ 表示钦定 $j$ 个 $p$ 的间隙大于 $K$，则 $f_i=\sum_{j=0}^{\min(N-i+1,\lfloor \frac{N}{K}\rfloor)} (-1)^j \binom{N-i+1}{j} \binom{N-jK}{N-i}i!(N-i)!$。

$Ans=\sum_{i=1}f_i=\sum_{j=0}^{\lfloor \frac{N}{K}\rfloor} \sum_i (-1)^j\binom{i+1}{j}\binom{N-jk}{i}i!(N-i)!$。

对于固定的 $j$，有

$\sum_i (-1)^j\binom{i+1}{j}\binom{N-jk}{i}i!(N-i)!=\sum_i (-1)^j\binom{i+1}{j}\frac{(N-jk)!i!(N-i)!}{(N-jk-i)!i!}=$

$\sum_i (-1)^j\binom{i+1}{j}\frac{(N-jk)!(N-i)!(jk)!}{(N-jk-i)!(jk)!}=(-1)^j (N-jk)!(jk)! \sum_i \binom{N-i}{jk}\binom{i+1}{j}$，右侧是范德蒙德卷积直接化成 $\binom{N+1}{jk+j}$。

时间复杂度 $O(N)$。

WC2025 即将来临，Public Round #14 将在 2025 年 1 月 12 日的早上 8:30 举行！比赛将进行 5 小时，共 3 道题，OI 赛制。

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

本次模拟赛的搬题人为 Lynkcat ，组题人为 Lynkcat ，验题人为 znstz, Kevin114514 等。

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

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

暂时离开了，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)$。

最短路径

？