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

_2eyks · 2025-08-19 19:37:54 · 题解

场上半小时才出思路，我太菜了。

注意到 x 只可能与 x\pm1 交换，所以记录每个数出现的位置 t_x，然后扫一遍就行。

考虑给每对能互相交换的数连无向边，因为是无向的，所以从前往后扫这个数列。

每扫到一个下标 i，令 x=a_i，考虑分别讨论连边 x+1,x-1 的情况。以与 x-1 连边为例：

• 如果 t_{x-1} 与 i-1 有连边，则 x-1 这个数可以被移动到 i-1 位置，那么 x-1 就可以与 x 交换，遂连边。
• 如果 t_{x-1} 与 i-2 有连边，则如果 a_{i-1}=x+1，那么也连边。

与 x+1 连边的情况类似。

然后你把连边放并查集上，猜测答案是连通块大小对应 fibonacci 数的乘积，你发现这在赛时能过联考所有大样例。某大神说可用数学归纳法证明。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pii pair<int,int>
#define yes cout<<'Y'<<'E'<<'S'<<endl
#define no cout<<'N'<<'O'<<endl
#define im cout<<-1<<endl
#define debug(x) cerr<<#x<<':'<<x<<endl
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define ro(i,r,l) for(int i=r;i>=l;i--)
#define couts(x) cout<<setprecision(x)<<fixed
void Ios(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const int N=1e6+5,M=998244353;
int n,a[N],f[N],r[N];
map<int,int>to;
namespace dsu{
    int fa[N],siz[N];
    int find(int x){
        if (fa[x]==x) return x;
        return fa[x]=find(fa[x]);
    }
    void merge(int x,int y){
        if (r[x]==x) r[x]=y;
        // cout<<x<<' '<<y<<'\n';
        x=find(x),y=find(y);
        if (x==y) return;
        fa[y]=x,siz[x]+=siz[y];
    }
}
using namespace dsu;
void solve(){
    cin>>n;
    to.clear();
    fo(i,1,n){
        cin>>a[i];
        fa[i]=i,siz[i]=1,r[i]=i;
        to[a[i]]=i;
        if (i>1){
            if (abs(a[i-1]-a[i])==1)
                merge(i-1,i);
            if (to[a[i]-1]){
                int x=to[a[i]-1];
                if (r[x]<=x+1){
                    if (r[x]==i-1)
                        merge(x,i);
                    else if (r[x]==i-2&&abs(a[i-1]-a[i])==1)
                        merge(x,i);
                }
            }
            if (to[a[i]+1]){
                int x=to[a[i]+1];
                if (r[x]<=x+1){
                    if (r[x]==i-1)
                        merge(x,i);
                    else if (r[x]==i-2&&abs(a[i-1]-a[i])==1)
                        merge(x,i);
                }
            }
        }
    }
    int rs=1;
    fo(i,1,n)
        if (find(i)==i)
            rs=rs*f[siz[i]]%M;
    cout<<rs<<'\n';
}
signed main(){
    freopen("disappear.in","r",stdin);
    freopen("disappear.out","w",stdout);
    Ios();
    f[0]=f[1]=1;
    fo(i,2,N-1)
        f[i]=(f[i-1]+f[i-2])%M;
    int T=1;
    // cin>>T>>T;
    while (T--)
        solve();
    return 0;
}
//30 4 5 3 1 2 13 14 12 11 9 10 7 8 40 22 20 21