Codeforces Round 779 (Div. 2)

B. Marin and Anti-coprime Permutation

题意：给定 $n$ ，问有几种 $n$ 的排列 $p$ ，使得 $\gcd (1 \cdot p_1, \, 2 \cdot p_2, \, \dots, \, n \cdot p_n) > 1$ .

数论

gcd只可能是1或2.

假设 gcd=k，则 $1$ 到 $n$ 中所有非 $k$ 的倍数都必须与 $k$ 的倍数相乘。而总共有 $\lfloor\frac{n}{k}\rfloor$ 个 $k$ 倍数，所以必须要 $2\cdot\lfloor\frac{n}{k}\rfloor \geq n$ ，则 $k\le 2$ 。

#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e5 + 10;

ll fac[N], inv[N];
ll power(ll a, int x) {
    ll ans = 1;
    while (x) {
        if (x & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        x >>= 1;
    }
    return ans;
}
void init() {
    fac[0] = 1;
    for (int i = 1; i < N; i++) {
        fac[i] = fac[i - 1] * i %mod;
    }
    inv[N - 1] = power(fac[N - 1], mod - 2);
    for (int i = N - 2; i >= 0; i--) {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}
ll C(int n, int k) {
    if (n < k)return 0;
    return fac[n] * inv[k] % mod*inv[n - k] % mod;
}

int T;
int n;

int main() {
    init();
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        if(n&1)puts("0");
        else{
            printf("%lld\n", fac[n / 2] * fac[n / 2] % mod);
        }
    }
    return 0;
}

C. Shinju and the Lost Permutation

题意：定义一个数列的前缀数组为该数列的各位置的前缀最大值。定义一个数列的能量为该数列的前缀数组中不同值的个数。现在有一个初始数列，循环移位，每次移位后求新数列的能量。现给出各时刻的能量值，问是否存在合法的初始数列。

构造

能量的变化必定满足以下条件：

有且仅有一次能量为1.
若能量增加，则每次最多增加1.
若能量减少或不变，则无限制。

满足条件的话，通过能量的减少和增加可以得到新移到第一位的数字与后面某个数字的大小关系，由此建出拓扑图后可以随便构造，必定有解。

#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e5 + 10;

int T;
int n;
int a[N];

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)scanf("%d", &a[i]);
        a[n + 1] = a[1];
        int cnt = 0, flg = 1;
        for(int i = 1; i <= n; i++){
            if(a[i] == 1)cnt++;
            if(a[i + 1] - a[i] > 1)flg = 0;
        }
        puts((flg && cnt == 1) ? "YES" : "NO");
    }
    return 0;
}

D2. 388535 (Hard Version)

题意：给定 $l,r$ ，有一个秘密数组，是 $[l,r]$ 的排列，以及一个秘密数字 $x$ 。先给出秘密数组各元素异或秘密数字 $x$ 的结果，问秘密数字 $x$ 是几，输出任意一解。

Trie

原数组两两不同，异或后的的数组必定也是两两不同。故只要限制给出的数组异或 $x$ 的值的最大值为 $r$ ，最小值为 $l$ ，则还原出的秘密数组必定为 $[l,r]$ 的排列。

枚举 $x$ ，用Trie $O(\log x)$ 求给定数组异或 $x$ 的最大最小值。

但不能直接枚举。考虑给定数组一定有一个数与 $l$ 对应，所以枚举数组中每个元素，假设它与 $l$ 对应，得到 $x$ 。

注意本题卡常，用vector，不用数组初始化。

#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e6 + 10;

int tot;

void ins(int x, vector<vector<int> > &ch) {
    int rt = 0;
    for (int i = 16; i >= 0; i--) {
        int bt = (x >> i & 1);
        if (!ch[rt][bt]) {
            int u = ++tot;
            ch[u][0] = ch[u][1] = 0;
            ch[rt][bt] = u;
        }
        rt = ch[rt][bt];
    }
}

int T;
int l, r;
int a[N];

int getmin(int x, vector<vector<int> > &ch){
    int rt = 0;
    int ans = 0;
    int pt = (1 << 16);
    for(int i = 16; i >= 0; i--){
        int bt = ((x & pt) != 0);
        if(ch[rt][bt])rt = ch[rt][bt];
        else{
            ans |= pt;
            rt = ch[rt][bt ^ 1];
        }
        pt >>= 1;
    }
    return ans;
}

int getmax(int x, vector<vector<int> > &ch){
    int rt = 0;
    int ans = 0;
    int pt = (1 << 16);
    for(int i = 16; i >= 0; i--){
        int bt = ((x & pt) != 0);
        if(ch[rt][bt ^ 1]){
            ans |= pt;
            rt = ch[rt][bt ^ 1];
        }
        else rt = ch[rt][bt];
        pt >>= 1;
    }
    return ans;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &l, &r);
        int s = 0, t = 0;
        vector<vector<int> > ch((r - l + 1) * 32 , vector<int>(2 , 0));
        tot = 0;
        for (int i = l; i <= r; i++)scanf("%d", &a[i]), s ^= a[i];
        for (int i = l; i <= r; i++)t ^= i;
        if ((r - l + 1) & 1) {
            printf("%d\n", s ^ t);
            continue;
        }
        for(int i = l; i <= r; i++)ins(a[i], ch);
        for(int i = l; i <= r; i++){
            int x = (l ^ a[i]);
            if(getmin(x, ch) == l && getmax(x, ch) == r){
                printf("%d\n", x);
                break;
            }
        }
    }
    return 0;
}