题面

题解

Polya 计数。旋转 2 个置换，翻转 3 个置换，单位置换 1 个。

旋转的循环就是每层（？）3 个转，反转就是对角线外两两转。

代码

const int N = 0, bN = 210;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, N;
	struct bigNum {
		int a[bN];
		bigNum (int x) { for (memset (a, 0, sizeof a); x; a[++a[0]] = x % 10, x /= 10); }
		void times (int x) {
			int r = 0;
			for (int i = 1; i <= a[0] || r; ++i) {
				int p = a[i] * x + r;
				r = p / 10; a[i] = p % 10;
				a[0] = max(a[0], i);
			}
		}
		void div (int x) {
			int r = 0;
			for (int i = a[0]; i; i--) {
				int p = a[i] + r * 10;
				r = p % x; a[i] = p / x;
			}
			for (; !a[a[0]]; a[0]--);
		}
		void print() { for(int i = a[0]; i; printf("%d", a[i]), i--); putchar(10);}
	};
	bigNum operator + (bigNum a, bigNum b) {
		if (a.a[0] < b.a[0]) swap(a, b);
		int r = 0;
		for (int i = 1; i <= a.a[0] || r; ++i) {
			int p = a.a[i] + b.a[i] + r;
			r = p / 10; a.a[i] = p % 10;
			a.a[0] = max(a.a[0], i);
		}
		return a;
	}
	int main () {
		n = Read(); N = n * (n + 1) / 2;
		bigNum A(1), B(2), C(3);
		for (int i = 1; i <= N; i++) A.times(2);
		for (int i = 1; i <= (N + 2) / 3; i++) B.times(2);
		for (int i = 1; i <= (N - (n + 1) / 2) / 2 + (n + 1) / 2; i++) C.times(2);
		A = A + B + C; 
		A.div(6);
		A.print();
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}