开始停课了 (喜.

并且发现最近写点什么都要像老妈子一样在开头絮絮叨叨 (大悲.

fill

$n\times n,n\le10^6$ 的白色网格图, 选 $m\le10^7$ 个格子涂黑, 使最终得到的图形关于两条对角线对称, 且旋转 $90^\circ$ 后不变.$t\le20$ 询问, 问方案数 $\bmod10^9+7$.

组合数搞一下, 首先判无解.$n\bmod2=0$ 时答案是

$$ \sum_{i=0}^{\frac m8}\binom{\frac{n\times(n-2)}8}i\binom{\frac n2}{\lfloor\frac m4-2i\rfloor} $$

$n\bmod2=1$ 时答案是

$$ \sum_{i=0}^{\lfloor\frac m8\rfloor}\binom{\lfloor\frac{n\times(n-2)}8\rfloor}i\binom{n-1}{\lfloor\frac m4-2i\rfloor} $$

另外这个柿子是现场手写的所以出锅是正常现象.$n$ 比较大所以组合数需要边走边算.

matrix

$n\times m$ 带权矩阵 $M$, 求一个权值和最大子矩阵 $(l,u,r,d)$ 满足

$$ \forall l<i<r,u<j<d,{\max\{M_{i-1,j},M_{i+1,j}\}<M_{i,j}<\min\{M_{i,j-1},M_{i,j+1}\}~\text{or}~\\ \min\{M_{i-1,j},M_{i+1,j}\}>M_{i,j}>\max\{M_{i,j-1},M_{i,j+1}\} } $$

首先易证 $r-l=2~\text{or}~d-u=2$(即符合要求的子矩阵一边长为 $3$). 每 $3$ 行或列压到一起做最大子段和,$\mathrm O(n^2)$.

minmex

$n,q\le5\times10^5,m\le10^6$.

有结论 $\operatorname{val}(u)=\operatorname{mex}(c),c\in\text{all}~P_{1\to u}$. 证明显然.

然后先建出最短路 DAG, 再对 DAG 建出支配树. 对于节点 $u$, 所有其子树中的 $v$ 都有 $\operatorname{val}(v)\not=c_u$. 转化为 DFS 序用线段树维护 值域区间 , 查询时在线段树上二分.

square

$n$ 个正方形, 第 $i$ 个下角在 $(i,0)$, 边长为 $i$ 的约数数量, 边与坐标轴平行. 问总覆盖面积.

屑题. 分段打表.