P3599 Koishi Loves Construction

Description

给定一下两种询问：

Task1：试判断能否构造并构造一个长度为 \(n\) 的 \(1\dots n\) 的排列，满足其 \(n\) 个前缀和在模 \(n\) 的意义下互不相同。
Task2：试判断能否构造并构造一个长度为 \(n\) 的 \(1\dots n\) 的排列，满足其 \(n\) 个前缀积在模 \(n\) 的意义下互不相同。

如果有相应的构造，还需输出其中一种合法的构造。

Solution

Task1

对题目进行分析，可以得到几个结论：

不能有区间 \([L,R](L \neq 1)\) 的倍数，否则 \(sum_{L-1}\equiv sum_R \pmod n\)
对于构造出的序列 \(a\) ， \(a_1 = n\) ，否则 \(sum_i\equiv sum_{i-1} \pmod n\)
\(n\in even\cup 1\) ，因为对于 \(n\in odd\)：

\[\sum_{i=2}^{n}a_i = \sum_{i=1}^{n-1}i = n\times\left(\frac{n-1}2\right)\equiv 0 \pmod n \]

从而不符合上面第一点的限制。

接下来如果在考场上，可以先与大样例对拍，确认无误后就可以打暴搜找规律，在 \(n = 6\) 下可以找到这样一组解：
6 1 4 3 2 5
通过这组解可以得到构造：

对于 \(i \in odd, a_i = n+1-i\) 。
对于 \(i \in even, a_i = i-1\) 。

Task2

Code

点击查看代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define mp make_pair
#define vi vector<int>
#define eb emplace_back
const int N = 1e5+5, MOD = 998244353, INF = 2e9;
inline int read() {
	register int x = 0, f = 1;
	register char ch = 0;
	while(ch < 48 || ch > 57) {
			ch = getchar();
			if (ch == '-') f = -1;
		}
	while(ch >= 48 && ch <= 57) x = x*10+(ch^48), ch = getchar();
	return f*x;
}

int n;

int powM(int x, int y) {
	int ret = 1;
	while (y) {
		if (y&1) ret = 1ll*ret*x%n;
		x = 1ll*x*x%n, y >>= 1;
	} return ret;
}

int pri[N], cntp;
bool np[N];
void sieve() {
	for (int i = 2; i <= 1e5; ++i) {
		if (!np[i]) pri[++cntp] = i;
		for (int j = 1; j <= cntp && i*pri[j] <= 1e5; ++j) {
			np[i*pri[j]] = true;
			if (i%pri[j] == 0) break;
		}
	}
}

void solve1() {
	if ((n&1)&&(n!=1)) return puts("0"), void();
	printf("2 ");
	for (int i = 1; i <= n; ++i)
		printf("%d ", i&1 ? n+1-i : i-1);
	puts("");
}

void solve2() {
	if (np[n] && n != 1 && n != 4) return puts("0"), void();
	if (n == 1) return puts("2 1"), void();
	if (n == 4) return puts("2 1 3 2 4"), void();
	printf("2 ");
	int tmp = 1, sum = 1;
	for (int i = 1; i <= n-1; ++i) {
		printf("%d ", tmp);
		tmp = 1ll*powM(sum, n-2)*(i+1)%n;
		sum = 1ll*sum*tmp%n;
	}
	printf("%d\n", n);
}

int main() {
	int opt, T;
	opt = read(), T = read();
	if (opt == 2) sieve();
	while (T--) {
		n = read();
		if (opt == 1) solve1();
		else solve2();
	}
	return 0;
}