题解：P12538 [XJTUPC 2025] 泰拉构史

Claire0918 · 2025-11-21 15:59:51 · 题解

我们先考虑如果保证 a_i = i 时怎样做。

不难发现如果 i 与某个位置交换过了，那么其再也无法交换，于是我们称操作 i 为交换 i 与 i + 1，那么我们就要选若干个操作，使得没有任何两个操作编号相邻，设 f_{i, 0/1} 表示选定了前 i 个操作，第 i 个选还是不选的方案数，就有转移

我们记

不难发现 f_{i, 0} = fib_i，答案即求 f_{n - 1, 0} + f_{n - 1, 1} = f_{n, 0} = fib_n。

考虑原问题，如果 i 与 i + 1 在 \{a_i\} 中可以交换到相邻，我们就称这二者合成一段，如此可以分成若干段。不难发现一段内的答案与保证 a_i = i 的问题本质相同，所以一个长为 x 的段答案就是 fib_x，而如果 i 和 i + 1 不在一段，则小于等于 i 的和大于等于 i + 1 的显然互相断开了，于是两段之间相互独立。将每一段贡献相乘即可，因为用到离散化，时间复杂度 \mathcal{O}(n\log n)。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

namespace IO{
    #define SIZ (1 << 18)
    char ibuf[SIZ], *p1 = nullptr, *p2 = nullptr;
    #define gc() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, SIZ, stdin), p1 == p2) ? EOF : *p1++)
    template <typename tp>
    void rd(tp &x){
        x = 0;
        int f = 1;
        char c = gc();
        for (;!isdigit(c); c == '-' && (f = -1), c = gc());
        for (;isdigit(c); x = x * 10 + (c ^ 48), c = gc());
        x *= f;
    }
    template <typename tp, typename... Arg>
    inline void rd(tp &x, Arg &...args){
        rd(x), rd(args...);
    }
    char obuf[SIZ], *p3 = obuf;
    inline void flush(){
        fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf;
    }
    inline void pc(const char c){
        p3 - obuf == SIZ && (flush(), 1538), *p3++ = c;
    }
    template <typename tp>
    void prt(tp x, char ed = '\n'){
        x < 0 && (pc('-'), x = -x);
        static char stk[40];
        int stkp = 0;
        do{
            stk[stkp] = char(x % 10), x /= 10, ++stkp;
        } while (x);
        while (stkp){
            pc(char(stk[--stkp] + '0'));
        }
        pc(ed);
    }
    #undef gc
    #undef SIZ
}

using namespace IO;

const int maxn = 1e6 + 10, mod = 998244353;

int n;
long long res = 1;
int a[maxn], f[maxn], pos[maxn];
vector<int> tmp;

template<typename Tp_x, typename Tp_y>
inline int mod_add(Tp_x x, Tp_y y){
    return x += y, x >= mod ? x -= mod : x;
}

template<typename Tp_x, typename Tp_y>
inline int self_mod_add(Tp_x &x, Tp_y y){
    return x = mod_add(x, y);
}

template<typename Tp, typename... Arg>
inline int mod_add(Tp x, Arg ...args){
    return x += mod_add(args...), x >= mod ? x -= mod : x;
}

int main(){
    rd(n), f[0] = f[1] = 1;
    for (int i = 2; i <= n; i++){
        f[i] = mod_add(f[i - 1], f[i - 2]);
    }
    for (int i = 1; i <= n; i++){
        rd(a[i]), tmp.push_back(a[i]);
    }
    sort(tmp.begin(), tmp.end()), tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
    for (int i = 1; i <= n; i++){
        pos[lower_bound(tmp.begin(), tmp.end(), a[i]) - tmp.begin() + 1] = i;
    }
    for (int i = 1; i <= tmp.size();){
        int l = i + 1;
        for (;l <= tmp.size() && tmp[l - 1] == tmp[l - 2] + 1 && 
            (pos[l] == pos[l - 1] + 1 || 
            pos[l] == pos[l - 1] - 1 || 
            pos[l] == pos[l - 1] - 2 && (a[pos[l] + 1] == tmp[l - 1] + 1 || a[pos[l] + 1] == tmp[l - 1] - 2) || 
            pos[l] == pos[l - 1] + 2 && (a[pos[l] - 1] == tmp[l - 1] + 1 || a[pos[l] - 1] == tmp[l - 1] - 2) || 
            pos[l] == pos[l - 1] - 3 && (a[pos[l] + 1] == tmp[l - 1] + 1 && a[pos[l] + 2] == tmp[l - 1] - 2 || a[pos[l] + 1] == tmp[l - 1] + 1 && a[pos[l] + 2] == tmp[l - 1] - 2) ||
            pos[l] == pos[l - 1] + 3 && (a[pos[l] - 1] == tmp[l - 1] + 1 && a[pos[l] - 2] == tmp[l - 1] - 2 || a[pos[l] - 1] == tmp[l - 1] + 1 && a[pos[l] - 2] == tmp[l - 1] - 2));
            l++);
        res = res * f[l - i] % mod, i = l;
    }
    prt(res), flush();

return 0;
}