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

ELECTRODE_kaf · 2025-06-11 17:05:02 · 题解

设 dp_{i,x,y} 表示考虑 a_1 到 a_i，序列最后两位分别为 x 和 y 的方案数。

考虑 dp_{i-1,x,y} 对于 dp_i 的贡献。序列中的每一位都不同，所以一个 a 只能和 a+1 和 a-1 换位，所以序列最后三项只有一下情况：

x    y    a[i]（1）
x    a[i] y   （2）
y    x    a[i] (*)
y    a[i] x    (*)
a[i] x    y   （3）
a[i] y    x    (*)

为了避免重复计算，打（*）的情况无需考虑。

情况（1）没有限制条件，累加 dp_{i-1,x,y} 对 dp_{i,y,a_i} 的贡献。

因为换位只能换相邻位置上的数，所以情况（1）首先要变为情况（2），然后变为情况（3）。

情况（1）变为情况（2）的条件是 |a_i-y|=1，若符合则累加 dp_{i-1,x,y} 对 dp_{i,a_i,y} 的贡献。

情况（2）变为情况（3）的条件是 |a_i-x|=1，若同时符合两次转化的条件则累加 dp_{i-1,x,y} 对 dp_{i,x,y} 的贡献。

最终答案即为 \sum dp_n。

const ll N=1e6+10,mod=998244353;
ll n,a[N];
map<pll,ll> dp[N];

bool check(ll x,ll y) {
    return abs(x-y)==1;
}

int main() {
    cin>>n;

    rep(i,1,n) cin>>a[i];

    dp[0][ {-1,-1}]=1;

    rep(i,1,n) {
        for(auto [num,sum]:dp[i-1]) {
            ll x=num.fi,y=num.se;
            (dp[i][ {y,a[i]}]+=sum)%=mod;

            if(check(y,a[i])) {
                (dp[i][ {a[i],y}]+=sum)%=mod;

                if(check(x,a[i])) (dp[i][num]+=sum)%=mod;
            }
        }
    }

    ll ans=0;

    for(auto [num,sum]:dp[n]) (ans+=sum)%=mod;

    cout<<ans;
}