[ARC208D] Symmetric Matrix 题解

· · 题解

前言

这或许是我目前离做出 AtCoder \color{Red}*3000 最近的一次。曾经在模拟赛里接触过完全图边染色，已经掌握完成本题所需要的所有知识，并且已经明确了思路，却没有在比赛有限的时间内写完。

过去已经凝固，我带着回忆向前。 谨以此题解纪念我 AtCoder 比赛生涯中的一次遗憾。

解法

提出一个与官方题解不同的思路。

前置知识：完全图边染色

判掉两个显然无解的情况：（1）Y 不是排列；（2）若存在 i 满足 Y_{Y_i}\ne i，那么最终的方阵不对称，直接输出 No。以下讨论不考虑这些情况。

先不考虑 Y_i 的限制。

观察到最终构造出的方阵是一个拉丁方（每行 / 列上的所有元素都不相同的方阵；“每列上的元素也不相同”是根据对称的性质得出的）。立即联想到 [SNOI2024] 拉丁方，虽然 SNOI 这题的二分图边染色的思路不太好拓展到本题（因为本题“对称”的条件比较棘手，二分图边染色不能处理这种“两条边颜色相同”的关系），但是这启发了一种新思路：“对称”的限制即为 A_{i,j}=A_{j,i}；如果按照二分图边染色的建图 i\leftrightarrow j+N 且使该边的颜色为 A_{i,j}，相当于就是限制 (i,j+N) 与 (j,i+N) 两条边颜色相等；那么忽略所有形如 (i,i+N) 的边后，是不是可以把这两条边“叠合”成同一条双向边 (i,j)？

答案是肯定的，这样的转换完美保留了拉丁方原有的所有性质，并且能够解决对称的限制。进一步发现这就是一个完全图边染色的问题：给定一个完全图 K_N，求出最少的颜色数 \chi'(K_N)（称为该图的“边色数”），使得可以给每条边染上一个 1\sim\chi'(K_N) 的颜色，满足对于所有结点 u 满足 u 的所有连边颜色不相同。

这个问题的解法可以参考文章开头给出的知乎回答链接（当然下文也同样会提到）。解决问题需要对完全图点数的奇偶性分类，接下来我们就来尝试对应地进行讨论。

N 为偶数

此时 K_N 的边色数 \chi'(K_N)=N-1。共有 \frac{N(N-1)}{2} 条边，一种颜色最多染 \frac{N}{2} 条，由鸽笼原理得至少需要 N-1 种颜色。以下提出一种构造，以证明边色数可以取到这个下界：把结点 1 取出，其他结点按照 2,3,\ldots,N-1,N 的顺序顺时针排列在结点 1 周围，形成一个正 N-1 边形，结点 1 为其中心。对于边 (1,i) 染上颜色 i-1，接下来将所有与 (1,i) 垂直的边染上颜色 i-1（换种说法就是维护两个指针 l,r，初始都为 i，接下来 l 每次往逆时针方向移动一步，r 同时往顺时针方向移动一步，移动完后将 (l,r) 染上颜色 i-1；重复此过程直到 l,r 再次相遇）。

前面忽略了 (i,i+N) 的情况（转换到现在的图上就是 (i,i)，可以理解为在完全图的基础上添加一些自环），现在开始处理它的问题。观察到还有一种颜色没用，直接把所有的自环染上剩下的那种颜色。

考虑 Y_i 的限制。不妨认为前面给完全图边染色的颜色值域为 [2,N]（即将上述完全图边染色中边的颜色编号全部 +1），剩下给自环染的颜色为 1。于是目前的方阵满足 A_{x,y}=1 当且仅当 x=y，注意到此时只需要对于第 i 行，交换 A_{i,i} 和 A_{i,Y_i} 即可满足 Y_i 的限制。此时每行的元素仍然互不相同，并且对称的性质得以保留（考虑一个限制 A_{x,y}=A_{y,x}=1，它们被换到正确的位置后显然对称，而与它们交换的元素最终被换到了正对角线上，不管是什么元素都不会影响对称性）。

N 为奇数

特判掉 N=1 的情况，以下只考虑 N\ge 3。

此时 K_N 的边色数 \chi'(K_N)=N。共有 \frac{N(N-1)}{2} 条边，一种颜色最多染 \frac{N-1}{2} 条，由鸽笼原理得至少需要 N 种颜色。构造只需要考虑对一个 N+1 个点的完全图进行边染色（即转换成偶数的情况），最后随便删一个点及与它相连的所有边即可。

为方便下文叙述，这里与 N 为偶数时的讨论略有差别——令结点 N+1 为多边形的中心而非结点 1（即多边形的顶点对应的结点顺时针方向为 1\sim N 而非 2\sim N+1），染色时令 (N+1,i) 的颜色为 i，然后使用和上面同样的方法，从 i 开始往两个方向绕着染色。染色完成后把结点 N+1 删除，删除完成后结点 i 就不存在相连的颜色为 i 的边了，故可以将自环 (i,i) 染成颜色 i。将此时对应构造出的方阵记为 B，B_{x,y}=1 当且仅当 x=y=1 或 x+y=N+2。

考虑 Y_i 的限制。发现 N 为偶数的“交换构造”策略不管用了，原因是颜色为 1 的元素初始时不一定在对角线上，直接交换可能破坏对称性。

尝试进一步考虑边染色的本质，能够得知除了结点 1 的那个自环之外，颜色为 1 的边构成了一个大小为 \frac{N-1}{2} 的匹配。又观察到如果不考虑 Y_i 的限制，每个位置确切地是哪个颜色其实并不重要；严谨地说，对于一种构造 A' 和一个 1\sim N 的排列 P'，将 A' 中的所有元素 A'_{i,j} 替换为 A'_{P'_i,P'_j} 后构造依然合法（相当于对行列编号同时进行了一个置换）。

上述的思考启发我们对行和列的编号进行置换，这样就能解决如下的情况：存在恰好一个满足 Y_j=j 的 j，剩下 N-1 个 i 均满足 Y_i\ne i。将那 N-1 个对称的限制转换成匹配（即令 Y_i 和 i 配对），令构成的匹配 M_1=\left\{(p_1,q_1),(p_2,q_2),\ldots,\left(p_{\frac{N-1}{2}},q_{\frac{N-1}{2}}\right)\right\}，同时令上文中完全图边染色时颜色为 1 的边对应的匹配 M_2=\left\{(2,N),(3,N-1),\ldots,\left(\frac{N+1}{2},\frac{N+3}{2}\right)\right\}（即满足 x+y=N+2 的 (x,y)），构造长度为 N 的排列 P 使得 P_j=1，并且让 M_1 和 M_2 下标相同的匹配中的元素在 P 中一一对应（即对于 (p_i,q_i) 和 (i+1,N-i+1)，有 P_{p_i}=i+1 和 P_{q_i}=N-i+1）。对 B 同时执行替换 B_{i,j}\gets B_{P_i,P_j}，得到的 B 就是最终的 A。

现在剩下一种情况不能处理：存在 >1 个满足 Y_j=j 的 j。我们断言这是无解的。证明考虑对于每种元素 c，由于 N 为奇数且方阵对称，故至少存在一个 i 使得 A_{i,i}=c，即每种元素都在对角线上出现至少一次，等价于 1 在对角线上出现最多一次，也就是满足 Y_j=j 的 j 必须有恰好一个，否则就是无解。

我们讨论完了所有的情况，直接对着模拟构造即可通过此题。时间复杂度 O(N^2)。

实现

代码中的数组是 0-indexed 的。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t; cin>>t;
  while(t--){
    int n; cin>>n;
    vector<int> a(n),ps(n);
    // a 数组对应文中的 Y 数组
    for(auto &i:a)cin>>i,i--;
    iota(ps.begin(),ps.end(),0);
    if(!is_permutation(a.begin(),a.end(),ps.begin())){
      cout<<"No\n"; continue;
    } // 如果不是排列无解
    bool f=true;
    int c=0;
    for(int i=0;i<n;i++)
      f&=a[a[i]]==i,c+=i==a[i];
    if(!f){cout<<"No\n"; continue;} // 存在 Y[i]!=i，无解
    vector w(n,vector<int>(n));
    if(!(n&1)){
      for(int i=0;i<n-1;i++){
        w[0][i+1]=w[i+1][0]=i+1;
        for(int l=(i+(n-1)-1)%(n-1),r=(i+1)%(n-1),c=0;c<n-2>>1;l=(l+n-2)%(n-1),r=(r+1)%(n-1),c++)
          w[l+1][r+1]=w[r+1][l+1]=i+1;
      } // 完全图边染色
      for(int i=0;i<n;i++)
        if(w[i][a[i]])swap(w[i][a[i]],w[i][i]); // 交换构造
    } // 偶数的构造
    else{
      if(c>1){cout<<"No\n"; continue;} // 多于一个 Y[i]=i，无解
      vector wp(n,vector<int>(n));
      for(int i=0;i<n;i++)
        for(int l=i,r=i,c=0;c<n+1>>1;l=(l+n-1)%n,r=(r+1)%n,c++)
          wp[l][r]=wp[r][l]=i;
          //  略有修改的完全图边染色
      vector<int> v1,v2;
      for(int i=0;i<n;i++)
        if(i==a[i])v1.emplace_back(i);
      for(int i=0;i<n;i++)
        if(i<a[i]){
          v1.emplace_back(i);
          v1.emplace_back(a[i]);
        } // 求匹配 M1
      for(int l=0,r=0,c=0;c<n+1>>1;l=(l+n-1)%n,r=(r+1)%n,c++){
        v2.emplace_back(l);
        if(l!=r)v2.emplace_back(r);
      } // 求匹配 M2
      vector<int> p(n);
      for(int i=0;i<n;i++)
        p[v1[i]]=v2[i];
      for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
          w[i][j]=wp[p[i]][p[j]]; // 替换操作
    } // 奇数的构造
    cout<<"Yes\n";
    for(auto i:w){
      for(int j:i)cout<<j+1<<' ';
      cout<<'\n';
    }
  }
  return 0;
}