题意 题目链接。 一共有 $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$时,这个题面是非常难求的,我…