Wannafly挑战赛13 zzf的好矩阵 题解 答案解释
# Wannafly挑战赛13 zzf的好矩阵 题解
@[toc]
链接：[https://ac.nowcoder.com/acm/contest/80/C](https://ac.nowcoder.com/acm/contest/80/C)
## 分析
1. 每个格子都有至少一个麦穗
2. 每个格子最多只能有p*p个麦穗
3. 任意两个格子的麦穗数不同
### 结论1
**由以上三点易得所有格子的麦穗数为$p^2$的全排列。**
### 结论2
**对于一个已知的一个符合题意的矩阵，行任意交换，列任意交换，或者所有行列进行转置，所得的矩阵仍然是一个符合条件的解。易得，如此一个基本解可以构造出$2*(p!)^2$个互不相同的解。**
---
转置乘以2.行的顺序有$p!$种，列的顺序有$p!$种。
### 结论3
**不考虑转置、行列交换等变换，本质不同的解有且只有一个。**
以下主要是从不重不漏出发，逐步逼近，找到C(带子)需要满足的条件，最终确定可行的c与r.
---
用$r_i,c_j,a_{i,j}$分别表示第$i$行选中的次数、第$j$列选中的次数，$i$行$j$列的麦穗数。
$a_{i,j}=r_i+c_j$.
$r=(r_1,r_2,r_3,...,r_p)$
$c=(c_1,c_2,c_3,...,c_p)$.
对于麦穗数为1的格子，显然只能分解成$1+0$或者$0+1$.
为了本质不同的解，我们不妨设行和列的选取数从小到大，且第一列取1，第一行取0.即：
$$r_1 \lt r_2 \lt r_3 \lt ... \lt r_p;\\
c_1 \lt c_2 \lt c_3 \lt ... \lt c_p; \\
c_1 = 1,\;r_1=0.$$
如此，确定一对$r,c$就确定了一个基本的解。
**容易验证$c=\left(1,2,3,4,...,p\right), r=\left(0,p,2p,3p,...,(p-1)p\right)$是一个解。**
接下来要说明只有这一组基本解。
---
#### C数组对应带子说明
#### 空白长度论述
不断移动C数组锁画出的这条带子，注意需要满足以下两点要求：
1. $1\text{-}p^2$的中每一个格子都被黑色覆盖一次且仅一次（即不重不漏）。
2. $r_i$其实就是第$i$次移动相比于初始位置的总的位移量。
3. 为了不漏，移动之后，下一次带子的开头应对应于还没覆盖的第一个空白格子。
根据不重不漏，容易推出以下结论。
$l_{白}=kl$
#### 后续黑色长度论述
$l^{'}=l$
**并且用不重不漏容易推出如果后面还有白色段，则长度一定和前面的白色段等长，再有黑色段，则又和最开始的黑色段等长……**
#### 能“密铺”的带子形式及特征
共有$k_1$个`kl白+l黑`片段。
带子移动k次，加上原本的不移动的一条，则刚好**不重不漏**的“密铺”了连续的一段。之后只需要按照前面的整体右移即可。
下图是k=3的例子：
带子黑色总长度：
$$p=(k_1+1)l$$
“密铺”一段长度：
$$l+k_1(kl+l)+kl=k_1kl+(k+k_1+1)l$$
**由于$p$是素数。**
1. $k_1 = 0,l=p$,则带子只有第一块黑色的片段，长度为p，故$c=(1,2,3,...,p)$,显然要密铺满$1-p^2$可得$r=(0,p,2p,3p,...,(p-1)p)$.或者
2. $k_1 = p-1,l=1$,则带子有$p$块黑色的片段，每两个黑色片段之间有一块长度为$k$的白色片段。密铺总长度应该是$p^2$的因数。
$$p^2=k_2\left[k_1kl+(k+k_1+1)l\right]\\=k_2\left[(p-1)k+(k+p)\right]\\=k_2(k+1)p \Rightarrow\\
p=k_2(k+1)$$
故
2.a. $k_2=1,k=p-1$或
2.b. $k_2=p,k=0$
对于`2.a`可得$c=(1,p+1,2p+1,...,(p-1)p+1), r=(0,1,2,3,4,...,p-1)$
对于`2.b`可得$c=(1,2,3,4,...,p),r=(0,p,2p,3p,...,(p-1)p)$
综上`1`,`2.a`,`2.b`，
$$c_{\alpha}=(1,2,3,4,...,p),\;r_{\alpha}=(0,p,2p,3p,...,(p-1)p);\\
c_{\beta}=(1,p+1,2p+1,...,(p-1)p+1),\; r_{\beta}=(0,1,2,3,4,...,p-1)$$
但是，容易发现，$\forall i,j$,有
$$a_{\alpha,i,j}=r_{\alpha,i}+c_{\alpha,j}=[(i-1)p]+[j]=(i-1)p+j\\
=a_{\beta,j,i}=r_{\beta,j}+c_{\beta,i}=[j-1]+[(i-1)p+1]=(i-1)p+j$$
即$\alpha,\beta$这两种方案所得矩阵互为转置矩阵。所以应计算成一种基本解。
### 最终结论
**因此，本质不同的解只有一种；考虑矩阵转置、行列交换等，一共有$2*(p!)^2$种解。**
@[toc]
链接：[https://ac.nowcoder.com/acm/contest/80/C](https://ac.nowcoder.com/acm/contest/80/C)
## 分析
1. 每个格子都有至少一个麦穗
2. 每个格子最多只能有p*p个麦穗
3. 任意两个格子的麦穗数不同
### 结论1
**由以上三点易得所有格子的麦穗数为$p^2$的全排列。**
### 结论2
**对于一个已知的一个符合题意的矩阵，行任意交换，列任意交换，或者所有行列进行转置，所得的矩阵仍然是一个符合条件的解。易得，如此一个基本解可以构造出$2*(p!)^2$个互不相同的解。**
---
转置乘以2.行的顺序有$p!$种，列的顺序有$p!$种。
### 结论3
**不考虑转置、行列交换等变换，本质不同的解有且只有一个。**
以下主要是从不重不漏出发，逐步逼近，找到C(带子)需要满足的条件，最终确定可行的c与r.
---
用$r_i,c_j,a_{i,j}$分别表示第$i$行选中的次数、第$j$列选中的次数，$i$行$j$列的麦穗数。
$a_{i,j}=r_i+c_j$.
$r=(r_1,r_2,r_3,...,r_p)$
$c=(c_1,c_2,c_3,...,c_p)$.
对于麦穗数为1的格子，显然只能分解成$1+0$或者$0+1$.
为了本质不同的解，我们不妨设行和列的选取数从小到大，且第一列取1，第一行取0.即：
$$r_1 \lt r_2 \lt r_3 \lt ... \lt r_p;\\
c_1 \lt c_2 \lt c_3 \lt ... \lt c_p; \\
c_1 = 1,\;r_1=0.$$
如此，确定一对$r,c$就确定了一个基本的解。
**容易验证$c=\left(1,2,3,4,...,p\right), r=\left(0,p,2p,3p,...,(p-1)p\right)$是一个解。**
接下来要说明只有这一组基本解。
---
#### C数组对应带子说明
#### 空白长度论述
不断移动C数组锁画出的这条带子，注意需要满足以下两点要求：
1. $1\text{-}p^2$的中每一个格子都被黑色覆盖一次且仅一次（即不重不漏）。
2. $r_i$其实就是第$i$次移动相比于初始位置的总的位移量。
3. 为了不漏，移动之后，下一次带子的开头应对应于还没覆盖的第一个空白格子。
根据不重不漏，容易推出以下结论。
$l_{白}=kl$
#### 后续黑色长度论述
$l^{'}=l$
**并且用不重不漏容易推出如果后面还有白色段，则长度一定和前面的白色段等长，再有黑色段，则又和最开始的黑色段等长……**
#### 能“密铺”的带子形式及特征
共有$k_1$个`kl白+l黑`片段。
带子移动k次，加上原本的不移动的一条，则刚好**不重不漏**的“密铺”了连续的一段。之后只需要按照前面的整体右移即可。
下图是k=3的例子：
带子黑色总长度：
$$p=(k_1+1)l$$
“密铺”一段长度：
$$l+k_1(kl+l)+kl=k_1kl+(k+k_1+1)l$$
**由于$p$是素数。**
1. $k_1 = 0,l=p$,则带子只有第一块黑色的片段，长度为p，故$c=(1,2,3,...,p)$,显然要密铺满$1-p^2$可得$r=(0,p,2p,3p,...,(p-1)p)$.或者
2. $k_1 = p-1,l=1$,则带子有$p$块黑色的片段，每两个黑色片段之间有一块长度为$k$的白色片段。密铺总长度应该是$p^2$的因数。
$$p^2=k_2\left[k_1kl+(k+k_1+1)l\right]\\=k_2\left[(p-1)k+(k+p)\right]\\=k_2(k+1)p \Rightarrow\\
p=k_2(k+1)$$
故
2.a. $k_2=1,k=p-1$或
2.b. $k_2=p,k=0$
对于`2.a`可得$c=(1,p+1,2p+1,...,(p-1)p+1), r=(0,1,2,3,4,...,p-1)$
对于`2.b`可得$c=(1,2,3,4,...,p),r=(0,p,2p,3p,...,(p-1)p)$
综上`1`,`2.a`,`2.b`，
$$c_{\alpha}=(1,2,3,4,...,p),\;r_{\alpha}=(0,p,2p,3p,...,(p-1)p);\\
c_{\beta}=(1,p+1,2p+1,...,(p-1)p+1),\; r_{\beta}=(0,1,2,3,4,...,p-1)$$
但是，容易发现，$\forall i,j$,有
$$a_{\alpha,i,j}=r_{\alpha,i}+c_{\alpha,j}=[(i-1)p]+[j]=(i-1)p+j\\
=a_{\beta,j,i}=r_{\beta,j}+c_{\beta,i}=[j-1]+[(i-1)p+1]=(i-1)p+j$$
即$\alpha,\beta$这两种方案所得矩阵互为转置矩阵。所以应计算成一种基本解。
### 最终结论
**因此，本质不同的解只有一种；考虑矩阵转置、行列交换等，一共有$2*(p!)^2$种解。**
拼多多集团-PDD三面183人在聊