SDOI2025集训第一轮

80+50+0 = 130，总榜 rk8，山东 rk5

显然应该先 $2^{r*c}$ 枚举左上角的 r*c 的矩形，然后不难发现只需要知道前 r 行和前 c 列就能确定整个 n*m 的矩形了。

手推一下发现 $a_{x,y}=a_{x-r,y}+a_{x,y-c}-a_{x-r,y-c}$，然后再把 $a_{x-r,y}$ 和 $a_{x,y-c}$ 用这个式子拆开，就能得到 $a_{x,y}=a_{x\%r,y}+a_{x,y\%c}-a_{x\%r,y\%c}$。

看什么时候 $a_{x,y}$ 不合法。发现当且仅当式子右边三项分别为 0,0,1 或 1,1,0 时 $a_{x,y}$ = -1 or 2 不合法，这个可以刻画为 $a_{x\%r,y\%c}$ 与 $a_{x\%r,y},a_{x,y\%c}$ 中至少一个相同。

进一步的，可得 $a_{x,y}$ 与任意的 $a_{x+k*r,y}$ 或任意的 $a_{x,y+k*c}$ 均相等，将这两种记为“行相等”和“列相等”。

也就是说，对于我们枚举的左上角的 r*c 的矩形，里面的每个位置要么满足“行相等”，要么满足“列相等”，这个就可以再去 $2^{r*c}$ 枚举了。

然后可能会有格子既满足“行相等”又满足“列相等”，容斥抵消计算即可。

进⼀步观察，当⼀个格⼦满⾜“⾏相等”时，该格⼦对于⾏的限制就不复存在，我们仅需考虑该格⼦对于列的限制；同理，当⼀个格⼦满⾜“列相等”时，该格⼦对于列的限制就不复存在，因此仅需考虑该格⼦对于⾏的限制。也就是说，每个格⼦的权值可以放在计算贡献时的统计部分进⾏，仅需考虑每⼀⾏中“列相等”格⼦的数量和每⼀列中“⾏相等”格⼦的数量即可。

然后每行每列贡献的计算可以预处理，这样就能做到 $O(3^{rc}*(r+c))$ 了。

首先有 d 是质数且 d%20==3 或 d<=10 这个限制，题目又保证数据随机，估测或者打个表看一下就知道有效点对实际上只有大概 $n^2/log n$ 对。

由此容易想到枚举点对 $(i,j)$ 并以 $d_{i,j}$ 作为最后的中位数，考虑如何算答案。

发现存在两个或三个距离相同时就不好算了，可以随便手动定义距离相同时的字典序，这样就设前面的 d 严格小于后面的 d。

这样枚举一遍所有的 k 即可。复杂度 $O(n^3/log n)$。

然后发现所有 $a_i=1$ 的 sub2 就可以直接bitset优化，$O(n^3/log n/w)$，这样就一共有 50pts 了。

考虑 bitset 的实质，我们是每 w=64 位压成一个 unsigned long long，然后通过 ull 的位运算来做的。那么这个能不能拓展到非 0/1 任意权值呢？

我们考虑每 B 个位置压成一块。。。

复杂度是 $O(n^2/B+)$。。。

最优 B 取 logn，。。。

观察“线图”的结构，会发现一个点周围的边进行一次变换之后，会形成一个团。每进行一次变换，这个图会变得更加“紧密”。

显然一个图在做一次线图变换后，连通性大致不会变（即原图中⼀个连通块不会在线图中被分裂成两个连通块）。

因为由若干个团构成，所以 k 阶线图的最⼤独⽴集就等价于 k-1 阶线图的最大匹配（选尽量多的边使得这些边两两无公共点）。

求 1 阶线图的最大匹配。

注意到线图具有较强的连通性质，那么对于每个连通块，最大匹配实际上就是 $\lfloor\frac{点数}{2}\rfloor$。而 1 阶线图的点数 = 原图的边数，所以答案 = $\sum \lfloor\frac{m}{2}\rfloor$，其中 m 是原图中一个连通块的边数。

求 2 阶线图的最大匹配。

后面基本都同理，懒得写了，看题解吧。

注意到从连续左/右走转向连续右/左走至多只有 log 次（因为每次调转方向都会翻倍），所以每次二分即可，复杂度 $O(mlog^2n)$。

做了。

90+0+15 = 105，总榜 rk27，山东 rk23

要么认识了所有的 n 个人，要么没有认识所有人。也就是说我最后会认识 i 个人 (i < n)，但是其他人都无法认识了。

设 $f_i$ 表示最终我的社交网络里恰好有 i 个人的概率，那么答案其实就是 $f_n$。

转移就是 $f_i=1-\sum\limits_{j=1}^{i-1}\binom{i-1}{j-1}f_j*(\sum\limits_{c=0}^{k-1}\binom{j-1}{c}p^c(1-p)^{j-c})^{i-j}$。

四分树 or KDT。我不会。

CRT 什么玩意的。不会。

首先题目要求的就是找一个包含颜色最少的连通块，使得内部出现的颜色和外部的颜色两两不同。

考虑点分治，对于每一次分治出来的重心 $x$，我们求出仅在 $x$ 子树中的且包含 $x$ 的最小连通块。具体就直接把需要加入的颜色加入队列，直到不需要加为止。这样一定能求出所有的答案，因为如果不包含 $x$，要么会在上一层的分治重心中算，要么会在下一层儿子那里的分治重心算。

不妨设 Bessie 从根节点出发，农民从叶子往上走，那么如果农民在 Bessie 到达某个点之前到达了这个点，那这个点的子树就“封锁”了。即要做到“准时到达封锁点”，这个用一个路径长度的不等式表示出来，就可以在根节点确定的时候，做一遍 dfs，数出有多少个封锁点就好了。那这样就有一个 $O(n^2)$ 的做法了。然后把式子形式化地表示一下，树上差分，点分治，做一个“不等式点对的点权统计”，就行了。

55+10+10 = 75，山东 rk18

注意到按照 $\frac{c_i}{1-p_i}$ 从小到大来挑战关卡一定是最优的。所以对于剩下所有的关卡中 $\frac{c_i}{1-p_i}$ 的最小的 $i$，在他的前驱 $d_i$ 挑战完之后就一定会直接挑战 $i$。

考虑合并 $i$ 和 $d_i$，合并之后的 $p=p_{d_i}*p_i,c=c_{d_i}+p_{d_i}*c_i$。用小根堆+并查集维护即可。

推箱子转为箱子瞬移，然后最大流/费用流消圈。

首先显然 $s=\sum a_i\ge 360$ 时，答案为 0。所以 $n\lt 360$。

讨论两边的角在上/下/中间，把式子写出来，dp/积分。

60+25+75 = 160，山东 rk9

考虑先按照所有位置的取值都是 1~n 去构造出一个解。然后考虑调整法。先去保证每行不重复，把被 forbidden 的数改为最小的合法的数，然后如果影响了列上的合法性就再去调整列。如此重复。不难发现不合法的位置数量不增，所以最坏做 $n^2$ 轮就会找到一组解。这样的复杂度最劣是 $O(n^4)$ 的。但是随机数据能过。

不会。

因为 $p<\frac{1}{2}$，所以显然当 $b1=2^k$ 时每次最优一定是选 $lowbit(x)$，直接记搜即可。

这其实就是 $x$ 是有限小数时。当 $x$ 不是有限小数时，它一定是一个有限小数+循环节组成。考虑 $x$ 是有限小数的做法的过程，实际上可以看作是矩阵乘法，并且可以证明循环小数部分的矩阵的无限次方是收敛的，所以直接求逆即可。

考虑直接状压 dp。设 $f_{s,x,y}$ 表示 $x$ 能否通过 $s$ 点集中的点到达 $y$，加上转移的复杂度是 $O(2^n*n^3)$。

考虑固定 $x$。只用维护 $f_{s,y}$，算答案的时候枚举两边的状态合并，这样可以做到 $O(2^n*n^2)$。

我们只维护 $f_s$，将 $y$ 放到 dp 的状态里，也就是 $f_s$ 的第 $i$ 位代表能否到达 $i$。复杂度是 $O(2^n*n)$，就能过了。

35+28+10=73，山东 rk25

当 $m$ 是奇数时，枚举哪个点是重心，用总方案数减去不合法的即可做到 $O(nm)$。考虑组合意义+递推可以做到 $O(n)$。

当 $m$ 是偶数时，容易发现可以作为中心的一定是一条链，中间的点全是 $0$。如果固定这条链，考虑链上任意一个点 $u$，设 $S$ 为满足如下条件的点的集合：在链上，编号小于 $u$，且到 $u$ 的路径上不含有其他小于 $u$ 的点。于是 $|S|\le 2$，且只需要对 $S$ 做一次容斥即可统计 $u$ 的贡献。这样我们将最小值的贡献拆到了每个点上。上述过程和链的形态没有关系，只需要容斥涉及到的点都是可能的重心即可。用并查集维护，时间复杂度 $O(nlogn+m)$。

另解：点分治。

首先，有一个 $O(n^2)$ 的 dp，设 $f_{i,j}$ 表示 $a$ 的元素之和为 $i$ 且最后一个元素为 $j$ 的方案数。

注意到，如果 $a_1=B$，那么 $\sum\limits_{k=1}^{m}a_k$ 会落在 $m*B±\frac{m*(m−1)}{2}$ 中，所以 $m=O(\frac{n}{B})$。

分类讨论 $a_1$ 的大小。如果 $a_1\le B$ 就暴力 dp，复杂度 $O(B^2)$。如果 $a_1\gt B$，直接把 $\sum_j (a_j-a1)$ 记到状态里可以得到一个 $O((\frac{n}{B})^4)$ 的做法，平衡得到 $O(n^\frac{8}{5})$。

考虑倒着做，每次往前加一个数，这样只需要记长度以及 $\sum_j (a_j-a1)$， 是 $O((\frac{n}{B})^3)$ 的，平衡得到 $O(n\sqrt n)$。

具体看 题解 吧。

10+0+0=10，山东 rk29

设 x 表示 123 最多的个数，y 表示 321 最多的个数。显然 x 越大，y 越小，那就直接双指针，考虑如何 check(x,y)。123 一定是选最前面的 x 个 1 和最后面的 x 个 3，321 同理。那这样就变成了一堆区间，中间的 2 的放置就直接排序+贪心放，这样是 $O(Tn^2logn)$ 的。

考虑优化。其实只需要求出 $x,y,x+y$ 的上界就可以直接算答案了，这样的复杂度是 $O(n)$ 的。

考虑这样的构造：有一个指针 p 和一个 26 bit 的内存，初始时 p=0。每次读取 p 指向的内存的值，如果为 0 则 p 回到 0，如果为 1 则 $p\leftarrow p+1$。移动 p 后将原先 p 指向的内存的值反转。p 第一次移动到 i 恰好需要 $2^i$ 步。每次调用会修改不超过 5 bit 的 p，以及 1 bit 的内存，总共不超过 6 bit。

题目：给定一张 n 个点的竞赛图 G，所有边的边权都是 1。求 G 中两两点对间的最小割。

100+8+21=129，山东 rk14

做了。

100+0+0=100，山东 rk12