题目描述
企鹅国的网吧们之间由网线互相连接，形成一棵树的结构。现在由于冬天到了，供暖部门缺少燃料，于是他们决定去拆一些网线来做燃料。但是现在有 K 只企鹅要上网和别人联机游戏，所以他们需要把这 K 只企鹅安排到不同的机房（两只企鹅在同一个机房会吵架），然后拆掉一些网线，但是需要保证每只企鹅至少还能通过留下来的网线和至少另一只企鹅联机游戏。
所以他们想知道，最少需要保留多少根网线？

从叶子节点往上贪心

用$sum\left [ i \right ]\left [ j \right ]$，记录第i 行，前j 个的和
枚举i ,j 两列$\left ( i<j \right ) ​$，用数组$c\left [ k \right ] ​$记录$sum\left [ k \right ]\left [j \right ]-sum\left [ k \right ]\left [ i-1 \right ] ​$
对于c 求一遍前缀和记为s，当且仅当$s\left [ i -1\right ]\equiv s\left [ j \right ]\left ( mod \ M \right )$，$\left [ i,j \right ]mod\ M=0$
用$cnt\left [ p \right ]$记录$s\equiv p\left ( mod \ M \right )$的个数，从左往右扫一遍
要注意的是$cnt\left [ 0 \right ]=1$
但是以上操作没有考虑仅一列的情况，枚举每一列再重复一遍以上操作

对于一组$gcd(x,y)=1$，若有一个质数p，则$gcd(xp,yp)=p$
枚举所有的p，求所有$xp<=n$，$yp<=n$的解，用欧拉函数即可

直接搜索加剪枝
剪枝可以考虑Cantor 展开，也可以直接用map

神奇的贪心

从大到小取$a_{i}$
因此对于每个$a_{i}$，若最终答案不包含$a_{i}$，则一定包含$a_{i-1}+a_{i+1}$
于是每次取$a_{i}$时，加入$a_{i-1}+a_{i+1}-a_{i}$，允许撤销操作

当且仅当$\left ( a_{1} \right ) xor\left ( a_{2}\right ) ...\left ( a_{n} \right )=0$为一个P

1. 最终状态为0
2. 对于一个$\left ( a_{1} \right ) xor\left ( a_{2}\right ) ...\left ( a_{n} \right )=k\left ( k>0 \right )$ 的状态，必存在一个$a_{i}>k$，使得下一步$\left ( a_{1} \right ) xor\left ( a_{2}\right ) ...\left ( a_{n} \right )=0$
3. 对于一个$\left ( a_{1} \right ) xor\left ( a_{2}\right ) ...\left ( a_{n} \right )=0$，不存在一种方案使得下一步$\left ( a_{1} \right ) xor\left ( a_{2}\right ) ...\left ( a_{n} \right )=k\left ( k>0 \right )$

通过观察可以发现点在%3意义下相同
直接暴力搜索加剪枝
但是要注意棋盘大小，棋盘小有些点跳不过去。
代码没有考虑棋盘大小，有部分点会WA

首先要有个妹子

问题描述：
今天CZY又找到了三个妹子，有着收藏爱好的他想要找三个地方将妹子们藏起来，将一片空地抽象成一个R行C列的表格，CZY要选出3个单元格。但要满足如下的两个条件：
（1）任意两个单元格都不在同一行。
（2）任意两个单元格都不在同一列。
选取格子存在一个花费，而这个花费是三个格子两两之间曼哈顿距离的和（如$\left ( x_{1},y_{1} \right )$和$\left ( x_{2},y_{2} \right )$的曼哈顿距离为$\left | x_{1}-x_{2} \right |+\left | y_{1}-y_{2} \right |$）。狗狗想知道的是，花费在minT 到maxT 之间的方案数有多少。
答案模1000000007。所谓的两种不同方案是指：只要它选中的单元格有一个不同，就认为是不同的方案。

通过观察，不难发现在一个$R*C$的矩阵中，所有最大的三个单元格曼哈顿距离相等，均为$2(R+C)-4$
通过简单地分析可以得出，在$R*C$的矩阵中，共有$6（R-2)(C-2)$组最大的三个单元格
代码就很简单了

预处理一行所有可能的情况
用$dp\left [d \right ]\left [ i\right ]\left [ k \right ]$数组记录第d行，当前状态为$s\left [ i \right ]$，总共放置k个的方案数
复杂度$O\left ( nk4^{n} \right )$

裸的二分，复杂度$O\left ( nlog^{2}n \right )$