标签：前缀 int 题解 ll 构造 cdots P3599 我们

本题是一道比较典的构造题，拿来扩宽扩宽大家的眼界吧。

Task 1

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

很容易想到的一点是：\(n\) 一定排在第一位，因为如果排在别的位，加上 \(n\) 后在模 \(n\) 意义下是不变的，因此不满足题意，只能放在第一位。

然后我们可能有一个朴素的想法：构造出的前缀和序列在模 \(n\) 意义下为 \(0,1,2,3,\cdots ,n\)。但是很显然，这是行不通的（做差分即可）。

但是当我们随便试试，我们也可以想到一种前缀和序列：\(0,1,-1,2,-2 \cdots\)。我们对它做个差分，就可以得到原序列为 \(0,1,-2,3,-4,\cdots\)。这很显然就是 \(n,1,n-2, 3, n-4, \cdots\)。这样就可以构造出来了！

但是还有一种情况，就是无解。我们考虑下当什么时候为无解，自己手玩几组样例就能发现：当 \(n\) 为除 \(1\) 以外的奇数时无解。

证明：

\[\sum \limits _{i=1}^{n-1} i = \frac{n(n-1)}{2} =kn\equiv 0(\bmod{n}) \]

这样我们就可以愉快的 AC 掉 Task 1 了。

Task 2

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

很显然，\(n\) 应该放最后，因为如果前缀积中出现 \(n\) 后后面的前缀积一定全为 \(0\)。

我们先来判断无解：当 \(n\) 为大于 \(4\) 的合数时无解。

---

证明：

引理：当 \(n\) 为大于等于 \(4\) 的合数时，存在 \(a, b < n\) 且 \(ab \bmod n = 0\)

因此 \(\prod_{1}^{n-1}i \bmod n=0\)

所以不管我们怎么摆放前 \(n-1\) 个数，总是会出现 \(2\) 个 \(0\)（一个为 \(n\)，一个为 \(ab\)）。

所以当 \(n\) 为大于 \(4\) 的合数时无解。

引理的证明：

1. 当 \(n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\) 时，我们可以找到两个数 \(x=\prod_{i=1}^{z}p_i^{a_i},y=\prod_{i=z+1}^{k}p_i^{a_i}\) 满足 \(xy \bmod n = 0\)。
2. 当 \(n=p^{k}(k>2)\) 时，我们可以找到 \(x=p^{a},y=p^{k-a}\) 满足要求。
3. 当 \(n=p^2(p>2)\) 时，我们可以找到 \(x=p, y = 2p\)，这时 \(n|xy\)。

得证。

---

有了上面的定理，我们就很好判断是否有解了。剩下的问题就是开始构造了。

我们通过一些手段（打表等）可以发现一个规律：前缀积为 \(1,2,3,\cdots\) 的方案一定能构造出来。我们就可以考虑这个方案。

不难发现按下面的方案构造就能出正解：

\[1,2, \frac{3}{2},\frac{4}{3},\frac{5}{4} \cdots \]

当 \(n\) 为 \(4\) 时，可以直接打表，当 \(n > 4\) 时，根据上面的无解方案，我们可以知道 \(n\) 一定为质数，我们就可以直接快速幂求逆元。

完整代码：

#define LOCAL
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

const int N = 1e6 + 10;
bitset<N> st;
int primes[N], cnt;
int a[N];
int type;

ll qmi(ll a, ll b, ll p)
{
    ll res = 1;
    while(b)
    {
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

void init(int n)
{
    for(int i = 2; i <= n; i ++ )
    {
        if(!st[i])
        {
            primes[++ cnt] = i;
        }
        for(int j = 1; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int main()
{
    init(100001);
    st[4] = false;

    type = read();
    int T = read();

    while(T -- )
    {
        int n = read();
        if(type == 1)
        {
            if(n == 1)
            {
                puts("2 1");
                continue;
            }
            if(n & 1) puts("0");
            else
            {
                printf("2 ");
                for(int i = 0; i < n; i ++ )
                {
                    if(!(i & 1)) printf("%d ", n - i);
                    else printf("%d ", i);
                }
                puts("");
            }
        }
        else
        {
            if(st[n]) puts("0");
            else
            {
                printf("2 1 ");
                if(n == 4)
                {
                    printf("3 2 4\n");
                    continue;
                }
                for(int i = 2; i < n; i ++ )
                {
                    printf("%d ", (ll)i * qmi(i - 1, n - 2, n) % n);
                }
                printf("%d\n", n);
            }
        }
    }

    return 0;
}

标签：前缀,int,题解,ll,构造,cdots,P3599,我们
From： https://www.cnblogs.com/crimsonawa/p/17542001.html