比赛地址

A. 小Ho的强迫症：

不妨设存在一个位置$x_0$（以下均指脚后跟的位置）, 使得小Ho从这个位置开始能够永久行走下去，我们可以推出小Ho第$i$步的位置（相对于上条缝隙的相对位置）$P_i=(i * D) \bmod L$。

由于可踩的位置为有限个，所以在这个“永久”的过程中肯定会踩到相同的位置，然后开始重复，事实上我们可以知道第一次踩到重复的位置是在第$L / gcd(L, D)$步后，小Ho重新走到$x_0$这个位置。也就是说这个循环节的长度为$L / gcd(L, D)$。

不难发现这$L / gcd(L, D)$个位置在$[0, L]$中是均匀分布的（简单的证明就是假设不均匀，不妨设发生不均匀的连续3个位置为$x_1$, $x_2$, $x_3$，且从$x_1$走到$x_2$花费的步数为$k$，$x_2-x_1<x_3-x_2$（大于的情况是对称的），那么从$x_2$走$k$步应该能走到$x_2+(x_2-x_1)$这个位置，而这个位置会小于$x_3$，这与我们的假设“$x_1,x_2,x_3$连续”矛盾），从而我们知道这$L / gcd(L, D)$个位置的坐标分别是$x_0$, $x_0 + gcd(L, D)$, $x_0 + 2 * gcd(L, D)$, … , $x_0 + (L / gcd(L, D) - 1) * gcd(L, D)$。

小Ho能一直走下去的条件是对于任意$i$,有$P_i\leq L-F$，才能每一步都不会踩到缝隙上，等价于判断$x_0 + (L / gcd(L, D) - 1) * gcd(L, D)\leq L-F$，即$(x_0 + L - gcd(L, D) \leq L-F)$是否成立。

在这种情况下，最有可能满足条件的$x_0=0$，所以对于任意的$L, F, D$，我们只需判断$gcd(L, D)$是否大于等于$F$，就可以知道小Ho能否无限走下去。

B. 拆字游戏：

这题的基础是让你寻找所有由$1$组成的连通块，在不考虑输出顺序的情况下，可以使用宽度优先搜索解决，即首先依次访问矩阵中的$1$，并且从这个位置开始，将所有与它连通的$1$都扫描出来，并且变成$0$（也可以使用Bool数组标记），这样就能得到一个块，并且一个块不会重复扫描。

在考虑输出顺序的情况下，我们就去枚举代表点的位置，按照答案顺序（即列号为第一关键字，行号为第二关键字）顺序枚举，并且从这个代表点开始扫描（注意到代表点选取的策略和答案顺序是一致的，这就为我们带来了遍历），这样扫描到的所有块，就可以直接按照扫描的顺序进行输出。

题目有个Trick，不过也在样例里提示了，就是如果一个块所在的$01$矩阵包含于另一个块所在的$01$矩阵，要注意输出其中一个的时候不要将属于另一个块的$1$也输出出来（这个可以结合前面那个Bool数组，改成一个Integer数组，用来标记是第几个块，然后输出的时候判断只有当前块的$1$才输出）

C. 数组拆分：

首先对于每个位置预处理数组的前缀和，即$s[i]=a[1]+a[2]+…+a[i]$。

然后使用动态规划进行计算，$f[i]$表示已经对$a[1, i]$进行拆分，且第$i$个数是其中最后一段末尾的方案数，初始状态为$f[0]=1$，目标状态为$f[n]$。

在计算$f[i]$时，我们只需要找到所有满足$s[i]\neq s[j]$的$0\leq j<i$，则有$f[i]=sum ( f[j] ) $（只需保证最后一段部为$0$即可）。

而$sum(f[j]|0\leq j<i\&s[i]\neq s[j])$ $=sum(f[j]|0\leq j < i)-sum(f[j]|0\leq j<i\&s[i]=s[j])$。

所以只需在从对$i=[1, n]$递推的过程中维护$g[s]=sum(f[j]|0\leq j<i且s[j]==s)$和$h[i]=sum(f[j]|0\leq j<i)$。

这样就有$f[i]=h[i] - g[s[i]]$。

D. 矩形计数：

这题使用容斥原理来进行计算，通过枚举$i=[0, 2^N-1]$来枚举所有不能被包含的格子的一种组合，这个组合如果包含奇数个格子，那么这一项为负数，如果包含偶数个格子（包含$0$个也是偶数），那么这一项为整数。

每一项的具体值如下计算：对于这些不能包含的格子，统计最左最右最上最下的位置——$4$个坐标，不妨设为$lx,rx,ly,ry$，则至少包含这些格子的方案数为$l_x\times l_y\times (n-r_x+1)\times(m-r_y+1)$。

最后将所有项加在一起，就可以计算出答案。