题解 - [Luogu P3599] Koishi Loves Construction

发表于 更新于 分类于 ， 本文字数： 1.2k 阅读时长 ≈ 4 分钟

题目链接

原始题面

题目描述

Koishi 决定走出幻想乡成为数学大师！

Flandre 听说她数学学的很好，就给 Koishi 出了这样一道构造题:

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

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

按照套路，Koishi 假装自己根本不会捉，就来找你帮忙辣

输入格式

第一行两个整数 \(X\) 和 \(T\), 分别表示 Task 类型和测试点内的数据组数

接下来 \(T\) 行，每行一个整数表示每组数据中的 \(n\)

输出格式

为了方便 SPJ 的编写，您需要遵从以下格式输出

对于每组数据仅包含一行输出:

  1. 如果您认为当前数据不存在符合题意的构造，只需输出一个整数 \(0\)

  2. 如果您认为当前数据存在符合题意的构造却不会构造，只需输出一个整数 \(1\)

  3. 如果您认为当前数据存在符合题意的构造并成功构造，则需要先输出一个整数 \(2\), 再输出 \(n\) 个整数表示构造的方案

每两个整数之间需要有空格作为分隔符

输入输出样例

输入 #1

1
2
1 1
8

输出 #1

1
2 8 7 6 5 4 3 2 1

输入 #2

1
2
2 1
11

输出 #2

1
2 1 2 3 5 10 6 7 4 9 8 11

说明 / 提示

对于每组数据

  1. 如果您对于构造的存在性判断正确，您将会得到 \(30\%\) 的分数，若您的构造符合题意或者确实不存在符合题意的构造，您将会得到剩余的 \(70\%\) 的分数

  2. 如果您对于构造的存在性判断不正确，您将不会得到任何分数

对于每组测试点，您的得分将是本组数据点中得分的最小值

测试点类型 1: 10 分，满足 \(X=1,1\leq n\leq 10\)

测试点类型 2: 40 分，满足 \(X=1,1\leq n\leq10^5\)

测试点类型 3: 10 分，满足 \(X=2,1\leq n\leq 10\)

测试点类型 4: 40 分，满足 \(X=2,1\leq n\leq10^5\)

对于所有测试点，满足 \(1\leq T\leq 10\)

解题思路

由于 \(n=1\) 时的构造方法显然，故下面的讨论中假设 \(n>1\)

  • 对于 Task1:

    我们能很容易地发现：若对 \(n\) 可构造出满足要求的数列，则

    1. 第一个数必为 \(n\)
    2. 之后的数列中的任意子区间 \([l,r]\) 上的和 \(s_{l,r}\) 均满足 \(s_{l,r}{\equiv}\llap{/\,}0\pmod{n}\)

    由第二条可推出：所有非 \(1\) 奇数均不可构造，因为 \(\sum_{i=1}^{n-1}i=n(\frac{n-1}{2})\equiv0\pmod n\)

    对于其他情况，即 \(n\) 为偶数时，我们可以这样构造数列 \(a_1,a_2,\dots,a_n\):

    令

    \[ a_i=\frac{n}{2}+(-1)^i\left(i-1-\frac{n}{2}\right)=\begin{cases} n-i+1,&2\nmid i\\ i-1,&2\mid i \end{cases} \]

    用自然语言描述就是：奇数项从 \(n\) 递减，步长为 \(2\); 偶数项从 \(1\) 递增，步长为 \(2\)

    此时有

    \[ S_x:=\sum_{i=1}^xa_i\equiv(-1)^x\left\lfloor\frac{x}{2}\right\rfloor\pmod n,~\forall x\in[1,n]\cap\mathbb{N} \]

    换种写法就是 \(S_1=\overline{0},~S_2=\overline{1}~,S_3=\overline{-1},...,S_{n-1}=\overline\frac{n}{2}~,S_n=\overline{-\frac{n}{2}}\)

  • 对于 Task2:

    我们能很容易地发现：若对 \(n\) 可构造出满足要求的数列，则

    1. 第一个数必为 \(1\)
    2. 最后一个数必为 \(n\)
    3. 剩下的数中任意子区间 \([l,r]\) 上的积 \(p_{l,r}\) 均满足 \(p_{l,r}{\equiv}\llap{/\,}0,1\pmod{n}\)

    由第三条可推出：所有满足 \(n\mid\prod_{i=1}^{n-1}i\) 的数均不可构造，即所有非 \(4\) 合数均不可构造

    对于其他情况

    • 当 \(n=4\) 时，其有唯一解 1 3 2 4

    • 当 \(n\ne4\) 时，即当 \(n\) 为素数时，我们令 \(a_i\) 为结果的第 \(i\) 项，\(P_i\) 为结果的前 \(i\) 项积，我们可以这样构造:

      令

      \[ a_i=\begin{cases} 1,&i=1\\ iP_{i-1}^{-1}\bmod n,&i>1 \end{cases} \]

      此时即有 \(P_i\equiv i\pmod n\),

      \[ a_i=\begin{cases} 1,&i=1\\ i(i-1)^{-1}\bmod n,&i>1 \end{cases} \]

      下面证明 \(a_i\) 的唯一性

      假设 \(a_i=a_j,~1\leqslant i,j\leqslant n\)

      又 \(\def\ss#1{a_{ #1}({ #1}-1)\equiv { #1}\pmod n}\ss{i},~~\ss{j}\)

      可得 \(0\equiv a_i(i-1)-a_j(j-1)\equiv i-j\pmod n\), 即 \(i=j\)

代码参考

Show code

Luogu_P3599view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
long long qpow(long long a, long long b, long long mod) {
  long long res = 1;
  for (; b; b >>= 1, (a *= a) %= mod)
    if (b & 1) (res *= a) %= mod;
  return res;
}
const int N = 1e5 + 5;
bool vis[N];
int prime[N], cnt_prime;
void init_prime(int n = N - 1) {
  for (int i = 2; i <= n; ++i) {
    if (!vis[i]) prime[++cnt_prime] = i;
    for (int j = 1; j <= cnt_prime && i * prime[j] <= n; ++j) {
      vis[i * prime[j]] = 1;
      if (i % prime[j] == 0) break;
    }
  }
}
int main() {
  init_prime();
  int x, kase;
  cin >> x >> kase;
  while (kase--) {
    int n;
    cin >> n;
    if (x == 1) {
      if (n & 1 && n > 1) {
        cout << "0" << endl;
        continue;
      }
      cout << "2";
      for (int i = 1; i <= n; ++i) cout << " " << (i & 1 ? n + 1 - i : i - 1);
      cout << endl;
    } else {
      if (vis[n] ^ (n == 4)) {
        cout << "0" << endl;
        continue;
      }
      if (n == 1) {
        cout << "2 1" << endl;
        continue;
      }
      if (n == 4) {
        cout << "2 1 3 2 4" << endl;
        continue;
      }
      cout << "2";
      for (long long i = 1, _ = 1, prod = 1; i < n; ++i) {
        cout << " " << _;
        _ = 1ll * (i + 1) * qpow(prod, n - 2, n) % n;
        (prod *= _) %= n;
      }
      cout << " " << n << endl;
    }
  __end_kase:;
  }
  return 0;
}