洛谷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;
}