20220219-Koishi-loves-construction

Posted on | In

简单构造题。注意分奇偶这个常见套路。

题意

给定 $n$，试构造 $1\sim n$ 的排列满足下列限制中的一条，或报告无解：

  1. $n$ 个前缀和在模 $n$ 意义下互不相同；
  2. $n$ 个前缀积在模 $n$ 意义下互不相同。

给定需满足的限制与 $n$，求排列。

多测，$T\le 10,n\le 10^5$。

source: luogu P3599 Koishi Loves Construction

思路

第一问

奇数显然不行：$n\mid 1+\cdots+n$，因而 $Sn=0$。若 $n$ 放在第 $i$ 位（$i\ne 1$），则 $S_i=S{i-1}$，矛盾，因而 $i=1$。此时 $S_1=S_n=0$，亦矛盾。

对于偶数 $n$：首先放置 $n$ 为首位。对于剩下的部分，我们试着两两配对使和为小定值。这里取 $1$，那么 $S{2k}=k,S{2k+1}=k+a_{2k+1}$（先删去开头的 $0$）。于是发现偶数项不断上升，尝试将奇数项不断下降，于是构造出 $2,-1,4,-3,5,-4,\cdots$。易验证正确性。时间复杂度 $\Theta(n)$。

第二问

非 $4$ 合数显然不行：如果 $n$ 不在末位而在第 $i$ 位，则 $Sj=0(j\ge i)$ ，矛盾。故 $n$ 在末位，$S_n=0$。由 $n\mid (n-1)!$ 知 $S{n-1}=0$，矛盾。

$1,2,4$ 特判一下，剩下奇素数的情况。$n$ 放末位，前面需使前缀积互不相同。考虑求离散对数，转化为 $n-1$ 的第一问。时间复杂度 $\Theta(n)$。

代码

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <cstdio>
#include <vector>

namespace mirai {

constexpr int MAXN = 100005;
int a[MAXN];

int pow(long long a, int b, int n) {
  long long ans = 1;
  while (b) {
    if (b & 1) {
      ans = ans * a % n;
    }
    a = a * a % n;
    b >>= 1;
  }
  return ans;
}

int main(int argc, char** argv) {
  int x, t;
  std::scanf("%d%d", &x, &t);
  while (t--) {
    int n;
    std::scanf("%d", &n);
    if (x == 1) {
      if (n == 1) {
        std::printf("2 1\n");
      } else if (n % 2 == 0) {
        std::printf("2 %d ", n);
        int odd = n - 1, even = 2;
        for (int i = 1; i <= n - 1; ++i) {
          if (i % 2 == 1) {
            std::printf("%d ", odd);
            odd -= 2;
          } else {
            std::printf("%d ", even);
            even += 2;
          }
        }
        std::printf("\n");
      } else {
        std::printf("0\n");
      }
    } else {
      bool isprime = true;
      if (n == 1) {
        std::printf("2 1\n");
        continue;
      }
      if (n == 2) {
        std::printf("2 1 2\n");
        continue;
      }
      if (n == 4) {
        std::printf("2 1 3 2 4\n");
        continue;
      }
      for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
          isprime = false;
          break;
        }
      }
      if (!isprime) {
        std::printf("0\n");
        continue;
      }
      std::vector<int> primes;
      int num = n - 1, now = 2;
      while (num != 1) {
        if (num % now == 0) {
          primes.push_back(now);
          while (num % now == 0) {
            num /= now;
          }
        }
        now += now == 2 ? 1 : 2;
      }
      int proot = 2;
      // std::printf("prime: ");
      while (true) {
        bool flag = true;
        for (auto i : primes) {
          // std::printf("%d ", i);
          if (pow(proot, (n - 1) / i, n) == 1) {
            flag = false;
            break;
          }
        }
        if (flag) {
          break;
        }
        proot++;
      }
      // std::printf("\nproot = %d\n", proot);
      a[0] = 1;
      for (int i = 1; i <= n - 1; ++i) {
        a[i] = static_cast<long long>(a[i - 1]) * proot % n;
        // std::printf(" %lld", a[i]);
      }
      std::printf("2 1 ");
      int odd = n - 2, even = 2;
      for (int i = 1; i <= n - 2; ++i) {
        // std::printf("%d ", a[i % 2 == 1 ? i : n - 1 - i]);
        if (i % 2 == 1) {
          std::printf("%d ", a[odd]);
          odd -= 2;
        } else {
          std::printf("%d ", a[even]);
          even += 2;
        }
      }
      std::printf("%d\n", n);
    }
  }
  return 0;
}

} // namespace mirai

int main(int argc, char** argv) {
  return mirai::main(argc, argv);
}