有一个
n
×
n
n\times n
n×n 的网格，每个格子有一个
{
−
1
,
0
,
1
}
\{-1,0,1\}
{−1,0,1} 之间的数
对于每行每列的和共
2
×
n
2\times n
2×n 个，要求这
2
×
n
2\times n
2×n 个数互不相同
若存在一种合法的填法，则称
n
n
n 是好的，问好的
n
n
n 有哪些？
加强：给定
n
n
n，问合法的填法有多少种
解：
- 首先注意到交换两行或两列并没有影响
于是我们可以将行和列都按大小排好序，设每个格子的数为 x i , j x_{i,j} xi,j
那么就是要求 x i , j ≥ x i , j + 1 , x i , j ≥ x i + 1 , j x_{i,j}\ge x_{i,j+1},x_{i,j}\ge x_{i+1,j} xi,j≥xi,j+1,xi,j≥xi+1,j，即将网格变成如下的形式
- 第二个观察是行和列的和都
∈
[
−
n
,
n
]
\in [-n,n]
∈[−n,n] 共
2
n
+
1
2n+1
2n+1 个数
也就是说只有一个数是不存在与这些和中的
有结论：对于 2 ∣ n 2\mid n 2∣n， n n n 为好的，否则 n n n 不是好的，证明如下 - 充分性：我们直接给出如下构造（下面是
n
=
6
n=6
n=6 的构造）
对于行，表示出 [ − n + 1 , − n / 2 ] ∪ [ n / 2 + 1 , n ] [-n+1,-n/2]\cup [n/2+1,n] [−n+1,−n/2]∪[n/2+1,n] 的数
对于列正好为 [ − n / 2 + 1 , n / 2 ] [-n/2+1,n/2] [−n/2+1,n/2] 的所有数
对于前 n / 2 n/2 n/2 行中的第 i i i 行，每行的前 n − i + 1 n-i+1 n−i+1 个数为 1 1 1，后面的为 0 0 0
对于后 n / 2 n/2 n/2 行中的第 i i i 行，每行的后 i − 1 i-1 i−1 个为 − 1 -1 −1，前面的为 0 0 0 - 必要性：为了证明必要性，我们先证一个引理：
最后的值域只能为 [ − n , n − 1 ] , [ − n + 1 , n ] [-n,n-1],[-n+1,n] [−n,n−1],[−n+1,n] 中的一种
我们从上面的构造开始调整，首先第一个位置只能调整 − n + 1 -n+1 −n+1 那一排，这必定为造成一列有 t 0 t_0 t0 变为 t 0 − 1 t_0-1 t0−1，于是我们会接着调整 t 0 − 1 t_0-1 t0−1 的那一排或一列，这必然会导致令一列或一排由 t 1 t_1 t1 变为 t 1 − 1 t_1-1 t1−1，调整会一直进行指导 t k = t 0 t_k=t_0 tk=t0，而这个时候会变成值域为 [ − n , n − 1 ] [-n,n-1] [−n,n−1] 的情况
即每行的和为 x i x_i xi，列的和为 y j y_j yj，那么有 ∑ x i = ∑ y j \sum x_i=\sum y_j ∑xi=∑yj，而 ∑ x i + ∑ y j = n \sum x_i+\sum y_j=n ∑xi+∑yj=n
故有 ∑ x i = n 2 \sum x_i=\frac n2 ∑xi=2n，所以 2 ∣ n 2\mid n 2∣n 是必要的 - 探究更多性质可以发现，只要能将
[
−
n
+
1
,
n
]
[-n+1,n]
[−n+1,n] 的数划分成两个大小为
n
n
n 的集合，使得和为
n
2
\frac n2
2n
那么这种方案就是合法的，而对于一个合法的 “标准方案”，任何一个行列置换都会到一个本质不同的情况，所以方案数就是标准方案数 w a y s × 2 × n ! 2 ways\times 2\times n!^2 ways×2×n!2
对于 w a y s ways ways，即计算 [ x n 2 y n ] ∏ i = − n + 1 n ( 1 + x i y ) = [ x n 2 + n ( n − 1 ) y n ] ∏ i = 0 2 n − 1 ( 1 + x i y ) [x^{\frac n2}y^n]\prod_{i=-n+1}^n(1+x^iy)=[x^{\frac n2+n(n-1)}y^n]\prod_{i=0}^{2n-1}(1+x^iy) [x2nyn]∏i=−n+1n(1+xiy)=[x2n+n(n−1)yn]∏i=02n−1(1+xiy)
用多项式技巧可以做到 O ( n 3 log n ) \mathcal{O}(n^3\log n) O(n3logn)，有更好的做法请不吝赐教