前几天vp subregional看到这样一个题，写了写发现和正解不一样，也不会证自己的做法的正确性

听说是错的

题目大意

给一个 $W\times H$ 的矩形，划分成尽量少的整边长正方形，输出方案

$1\le W,H\le 60$

错误做法

猜想一定存在一条分割线贯穿矩形，使得矩形分成两半，并且两半的最优解拼起来就是整个矩形的最优解，然后随便dp

Hack

AAAAAAAABBBBBBBBBBB      AAAAAAAAABBBBBBBBBB
AAAAAAAABBBBBBBBBBB      AAAAAAAAABBBBBBBBBB
AAAAAAAABBBBBBBBBBB      AAAAAAAAABBBBBBBBBB
AAAAAAAABBBBBBBBBBB      AAAAAAAAABBBBBBBBBB
AAAAAAAABBBBBBBBBBB      AAAAAAAAABBBBBBBBBB
AAAAAAAABBBBBBBBBBB      AAAAAAAAABBBBBBBBBB
AAAAAAAABBBBBBBBBBB      AAAAAAAAABBBBBBBBBB
AAAAAAAABBBBBBBBBBB      AAAAAAAAABBBBBBBBBB
BBBBBCCCBBBBBBBBBBB  vs  AAAAAAAAABBBBBBBBBB
BBBBBCCCBBBBBBBBBBB      CCCCCCCCCBBBBBBBBBB
BBBBBCCCBBBBBBBBBBB      CCCCCCCCCAAAAAAAACC
BBBBBAAAAAAACCCCCCC      CCCCCCCCCAAAAAAAACC
BBBBBAAAAAAACCCCCCC      CCCCCCCCCAAAAAAAABB
CCCCCAAAAAAACCCCCCC      CCCCCCCCCAAAAAAAABB
CCCCCAAAAAAACCCCCCC      CCCCCCCCCAAAAAAAACC
CCCCCAAAAAAACCCCCCC      CCCCCCCCCAAAAAAAACC
CCCCCAAAAAAACCCCCCC      CCCCCCCCCAAAAAAAABB
CCCCCAAAAAAACCCCCCC      CCCCCCCCCAAAAAAAABB
      total=7                  total=8

这两个平面图的色数都是3，很有趣（被打

乱搞做法

根据以上反例猜想dp的每一个状态要么是一个矩形，要么是一个矩形抠掉一个角上的另一个矩形（称为L形）

矩形状态枚举抠掉哪个正方形转移，共$O(n)$种转移，$O(n^2)$种状态

L形状态共有5对关于$y=x$对称的转移共10种，共$O(1)$种转移，$O(n^4)$种状态

1.贴小矩形的右边界 （X是抠掉的位置，O是新放置的正方形，下同）

XXXX.....
XXXX.....
XXXX.....
XXXX.....
XXXX.....
XXXX.....
OOOO.....
OOOO.....
OOOO.....
OOOO.....
.........
.........

2.贴大矩形的左边界，右边界不到小矩形右边界

XXXX.....
XXXX.....
XXXX.....
XXXX.....
XXXX.....
XXXX.....
OOO......
OOO......
OOO......

3.贴大矩形的左边界，同时右边界贴小矩形右边界

XXXX.....
XXXX.....
XXXX.....
XXXX.....
XXXX.....
XXXX.....
OOOO.....
OOOO.....
OOOO.....
OOOO.....

4.贴大矩形的左边界，右边界超出小矩形右边界

XXXX.....
XXXX.....
XXXX.....
XXXX.....
XXXX.....
XXXX.....
OOOOO....
OOOOO....
OOOOO....
OOOOO....
OOOOO....

（此时转移到整个矩形上下翻转后的情况）

5.贴大矩形的左边界，同时右边界贴大矩形右边界

XXXX.....
XXXX.....
XXXX.....
XXXX.....
XXXX.....
XXXX.....
OOOOOOOOO
OOOOOOOOO
OOOOOOOOO
OOOOOOOOO
OOOOOOOOO
OOOOOOOOO
OOOOOOOOO
OOOOOOOOO
OOOOOOOOO

6~10是对称的，略

可以发现每种情况要么大矩形边界缩小，要么小矩形边界扩大，所以可以 $O(n^4)$ dp

代码在此，可以下载下来hack

std

看不懂俄文，机翻了一下好像是说什么枚举杨表然后本地打表，反正看起来就不怎么多项式

之前做魔法森林,提交了一个看起来错误的代码，发现通过了就没再管

后来再做别的LCT题时发现新写的代码和之前的代码不一样

唯一不同的函数——cut函数分别为

inline void cut(node *x,node *y)
{
    mkr(x);
    access(y);
    x->pa->rson=0;//老代码
    x->pa=0;
}

和

inline void cut(node *x,node *y)
{
    mkr(x);
    access(y);
    x->pa->lson=0;//新代码
    x->pa=0;
}

提交记录如下

1.老代码

2.新代码

后来我又尝试把这行不同的代码去掉

还是过了

3.修改后的代码

有没有路过的好心人帮忙解释一下这个代码为什么对，或者为什么错吗？

如果能hack掉那当然是坠吼的

upd1:相同方式修改cut函数后去交动态图连通性仍然是三种都能过

upd2:已解决，感谢各位神犇

题目描述

一个 $n$ 个点构成的竞赛图中最多能有多少条哈密顿路径？

$n$ 最多能做到多大？

样例输入

 4

样例输出

 5

样例解释

 边的朝向分别为
 1->2
 2->3
 3->4
 4->1
 1->3
 2->4
 时

 哈密顿路径分别为
 1->2->3->4
 2->3->4->1
 3->4->1->2
 4->1->2->3
 2->4->1->3

 共5条

 P.S.经过爆搜发现n=1~9时答案分别为1,1,3,5,15,45,189,661,3357