f 记录第i 个点，访问j 条边，且返回i 点，经过的最大格点数量
g 则记录不返回的

$$f\left[i\right]\left[j\right]=max\left\{ f\left[i\right]\left[k\right]+f\left[to\right]\left[j-k-2\right]\right\}\left ( to\in i_{son} \right )$$

不在该子节点一去不回头

$$g\left[i\right]\left[j\right]=max\left\{ g\left[i\right]\left[k\right]+f\left[to\right]\left[j-k-2\right]\right\}\left ( to\in i_{son} \right )$$

在该子节点一去不回头

$$g\left[i\right]\left[j\right]=max\left\{ f\left[i\right]\left[k\right]+g\left[to\right]\left[j-k-1\right]\right\}\left ( to\in i_{son} \right )$$

设$N=\prod p_{i}^{a_{i}}$
则N 的约数个数为$\prod \left( a_{i}+1 \right)$
题目中n 最大值为50000，因此N 的质因子不超过16个
为了方便保存状态用了dfs
当然搜索不可能用高精度，于是取对数保存

对于图上所有的棋盘一定属于以下两种类型：

• 黑格行列奇偶性相同，白格不同

• 白格行列奇偶性相同，黑格不同

分两类讨论
每次翻转一部分棋盘的颜色
然后问题就变成了求全1 的最大正方形和最大矩形
参考洛谷P1736 创意吃鱼法，洛谷P4147-玉蟾宫

对于每个元素
预处理出其左端和上方最近的1 的位置，分别记为L 和U

$$dp\left [i \right ]\left [j \right ]=max\left (dp\left [i-1 \right ]\left [ j-1 \right ],L\left [i \right ]\left [ j-1 \right ],U\left [i-1 \right ]\left [j \right ] \right )+1 \left ( w\left [i \right ]\left [j \right ]=1\right)$$

水平翻转矩阵后再求一次

首先预处理出f 数组为当前位置向左延伸的最大长度
然后枚举每一列做一遍最大子矩形面积

经典题目
这里简要的总结一下它的四种做法
最大子矩阵有四种做法，你知道吗

• 单调栈
  维护一个单调递增的栈
  栈中保存一个二元组$\left ( height,sz \right )$，分别为高度和能覆盖到的宽度
  一个元素只会在超过它能覆盖的最大宽度后退栈
  此时更新答案即可

• 笛卡尔树
  笛卡尔树的定义这里就不赘述了
  如果有一棵以高度为权值构造好的笛卡尔树
  只需一遍dfs 即可得出答案
  用单调栈可在$O\left ( N\right )$时间内建树
  维护一个单调递增的栈
  对于新加入的元素x ，将最后一个退栈元素作为其左儿子，将其作为栈中top 元素的右儿子

• 并查集
  一种看似暴力的做法
  实际上复杂度应该是$O\left ( N\right )$
  具体看代码实现
  其中L 为当前位置向左能延伸的最大位置，R 为向右的

• 倍增
  对于一个区间
  找到其最小值所在位置
  可将其分为左右两个区间递归处理，且互不影响
  倍增数组维护最小值和最小值位置即可
  倍增代码就不放了

代码依次给出

观察到m 比较小，考虑状压m
对于当前状态s
当s‘ 去掉末尾位和s 去掉开头位相等，且s‘ 中个数<=k

$$dp\left [i \right ]\left [s’ \right ]+=dp\left [i-1 \right ]\left [ s \right ]$$

然而问题没有这么简单，花园是个环
设开头m 个状态为s ，则 $dp\left [n+m \right ]\left [s\right ]$为以s 开头的答案
因此枚举开头所有状态即可，这样就有80分了

对于最后20分
首先观察转移
设当s 可以转移到s’ 时，$f\left [s \right ]\left [s’ \right ]=1$

$$dp\left [i \right ]\left [s’ \right ]=\sum dp\left [i-1 \right ]\left [ s \right ]* f\left [s \right ]\left [ s' \right ]$$

与矩阵乘法一致
因此

$$dp\left [ n+m \right ]\left [ s \right ]=dp\left [ m \right ]\left [ s \right ]*F^{n}$$

挺有难度的一道题，参考了一下大佬的题解

对于一个联通块

1. 若无割点，则它与外界完全隔离，需要建两个出口以防一个出口被炸
2. 若只有一个割点，还需要在非割点节点再建一个出口以防割点被炸
3. 若有两个或以上割点，就不用担心了

每行每列最多放两个
dp 数组记录第i 行，有j 列放了1个，k 列放了2个的方案数
不放

$$dp\left [i \right ]\left [ j \right ]\left [k \right ]+=dp\left [i-1 \right ]\left [ j \right ]\left [k \right ]$$

放一个

$$dp\left [i\right ]\left [ j+1 \right ]\left [k \right ]+=dp\left [i-1 \right ]\left [ j \right ]\left [k \right ]*(m-j-k)(m-j-k>0)$$ $$dp\left [i \right ]\left [ j \right ]\left [k +1 \right ]+=dp\left [i -1\right ]\left [ j \right ]\left [k \right ]*j(j>0)$$

放两个

$$dp\left [i \right ]\left [ j -2\right ]\left [k +2 \right ]+=dp\left [i-1 \right ]\left [ j \right ]\left [k \right ]*C_{j}^{2}(j\geq 2)$$ $$dp\left [i \right ]\left [ j +2\right ]\left [k \right ]+=dp\left [i-1 \right ]\left [ j \right ]\left [k \right ]*C_{m-j-k}^{2}(m-j-k\geq 2)$$ $$dp\left [i \right ]\left [ j \right ]\left [k +1\right ]+=dp\left [i-1 \right ]\left [ j \right ]\left [k \right ]*(m-j-k)*j(j>0,m-j-k>0)$$

缩点时在新节点中保存最小花费和最小编号即可