题解：P7886 「MCOI-06」Gerrymandering

由题意可知，假设对于一个 $n \times m$ 的表格，我们用了 $p$ 种颜色去染色，显然有 $n \times m = p \times k$。移项可知，$p = n \times m \div k$。又因为 $p$ 是整数，所以需要满足 $(n \times m) \bmod k = 0$ 时才有解。

那么对于一张存在解的表格，可以考虑蛇形方阵式的染色。从左上角开始染色，然后向右直到染色至边界，然后向下，再向左至边界……以此类推，直到染完为止。为了放置爆空间，本题解选择逐行输出答案（当然也可以使用 vector）。

最后核心代码如下：

while (no <= num)
{
    ++cnt;
    if (ty == 1)//从左往右
    {
        if (dx <= m) ans[dx] = no,++dx;
        else//整一行已经染色完毕
        {
            for (int i = 1;i <= m;++i) printf ("%d ",ans[i]),ans[i] = 0;
            puts ("");
            ty = 2;dx = m;
            ans[dx] = no;--dx;
        }
    }
    else if (ty == 2)//从右往左
    {
        if (dx >= 1) ans[dx] = no,--dx;
        else
        {
            for (int i = 1;i <= m;++i) printf ("%d ",ans[i]),ans[i] = 0;
            puts ("");
            ty = 1;dx = 1;ans[dx] = no;++dx;
        }
    }
    if (cnt % k == 0) ++no;//一种颜色的连通块大小为 k
}
for (int i = 1;i <= m;++i) printf ("%d ",ans[i]);//最后一行
puts ("");