贪心、构造
首先解决前缀和互不相同的构造问题。
很显然 $n$ 得放在第一位，否则 $n$ 前边的位置和 $n$ 的前缀和是相同的，这样就不符合条件了。
样例对于 $n=8$ 给出了一个 $n \sim 1$ 排列的构造，用程序验证一下这种构造在其他情况下是否正确。
发现当且仅当 $n=2^k$ 时这种构造正确，感觉用处不大。尝试对于给定的 $n$ 打表观察所有可行解并找规律。
发现 $n$ 为奇数且不为 $1$ 时无解，同时有几组很有趣的构造，它们的偶数项为 $1,3,5,7, \cdots ,n-1$ 而奇数项为 $n,n-2,n-4, \cdots ,2$，提交一次代码验证一下正确性，如果求的是前缀积的构造直接让代码返回 $-1$ 来区分。
4
4 1 2 3
6
6 1 4 3 2 5
8
8 1 6 3 4 5 2 7
10
10 1 8 3 6 5 4 7 2 9测试点只有 RE 和 AC 两种状态，全对了。
考虑这样为啥对，把偶数看成减法，奇数看成加法，$n$ 视为 $0$，那么相当于构造了一个 $0,1,-2,3,-4,\cdots$ 的序列，它的前缀和是 $0,1,-1,2,-2,\cdots$ 这样两两不同的。
接下来解决前缀积互不相同的构造问题。
很显然 $n$ 得放在最后一位，不然会出现多个前缀积为 $0$ 的位置。
继续想，如果 $[1,n-1]$ 中存在两个不同的整数 $i,j$ 使得 $ij \bmod n = 0$ 那么必定无解。实际上这个条件等价于 $\left( \prod\limits_{i=1}^{n-1} i \right) \bmod n = 0$，接下来没啥活了，打个表先。
似乎不满足上方判定无解条件的 $n$ 都有解，效率限制打表只能打到 $n=13$，观察已有的表猜想如何构造。
发现若 $n$ 为偶数且 $n > 4$ 则必定无解，这是显然的。题目中如果不会构造，仅判断有解会给部分分数，经过验证使用 $\prod\limits_{i=1}^{n-1} i$ 判断无解是正确的。
接下来只讨论 $n$ 为奇数的情况。
发现总是存在能够让前缀积为 $1,3,5,\cdots,n-2,2,4,\cdots,n-1,0$ 的构造方案。下表中每组数据的第二行是每个位置对应的前缀积模 $n$ 的值。
5
1 3 4 2 5
1 3 2 4 0
7
1 3 4 6 2 5 7
1 3 5 2 4 6 0
11
1 3 9 8 6 10 2 7 5 4 11
1 3 5 7 9 2 4 6 8 10 0继续观察，发现符合条件的奇数 $n$ 必为质数或 $1$，因为一旦 $n$ 有两个不同质因子 $\prod\limits_{i=1}^{n-1} i$ 就是 $n$ 的倍数，如果 $n$ 为质数 $p$ 的 $k$ 次方（$k \geq 2$）那么 $p$ 作为 $[1,n-1]$ 中的数的因数的出现次数就是 $cnt = \left\lfloor \dfrac{p^k - 1}{p} \right\rfloor + \left\lfloor \dfrac{p^k - 1}{p^2} \right\rfloor + \cdots + \left\lfloor \dfrac{p^k - 1}{p^{k-1}} \right\rfloor$，当 $p$ 取 $3$ 时对于所有 $k \geq 2$ 都有 $cnt \geq k$，故该结论成立。
根据当前位置前缀积的值 $a_i$ 与下一个位置的前缀积的值 $a_{i+1}$ 计算当前位置应该填入的数字 $\dfrac{a_{i+1}}{a_i}$，对 $1 \sim n-1$ 求一遍逆元即可。
时间复杂度 $O(n)$。
#include<bits/stdc++.h>
using namespace std;
int n;
void solution_add(){
scanf("%d",&n);
if(n==1) return puts("2 1"),void();
if(n&1) return puts("0"),void();
putchar('2'),putchar(' ');
int odd=n,eve=1;
for(int i=1;i<=n;i++){
if(i&1) printf("%d ",odd),odd-=2;
else printf("%d ",eve),eve+=2;
}
putchar('\n');
}
void solution_mul(){
scanf("%d",&n);
if(n==2) return puts("2 1 2"),void();
if(n==4) return puts("2 1 3 2 4"),void();
long long mul=1ll;
for(int i=1;i<=n-1;i++) mul=mul*i%n;
if(mul==0) return puts("0"),void();
static int inv[100'005],sum[100'005];
inv[1]=1,sum[1]=1;
for(int i=2;i<=n-1;i++){
sum[i]=sum[i-1]+2;
if(sum[i]==n) sum[i]=2;
inv[i]=(-1ll*(n/i)*inv[n%i]%n+n)%n;
}
putchar('2'),putchar(' ');
putchar('1'),putchar(' ');
for(int i=1;i<=n-2;i++){
int ans=1ll*sum[i+1]*inv[sum[i]]%n;
printf("%d ",ans);
}
printf("%d\n",n);
}
int X,T;
int main(){
scanf("%d%d",&X,&T);
if(X==1) while(T--) solution_add();
else while(T--) solution_mul();
return 0;
}