题意 题目链接 题目中给出了一个 $N$ ，而我们要求的是有多少对$(a,b)$ 使得一个 $a$ 行 $b$ 列的矩形,满足其对角线穿过的格子数为 $N$。 解析 通过画图以及对题意的观察与分析，我们发现，对于一个 $a,b$ 互质的矩形，其对角线穿过的格子应该是呈阶梯状上升的(如图)。 我们再像小学做这类数学题一样，将这些格子推向两边，可以数出…

题意 一个长度为 $N+M$ 的 $01$ 串，包含 $N$ 个 $0$ 和 $M$ 个 $1$。 现在随机生成这个 $01$ 串，要求在它的每个前缀中，$0$ 的个数都要不多于 $1$ 的个数。 求生成合法串的概率。 解析 首先我们知道，若 $M<N$ ，答案显然为 $0$。 然后我们发现，在 $M \ge N$时，这个题面是非常难求的，我…