题意 题目链接。 一共有 $n$ 个格子，给定两个整数 $A,B$ 分别位于第 $1$ 和第 $n$ 格，中间有 $n-2$ 个空格。询问是否存在一种填数方案满足任意相邻两个数之差的绝对值在 $[C,D]$ 之间。 解析 考虑这 $n$ 个数之间有 $n-1$ 对差，因此题目等价于： 是否存在 $A+\sum\limits^{n-1}_{i=1} …

本博客仅罗列定理，不给出证明，如需要请自行搜索。 质数相关 线性筛素数 inline void sieve(int n){//线性筛求 pri 和 phi phi[1]=1; for(int i=2;i<=n;i++){ if(!vis[i]){phi[i]=i-1;pri[++cnt]=i;} for(int j=1;j<=cnt&a…

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

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