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

chenhanzheapple · 2026-03-04 22:18:03 · 题解

传送门

思路

首先注意到一个数最多被交换 2 次，也就是 a_i-1,a_i+1,a_i 和 a_i+1,a_i-1,a_i 两种情况。

所以考虑 DP。

设 f_{i,j,k} 表示现在决策了 i 个数的位置，第 i-1 个位置是 j，第 i 个位置是 k 的方案数。

因为一个位置合法的状态并不多（因为 j 和 k 只有可能是 i-4,i-3,i-2,i-1,i 这几个位置上的数），所以可以用 map 存状态，然后用刷表法（我为人人）的方式进行转移。

转移方程是简单的，只需要考虑可以和要不要交换即可，详情请见代码。

代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n;
const int MOD = 998244353;
int a[1000005];
map<pair<int,int>,int> f[1000005];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    f[0][{-1e18,-1e18}] = 1;
    for(int i=0;i<n;i++){
        for(auto x:f[i]){
            auto y = x.first;
            f[i+1][{y.second,a[i+1]}] = (f[i+1][{y.second,a[i+1]}]+x.second)%MOD;
            if(abs(a[i+1]-y.second)==1){
                f[i+1][{a[i+1],y.second}] = (f[i+1][{a[i+1],y.second}]+x.second)%MOD;
                if(abs(a[i+1]-y.first)==1){
                    f[i+1][y] = (f[i+1][y]+x.second)%MOD;
                }
            }
        }
    }
    int ans = 0;
    for(auto x:f[n]){
        ans = (ans+x.second)%MOD;
    }
    cout << ans;
    return 0;
}