A. Monotonic Matrix

给定\(1\leq m,n \leq 1000\)，求满足下列条件的\(m \times n\)矩阵个数，使得

• \(a_{i,j} \in \{0, 1, 2\}\)
• 每一行从左到右和每一列从上到下单调不减

题解：考虑每一行大于等于1和大于等于2的位置，其实就是要求两个单调不减的数列\(\{a_i\}, \{b_i\}\)的个数，满足对于任意\(i\)，有\(a_i \leq b_i\)。

B. Symmetric Matrix

给定\(1 \leq n \leq 10^5\)，求满足每个元素为非负整数，主对角线全0，每一行和为2的\(n \times n\)的对称矩阵的数量。

题解：把矩阵想象成邻接矩阵，就是要求顶点带标号的所有不允许自环、但允许重边的2-正则图的数量。

C. Fluorescent 2

在模2域下，给定\(m \times n\)的01矩阵\(M\)，\(1 \leq n \leq 50\)，\(1 \leq m \leq 1000\)，求对于每一个\(n\)维向量\(v\)，\(Mv\)中0的个数的三次方的和。

D. Two Graphs

给定图\(G_1 = (V, E_1), G_2 = (V, E_2)\)，求有多少\(E_1\)的子集\(E’\)，使得\((V, E’)\)与\(G_2\)同构。点数不超过8。

题解：枚举所有的排列，如果构成子图，就把选出来的边用bitmap表示出来，最后去重即可。

E. Removal

给定\(1 \leq n \leq 10^5\)个数的序列，每个数为不超过\(k\)的正整数。问删掉\(m\)个数后，有多少种不同的子序列。\(k, m\)不超过10。

题解：用dp[i][j][k]表示前i个数删去j个数后，最后一个数为k的方案数。可以在\(O(1)\)时间内转移。

F. Sum of Maximum

给定数列\(a_1, a_2, \cdots, a_n\)，求

\[\sum_{x_1=1}^{a_1} \sum_{x_2=1}^{a_1} \cdots \sum_{x_n=1}^{a_n} \max\{x_1, x_2, \cdots, x_n\}\]

题解：把\(\max\{x_1, x_2, \cdots, x_n\}\)写为\(\sum_{m=1}^a [\exists i, x_i \geq m]\)，进而改写为\(\sum_{m=1}^a 1-[\forall i, x_i < m]\)。将\(a_i\)排序后，从大到小分段计算，每一段都是\(x_i\)的一个前缀积乘以\(i^k\)的求和，后者可用Lagrange插值法快速计算。

G. Steiner Tree

H. Longest Path

I. Substring

给一个字符集为{a,b,c}的字符串，求在同构意义下的子串的等价类的数目。两个串同构当且仅当长度相等，并且存在字符集到字符集的双射f，使得一个串经过f变换后变成另一个串。

题解：将原串经过6种双射f后变成的6个串丢到SAM里，求出所有本质不同的子串。含有大于等于2种子串有6中不同的同构串，而只含有1种字符的串只有3中不同的同构串，分类讨论一下即可。

J. Different Integers

给一个序列，每次询问给出一个区间，求序列扣除这个区间后，有多少个不同数。

题解：在某次询问中，某数不出现当且仅当这个数第一次出现到最后一次出现包含于询问区间中即可。只要离线排序一下，按右端点的顺序处理即可。