补题进度：4/7(10)
$The$ $end$ $always$ $near$
A.Monotonic Matrix
题意
$n*m$ 的矩阵，每个数 $0<=a_i<=2$， 问满足 $ a_{i,j} <= a_{i+1,j}$ AND $ a_{i,j} <= a_{i,j+1}$ 的矩阵数量
题解
假如只有01，考虑01分界线的位置(分界线上的格子只能填0，下面只能填1)，答案即为：
$$
C_{n+m}^{m}
$$
现在考虑012三个数字，考虑01和12分界线，
其实是(0,0)到(n,m)的两条不相交(可重合)路径数量
Lindström–Gessel–Viennot lemma
由于分界线的起点和终点不能 在同一行和同一列， 可以将01的分界线分别在xy方向都移动一格即可
B. Symmetric Matrix
题意
$n*n$ 的矩阵 矩阵每行的和必须为2 且是一个沿右对角线对称的矩阵 并且 $a_{i,i}=0$ 问合法矩阵数量 ($0<=a_i<=2$)。
题解
待补
C.Fluorescent 2
留坑
D.Two Graphs
题解
赛时想了个从E2中选出E1条边，再和G1去匹配，很难写
正解：直接枚举G2的点n!种排列方式，暴力的和G1的中每个点的边的情况进行匹配，但存在一个问题: 一个图的遍历顺序不同，但是同构的，故要求出E1的所有同构
相当于G2中所有满足要求的都 $*$ 了一个 E1的所有同构, 排除即可
时间复杂度$O(n!*n^2)$
E.Removal
题意
长度为n的序列，每个数 <= k， 删除m个后，序列的种数(k<=10)
题解
法一：
法二：
定义：$dp_{ij}$：前i个删除j个的方案数
转移：$dp_{i,j}=dp_{i-1,j-1}+dp_{i-1,j}-以a_i 结尾相同的方案$
设以a_i 结尾相同的方案：
$$
ans[i]=dp_{pre[i]-1,j-(i-pre[i])}
$$
其中 $pre_i$:位置i的 $a_i$上次出现的位置。
$Thick: $ 多个位置有相同的$a_i$，每个位置都处理了它的前一个位置
pre[i]就是上一个a[i]出现位置,d是当前a[i]和前一个a[i]之间的距离。我们把他俩之间的全删掉才能保证串是重复的。j-d就是我们删掉他们之间所有所有字符后还剩下几次操作次数。
F.Sum of Maximum
题意
给一个序列 $a$， 问
$$
\sum_{x_1=1}^{a_1}\sum_{x_2=1}^{a_2}…\sum_{x_n=1}^{a_n} max(x_1, x_2,….,x_n)
$$
$$
mod (10^9+7)
$$
题解
拉格朗日插值
待补
G. Steiner Tree
题意
留坑
H. Longest Path
留坑
I. Different Integers
题意
题解
待补
J. Different Integers
题解
赛时写了个复杂度不对的莫队，侥幸过了题
正解：树状数组
要是一个区间的话怎么做？
将数组长度n扩展到2n即可转化为一个区间
$$
count(i,j)=[1,i]+[j,n] => [j,n+i]
$$
设$pre[]:$ 表示出现不同的数的前缀和
$$
answer=pre[r]-pre[l-1]+([1,l-1]和[l,r]都出现的数)
$$
问题转化为：如何求($[1,l-1]和[l,r]$都出现的数）
设树状数组中的 $C_i$ 为：第i个位置的数字是否在[1,i]出现过,这就需要维护一个nxt数组了表示每个位置的数出现的下一个位置
则 $[1,l-1]和[l,r]$都出现的数 $= sum[r]-sum[l-1]$
确认无误：无签到