牛客多校第一场

补题进度：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]$

确认无误：无签到