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

我们先考虑如果保证

a_i = i

时怎样做。

不难发现如果

i

与某个位置交换过了，那么其再也无法交换，于是我们称操作

i

为交换

i

与

i + 1

，那么我们就要选若干个操作，使得没有任何两个操作编号相邻，设

f_{i, 0/1}

表示选定了前

i

个操作，第

i

个选还是不选的方案数，就有转移

f_{i, 1} = f_{i - 1, 0} f_{i, 0} = f_{i - 1, 0} + f_{i - 1, 1} = f_{i - 1, 0} + f_{i - 2, 0}

我们记

fib_i = \begin{cases} 1 & i \in \{0, 1\}\\ fib_{i - 1} + fib_{i - 2} & \text{otherwise}\\ \end{cases}

不难发现

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：

CPP

#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;
}

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

文章操作

相关推荐

评论

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