题目
Task1：试判断能否构造并构造一个长度 $n$ 的 $1...n$ 的排列，满足其 $n$ 个前缀和在模 $n$ 的意义下互不相同
Task2：试判断能否构造并构造一个长度 $n$ 的 $1...n$ 的排列，满足其 $n$ 个前缀积在模 $n$ 的意义下互不相同。
分析
既然考虑原数列很难，就直接考虑前缀和和前缀积。
对于task1：
在模 $n$ 意义下，$\{1,2,3,...n\}$ 等价于 $ \{0,1,-1,2,-2,... \}$，我们将它设为前缀和。
其次，我们可以发现 $n$ 必定出现在数列的第一位，否则 $n$ 出现前后的两个前缀和会相等。已知首项，已知前缀和，就可以推出各项。奇数不行。
总结：
当 $n$ 为奇数时，无法构造出合法解（1特判）
当 $n$ 为偶数时，可以构成形如 $n, n-1, 2, n-3, 4...$ 这样的数列
对于Task2：
根据消元法，构造数列 $1,\frac{2}{1},\frac{3}{2},...,\frac{n-1}{n-2}$。
显然，合数没有解，因为其两个两个因子相乘之后，后面取模都为0了。
显然，首项为1，末项为n。
只需证明中间那些数是互不相同的。因为 $\frac{k+1}{k} = 1 + \frac{1}{k}$，当 $n$为质数时，每个元素都有逆元且不相同。
总结：
当 $n$ 为合数，无法构造出合法解（特判4）
当 $n$ 为质数，可以构造形如 $1,\frac{2}{1},\frac{3}{2},...,\frac{n-1}{n-2},n$.（特判1）
注意开 long long!!!
#include<bits/stdc++.h>
using namespace std; typedef long long ll;
const int maxn = + ;
int task, T;
int n; void solve1()
{
if(n == )
{
printf("2 1\n");
return;
}
if(n&)
{
printf("0\n");
return;
}
printf("2 %d ", n);
ll pre = ;
//printf("n:%d\n", n);
for(int i = ;i < n;i++)
{
int tmp = ((i&) == ? : -) * ((i+) / ); //printf("tmp: %d\n", tmp);
printf("%d", (tmp -pre+n)%n);
if(i == n-) printf("\n");
else printf(" ");
pre = tmp;
}
} bool is_prime[maxn + ];
void sieve(int n)
{
int m = (int)sqrt(n + 0.5);
memset(is_prime, true, sizeof(is_prime));
is_prime[] = is_prime[] = false; //1是特例
for (int i = ; i <= m; i++) if (is_prime[i])
for (int j = i * i; j <= n; j += i) is_prime[j] = false;
} int inv[maxn];
void init_inv(int n, int mod)
{
inv[] = ;
for(int i = ;i < n;i++) inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod; //加mod不改变结果
} void solve2()
{
if(n == )
{
printf("2 1\n");
return;
}
if(n == )
{
printf("2 1 3 2 4\n");
return;
}
sieve(n);
if(!is_prime[n])
{
printf("0\n");
return;
}
init_inv(n, n);
printf("2 1 ");
for(int i = ;i <= n-;i++) printf("%d ", 1LL * i * inv[i-] % n);
printf("%d\n", n);
} int main()
{
scanf("%d%d", &task, &T);
while(T--)
{
scanf("%d", &n);
if(task == ) solve1();
else solve2();
}
return ;
}
参考链接：