Atcoder ARC159C Permutation Addition

设 \(s=\sum\limits_{i = 1}^n a_i\)，考虑加上排列 \(p\)，那么 \(s\leftarrow s + \frac{n\times (n + 1)}{2}\)。
当有解时，因为 \(a_i\) 相等，所以有 \(s\bmod n = 0\)。

考虑 \(n \bmod 2 = 1\) 时，\(\frac{n\times (n + 1)}{2}\bmod n = 0\)，所以 \(s\bmod n = 0\) 时才会有解。

然后构造方案，考虑先构造 \(2\) 个排列 \(p_i = i, p'_i = n - i + 1(1\le i\le n)\)，这样的话 \(a_i\leftarrow a_i + p_i + p'_i\) 相当于 \(a_i\leftarrow a_i + (n + 1)\)，\(a_i\) 之间大小没有变化。
然后进行一些变化，交换 \(p_1, p_2\) 的值，即 \(p_1 = 2, p_2 = 1, p_i = i(3\le i\le n),p'_j = n - j + 1(1\le j\le n)\)，这样再 \(a_i\leftarrow a_i + p_i + p'_i\)，则会是 \(a_1\leftarrow a_1 + (n + 2), a_2\leftarrow a_2 + n, a_i\leftarrow a_i + (n + 1)(3\le i\le n)\)，\(a_i\) 之间大小就相当于是 \(a_1\leftarrow a_1 + 1, a_2\leftarrow a_2 - 1\)。
于是发现仅需 \(2\) 个排列就可以使 \(a_i\leftarrow a_i + 1, a_j\leftarrow a_j - 1(1\le i, j\le n)\)，因为排列的值是可以是可以交换的。
于是令 \(mid = \frac{s}{n}\)，一直使用上述操作使 \(a_i = mid(1\le i\le n)\) 即可，可以证明一定有方法且小于操作次数。

当 \(n\bmod 2 = 0\) 时，\(\frac{n\times (n + 1)}{2}\bmod n = \frac{n}{2}\)，所以当 \(s\bmod n = 0\) 或 \(s\bmod n = \frac{n}{2}\) 有解。
当 \(s\bmod n = 0\) 时，直接用上述的做法；当 \(s\bmod n = \frac{n}{2}\) 时，先随便加一个排列 \(p\) 上去使得 \(s\bmod n = 0\)，然后再用上述的做法即可。

能发现构造次数即为 \([n\bmod 2 = 0\land s\bmod n = \frac{n}{2}] + \sum\limits_{i = 1}^n |a_i - mid|\)，不会超过 \(10^4\)。

// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: C - Permutation Addition
// Contest: AtCoder - AtCoder Regular Contest 159
// URL: https://atcoder.jp/contests/arc159/tasks/arc159_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 50 + 5;
int a[N];
int main() {
	int n;
	scanf("%d", &n);
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		sum += a[i];
	}
	if (n % 2 == 1 && sum % n != 0) {
		printf("No\n");
		return 0;
	}
	if (n % 2 == 0 && sum % n != 0 && sum % n != n / 2) {
		printf("No\n");
		return 0;
	}
	printf("Yes\n");
	int p1 = 0;
	if (n % 2 == 0 && sum % n == n / 2) {
		p1 = 1;
		sum += n * (n + 1) / 2;
		for (int i = 1; i <= n; i++) {
			a[i] += i;
		}
	}
	int mid = sum / n;
	vector<int> x, y;
	for (int i = 1; i <= n; i++) {
		for (; a[i] < mid; a[i]++) {
			x.push_back(i);
		}
		for (; a[i] > mid; a[i]--) {
			y.push_back(i);
		}
	}
	printf("%d\n", (int)(x.size()) * 2 + p1);
	if (p1) {
		for (int i = 1; i <= n; i++) {
			printf("%d ", i);
		}
		printf("\n");
	}
	for (size_t i = 0; i < x.size(); i++) {
		int u = x[i], v = y[i];
		int l = 3, r = n - 2;
		for (int j = 1; j <= n; j++) {
			printf("%d ", (j != u && j != v ? l++ : (j == u ? 2 : 1)));
		}
		printf("\n");
		for (int j = 1; j <= n; j++) {
			printf("%d ", (j != u && j != v ? r-- : (j == u ? n : n - 1)));
		}
		printf("\n");
	}
	return 0;
}