赤道上有逆时针排列的 n 座岛屿。给定其中一些岛屿的方位关系（东，西）。问满足这些条件的基础上，n 座岛屿之间的关系矩阵有多少种。（$1\le n\le 500$）
由于矩阵的反对称性，只考虑右上角的矩阵，对于第 $i$ 行，当第 $j$ 列为 W 时，其 $i+1\sim j$ 列都必须为 W，当第 $j$ 列为 E 时，其 $j\sim n$ 列都必须为 E，对于每行最早出现的 E 的列数必须是不严格递增的。特别地，对于第一行，当 E 第一次出现在第 $j$ 列时，$j\sim n$ 行都必须为 W。根据以上规则 DP 即可。
时间复杂度 $O(n^3)$

构造一个大小为 n · m 的二维网格，使其其中有 k 个 1，其余均为 0。并且该网格的每一行和每一列的和均为奇数。
将 $k$ 分别分解为 $n$ 个小于 $m$ 的奇数作为每行的 $1$ 的个数和 $m$ 个小于 $n$ 的奇数作为每列的 $1$ 的个数。当分解尽可能平均时可以最大可能的保证有解，当且仅当 $n,m$ 为奇数且 $k=nm-2$ 时无解。
ps:比赛时过了但结束后被自己用 3 3 7 给hack了。