题解：P12676 相等排列（equal）

fish_love_cat · 2025-08-07 18:46:34 · 题解

简单构造题。

首先偶数个排列显然可以 S 形构造。

奇数个排列时，如果长度是偶数，每一个数的下标和显然不是整数，于是无解。

于是只剩长度奇数的情况。

先考虑三个排列的构造。

不妨将第一个升序排序。

注意到每个下标的加和为 3\times\frac{(1+m)}{2}，然后第一个和第二个排列造成的贡献要刚好落满 [3\times\frac{(1+m)}{2}-m,3\times\frac{(1+m)}{2}-1]。

容易想到这么一个构造，在前两个排列搞出 (1,m),(2,m-2),(3,m-4),\dots,(k,m-2k),(k+1,2m-2(k+1)),\dots,(k+d,2m-2k-2d) 这样的对，然后根据这个填第三个排列。

由于 m 是奇数，刚好满足限制。

去掉这三个就变成偶数局面，解法一样同上。

于是做完了。

#include<bits/stdc++.h>
using namespace std;
void solve(){
    int n,m;
    cin>>n>>m;
    if(n==1){
        if(m!=1)puts("-1");
        else puts("1");
        return;
    }
    if(n&1){
        if(m&1){
            map<int,int>mp;
            for(int i=1;i<=m;i++)cout<<i<<" ";cout<<'\n';
            for(int i=1,j=m;i<=m;i++,j=(j-2+m)%m)mp[j]=i;
            for(int i=1;i<=m;i++)cout<<mp[i]<<" ";cout<<'\n';
            for(int i=1,j=m;i<=m;i++,j=(j-2+m)%m)mp[((1+m)/2)*3-j-i]=i;
            for(int i=1;i<=m;i++)cout<<mp[i]<<" ";cout<<'\n';
        }else{
            puts("-1");
            return;
        }
        n-=3;
    }
    while(n){
        for(int i=1;i<=m;i++)cout<<i<<' ';cout<<'\n';
        for(int i=m;i;i--)cout<<i<<' ';cout<<'\n';
        n-=2;
    }
}
int main(){
    // ios::sync_with_stdio(0);
    // cin.tie(),cout.tie();
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}