洛谷P3599 Koishi Loves Construction 题解

题意

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

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

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

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

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

输入格式：

第一行两个整数 $X$ 和 $T$，分别表示 Task 类型和测试点内的数据组数。

接下来 $T$ 行，每行一个整数表示每组数据中的 $n$。

输出格式：

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

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

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

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

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

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

数据范围：

对于所有测试点，满足 $1 \leq T \leq 10,~X=1,2,~1 \le n \le 10^5$ 。

本题是缝合怪：CF1822D 和 CF487C 。

第一问，考虑构造 $1,\,-2,\,3,\,-4,\,\cdots$ ，这样前缀和就是 $1,-1,2,-2,\cdots$ 。

第二问，可以发现

不能有区间 $[l,r]$ 的积 $\equiv 1\pmod{n}$ ，其中 $l > 1$ 。
不能有区间 $[l,r]$ 的积 $\equiv 0\pmod{n}$ ，其中 $r < n$ 。
$n \not\mid (\prod_{i=1}^{n-1}i)$ ，否则肯定凑不出来。

于是显然有 $a_1=1,~a_n=n$ 。并且从第三条可以发现 $n$ 为质数时有解（除了 $n=1$ 和 $n=4$ 的情况）

记 $p_i = \prod_{j=1}^ia_j$ ，那么构造一种方案使得 $p_i \equiv i \pmod{n}$ 即可，可以求逆元构造。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)())

bool is_pri(int x)
{
    for(int i = 2; i * i <= x; i++)
        if(x % i == 0) return false;
    return true;
}
int qpow(int a, int b, int mod)
{
    int r = 1;
    for(a %= mod; b; b >>= 1, a = a * a % mod)
        if(b & 1) r = r * a % mod;
    return r;
}
void solve1()
{
    int n; cin >> n; if((n & 1) && (n != 1)) { return cout << "0\n", void(0); }
    cout << "2 "; rep(i, 1, n) cout << (i & 1 ? n + 1 - i : i - 1) << " \n"[i == n];
}
void solve2()
{
    int n; cin >> n;
    if(n == 1) { return cout << "2 1\n", void(0); }
    if(n == 4) { return cout << "2 1 3 2 4\n", void(0); }
    if(!is_pri(n)) { return cout << "0\n", void(0); }
    cout << '2';
    for(int i = 1, x = 1, prod = 1; i < n; i++)
    {
        cout << ' ' << x;
        x = qpow(prod, n - 2, n) * (i + 1) % n; prod = prod * x % n;
    }
    cout << ' ' << n << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int cxy, qwq; cin >> cxy >> qwq;
    while(qwq--) { cxy - 1 ? solve2() : solve1(); }
    return 0;
}