1

给定 $n$，求

$$
\sum_{k=1}^{n}k\sum_{j=1}^{k}\sum_{i=0}^{n-1}{i \choose k-j}{n-i-1 \choose j - 1}
$$

保证 $n \le 10^9$

~~毒瘤出题人，怕是从文化课卷子上抄的题~~

首先需要知道，${i \choose k-j}{n-i-1 \choose j - 1}$ 的组合意义，即从大小为 $i$ 的集合中挑出 $k-j$ 个元素的方案数，乘上从大小为 $n-i-1$ 的集合中挑出 $j-1$ 个元素的方案数

然后对它求和，即 $\sum_{j=1}^{k}{i \choose k-j}{n-i-1 \choose j - 1}$，也就是 ${n-1 \choose k-1}$

由于后者的每一种组合方法都会在前者中唯一对应，因此两者相等

于是接着化简：

$$
\begin{aligned}
&\sum_{k=1}^{n}k\sum_{j=1}^{k}\sum_{i=0}^{n-1}{i \choose k-j}{n-i-1 \choose j - 1} \\
=&\sum_{i=0}^{n-1}\sum_{k=1}^{n}k\sum_{j=1}^{k}{i \choose k-j}{n-i-1 \choose j - 1} \\
=&\sum_{i=0}^{n-1}\sum_{k=1}^{n}k {n-1 \choose k-1} \\
=&n\sum_{k=0}^{n-1}(k+1) {n-1 \choose k} \\
=&n\left(\left(\sum_{k=0}^{n-1}k {n-1 \choose k}\right)+\left(\sum_{k=0}^{n-1}{n-1 \choose k}\right)\right)\\
=&n\left(\left(\sum_{k=0}^{n-1}\frac{(n-1)!k}{k!(n-1-k)!}\right)+2^{n-1}\right)\\
=&n\left(\left(\sum_{k=0}^{n-1}\frac{(n-2)!(n-1)}{(k-1)!((n-2)-(k-1))!}\right)+2^{n-1}\right)\\
=&n\left(\left((n-1)\sum_{k=0}^{n-1}{n-2 \choose k-1}\right)+2^{n-1}\right)\\
=&n\left(\left((n-1)\sum_{k=0}^{n-2}{n-2 \choose k}\right)+2^{n-1}\right)\\
=&n((n-1)2^{n-2}+2^{n-1}) \\
=&n(n+1)2^{n-1}
\end{aligned}
$$

2

有 $m$ 个人在一个环形跑道上跑步，跑道可以看成 $n$ 个格子，格子按照顺时针从 $0$ 编号到 $n-1$

一开始每个人都在第 $0$ 号格子，之后第$i$个人每次都会向前走 $a_i$ 步，如果他从第 $n-1$ 个格子处往下走一步，那么他会到达第 $0$ 个格子

求有多少个格子永远不会被走到

$1 \le n \le 10^9,1 \le m \le 50, 1 \le a_i \le n$

首先如果一个格子 $x$ 会被走到，则有 $pa_i \equiv x \pmod {n}$

也就是说 $pa_i - nq=x$ 存在整数解，即 $\gcd(a_i,n) \mid x$

也就是说对于第 $i$ 个人，他会走到所有在 $[0,n)$ 中，是 $\gcd(a_i,n)$ 的倍数的格子

同时可得，$i$ 和 $j$ 同时可以到达的格子都是 $\text{lcm}(\gcd(a_i,n),\gcd(a_j,n))$ 的倍数

于是可以直接用容斥搞一搞

设 $b_i=\gcd(a_i,n)$，且 $B={b_i \mid i \in [1,m] \cap \mathbb{Z} }$，定义 $\text{lcm}(\emptyset)=1$

则答案 $T$ 满足：

$$
\begin{aligned}
T=\sum_{S \subseteq B} (-1)^{\mid S \mid} \frac{n}{\text{lcm}(S)}
\end{aligned}
$$

如果对所有的 $b_i$ 进行排序去重后，可以获得 $90$ 分的好成绩

然而其实可以再优化

发现 $\text{lcm}(S)$ 的种类数不会超过 $\sigma_0(n)$ ，因为 $b_i=\gcd(a_i,n)$，所以 $b_i \mid n$

对于 $x \mid n,y \mid n$，有 $\text{lcm}(x,y) \mid n$，证明可以考虑 唯一分解定理 和 最小公倍数的定义

于是可以依次插入所有的 $b_i$，同时维护当前所有的 $b_i$ 构成的 $\text{lcm}$ 的集合，并依次更新

又由于 $\sigma_0(n) \le \sqrt n$，因此时间复杂度为 $O(\sqrt n m\log(n))$

3

有 $n$ 个格子，每个格子里可以选择：

放一个价值为 $a$ 的物品

放一个价值为 $b$ 的物品

放一个价值为 $a+b$ 的物品

什么都不放

求对于所有格子都决策之后，放下的物品的价值总和为 $k$ 的方案数

$1 \le n \le 10^7$

$0 \le k \le 10^{15}$

$0 \le a,b \le 10^5$

~~看起来很棘手~~

首先需要特判 $a,b$ 中至少一个是 $0$ 的情况

考虑枚举放多少个价值为 $a$ 的物品，假设放了 $x$ 个，那么剩下必须放价值为 $b$ 的物品共 $\frac{k-ax}{b}$ 个

那么答案就是 $\sum_{i=0}^{n} {n \choose x} {n \choose \frac{k-ax}{b}}$

至于价值为 $a+b$ 的那些物品，在如上的计数中重合的部分就是那些了

注意在累加的时候应判断是否合法

4

给定一个 $n \times m$ 的 $01$ 矩阵，求包含 $[l,r]$ 个 $1$ 的子矩形个数

$n \le 30,m \le 5 \times 10^4,0 \le l \le r \le n \times m$

感觉似曾相识……想了想后发现似乎就是入阵曲这样的套路题……

由于 $n$ 比较小，所以可以枚举一个上下边界，然后把在上下边界中的行都压成一行，这样新的序列中的每一个连续区间都对应着原矩阵的一个子矩阵

询问 $[l,r]$ 可以拆成 $[0,r]$ 和 $[0,l-1]$ 然后前者的答案减去后者的答案就行了

于是可以对新序列做一个前缀和，然后就只需要询问 $s_r-s_l \le x$ 的个数了，即 $s_l \ge s_r-x$

可以先枚举 $r$，然后由于 $s_r$ 是不减的，于是可以直接维护最靠左且可行的 $l$ 就行了

时间复杂度 $O(n^2m)$

5

给定 $n$ 个正整数序列 $𝑎 _ 1, 𝑎 _ 2, \dots , 𝑎 _ 𝑛$，每个序列长度为 $m$

选择至少 $1$ 个序列，在每个被选择的序列中选择一个元素，求出所有被选择的元素的 $gcd$

求所有方案的结果之和，答案对 $10^9+7$ 取模

两种方案不同，当且仅当存在至少一个元素，在一种方案中被选择，在另一种中没有

$n \le 20, m \le 10^5,a_{i,j} \le 10^5$

由于值域不大，所以可以枚举最大公约数 $d$，设 $f(d)$ 表示最大公约数恰好为 $d$ 方案数

那么答案就是 $\sum_{d=1}^{10^5}d \cdot f(d)$

然而 $f(d)$ 不太好求，但如果要求最大公约数是 $d$ 的倍数的方案数的话还是很好做的，设这个是 $g(d)$

然后有 $g(n)=\sum_{n \mid d}f(d)$，直接莫比乌斯反演成 $f(n)=\sum_{n \mid d}\mu(d)g(\frac{d}{n})$

然后就做完了……

6

你在一个数轴上走路，一开始你会随机获得 $n$ 张卡片，每张卡片上写着一个 $[1,m]$ 之间的整数，第 $i$ 张卡片上的数字是 $x_i$

每次你可以选择任意一张卡片，然后向左走上面对应的数字的步数，或者向右走上面对应的数字的步数

一开始你在数轴原点处，求最终可以走到数轴 $1$ 点处的概率

$1 \le n,m \le 10^{11}$

首先，裴蜀定理告诉我们，对于如下关于$x_i$的整数方程：

$$
\sum_{i=1}^{n}a_ix_i=k
$$

有解的条件是$\gcd(a_1,a_2,a_3, \dots , a_n) \mid k$

在这道题中，是求$\gcd(x_1,x_2,x_3, \dots , x_n) \mid 1$的方案数，即$\gcd(x_1,x_2,x_3, \dots , x_n)=1$的方案数

于是推式子：

$$
\begin{align}
&\sum_{i_1=1}^{m}\sum_{i_2=1}^{m} \dots \sum_{i_n=1}^{m}[\gcd(i_1,i_2, \dots i_n)=1] \\ =&\sum_{i_1=1}^{m}\sum_{i_2=1}^{m} \dots \sum_{i_n=1}^{m}\sum_{t \mid \gcd(i_1,i_2, \dots i_n)}\mu(t) \\
=&\sum_{t=1}^{m}\mu(t)\sum_{i_1=1}^{m}\sum_{i_2=1}^{m} \dots \sum_{i_n=1}^{m} [t \mid i_1 \wedge t \mid i_2 \wedge \dots \wedge t \mid i_n]\\
=&\sum_{t=1}^{m}\mu(t) \lfloor \frac{m}{t} \rfloor^n
\end{align}
$$

然后就是套路了，由于$\lfloor \frac{m}{T} \rfloor$的取值范围只有$\sqrt m$种，所以可以对其数论分块

之后就要处理一段区间中的$\mu$之和，这个直接杜教筛就行了

7

有两类物品，第一类一共有 $n$ 个，第二类一共有 $[0,M]$ 个

求从这两类中任意拿出 $k$ 个物品，其中有质数个第一类物品的概率

对于每一个 $m \in [0,M]$ 都输出一遍答案

$n,M,k \le 10^5$

显然答案是

$$
T(m)=\frac{\sum_{p \in \mathbb{P} } {n \choose p} {m \choose k-p} } { {n+m \choose k} }
$$

分母可以直接预处理出来，所以只需要关注上面那个式子怎么做，显然有：

$$
\begin{aligned}
h(m)=&\sum_{p \in \mathbb{P} } { n \choose p } { m \choose k-p} \\
=&\sum_{i=0}^{m} {n \choose k - i}[k-i \in \mathbb P \wedge 2 \le k-i \le k] {m \choose i} \\
=&m!\sum_{i=0}^{m} \frac{ {n \choose k - i}[k-i \in \mathbb P \wedge 2 \le k-i \le k]} {i!} \frac{1} {(m-i)!} \\
=&m!\sum_{i=0}^{m}f(i)g(m-i)
\end{aligned}
$$

于是可以先求出 $\hat h=f \times g$，之后就可以通过 $h(m)=m! \hat h(m)$ 来求出 $h$ 了

于是就有

$$
T(m)=\frac{h(m)} { {n+m \choose k} }
$$

~~所以说为什么联赛模拟中会有快速数论变换啊~~

8

求 $(n-1)! \bmod n$ 的值，其中 $1 \le n \le 10^{18}$

显然答案就是：
$$
(n-1)! \bmod n=
\begin{cases}
2 & n=4 \\
n-1 & n \in \mathbb{P} \\
0 & \text{otherwise}
\end{cases}
$$
于是问题就转化为了判断 $n$ 是否是素数

~~于是你可以用 米勒拉宾素数测试 来解决这道题了~~

然而由于出题人懒得造数据，实际上只需要判断 $2^{n-1}\bmod n$ 是不是 $1$ 即可通过本题

~~下面扯一扯证明~~

由 威尔逊定理 可得，$(n-1)! \equiv n-1 \pmod n$ 成立当且仅当 $n$ 是素数

考虑 $n$ 不是素数的情况

若 $n=p^2$，且 $p \in \mathbb{P}$，若存在 $1 \le 2p < n$，则 $(n-1)! \equiv 0 \pmod n$，即同余 $0$ 的充分条件是 $2 < \frac{n}{p} = \sqrt n$，可以得知，该等式不成立当且仅当 $n=4$

若 $n=pq$，且 $p \not= q$，则 $1 \le p < q < n$，于是 $(n-1) \equiv 0 \pmod n$

综上可得：

$$
(n-1)! \bmod n=
\begin{cases}
2 & n=4 \\
n-1 & n \in \mathbb{P} \\
0 & \text{otherwise}
\end{cases}
$$

9

给定一棵树，以及一共 $m$ 种颜色，你需要把每个点都染上色

有 $q$ 个约束，每个约束诸如限制从某个点到根这条路径上的颜色并中需要包含某个颜色

问有多少种染色方案，使得满足所有约束

$n \le 5000, m \le 10, q \le n \times m$

一开始想容斥去了……然后没搞出来……

实际上很简单……

设 $h_u$ 表示所有在 $u$ 处的约束的颜色并

设 $f_{u,S}$ 表示 $u$ 到根中不包括 $u$ 的点的颜色并的集合为 $S$ 的方案数，答案显然是 $f_{1,\emptyset}$

转移的话看一下 $\mid h_u-(h_u \cap S) \mid$ 是多少

如果是 $0$，那么当前点的颜色可以随意选

如果是 $1$，那么当前点的颜色只能唯一确定

如果是其它的话，那么当前无解

转移的话直接在树上跑记忆化搜索就行了

10

给定一个 $n \times n$ 的矩阵，保证每一行和每一列有且仅有一个点

求有多少个 $m \times m$ 的子矩阵，满足 $1 \le m \le n$，且该子矩阵中点的个数等于 $m$

$n \le 50000$

~~仔细理解完题意后会发现实际上读入了个排列，然后问有多少个值域连续的子段~~

论如何优化暴力

首先有三种暴力：

枚举左上角和右下角，然后判断这个矩形是否合法
发现必须是正方形，那么可以枚举边长然后再枚举左上角
然而还有另外一种暴力方法，即枚举矩形的上下边界，然后判断有多少个顶着上下边界的子矩形合法

显然前两种没啥用，不妨看看第三种

假设枚举上下边界为 $i,j$，由于要求子矩形是正方形，因此可以得知 $m=j-i+1$

由于每一行都有且仅有一个点，而且还要求子矩形里有 $m$ 个点，所以在这些行里的点都必须选上

考虑到正方形的边长都是 $m$，且每一列有且仅有一个点，因此要求这些点必须相邻要挨着

于是可以每读入 $(x,y)$，然后令 $a_x=y$

之后相当于查询有多少个 $(i,j)$ 满足 $i \le j$ 且 $j-i=(\text{max}{k=l}^{r}a_k)-(\text{min}{k=l}^{r}a_k)$

然后就是套路题了，考虑分治，假设现在要解决 $[l,r]$ 的答案，设 $mid=\lfloor\frac{l+r}{2}\rfloor$

对于 $[l,mid]$ 和 $[mid+1,r]$ 的答案，可以递归做下去，因此只需要考虑左端点在 $[l,mid]$ 且右端点在 $[mid+1,r]$ 的答案即可

一共就四种情况：

最大值在左侧，最小值在左侧
最大值在左侧，最小值在左侧
最大值在右侧，最小值在左侧
最大值在右侧，最小值在右侧

维护前后缀极值后扫一遍就行了

由于数据范围比较小，$O(n \log^2n)$ 都可以通过此题

11

给定一个素数 $p$，保证 $p \in [5,150]$

求任意一个 $2x > p$，使得 $p^{2x-1} \equiv 1 \pmod {2x}$ 成立

要求 $2x$ 的位数不超过 $300$ 位

~~出题人：我有个奇妙的构造方法，你一定想不出来~~

于是直接暴力就做完了……