ARC160F Count Sorted Arrays 题解

Coffee_zzz · 2025-10-10 18:14:58 · 题解

考虑把排列 p 拆成 n+1 个 01 串 c_0,c_2,\dots,c_n，其中 c_{i,j}=[p_j\ge i]，那么排列 p 能通过操作排好序当且仅当它拆成的 n+1 个 01 串都能通过操作排好序。

可以时刻维护每个 01 串是否合法，把每个排列 p 看成一个 00\cdots0 到 11\cdots1 的长度为 n 的路径，对合法的 01 串做一个 dp 即可得到合法的排列 p 的数量，时间复杂度 \mathcal O(nm2^n)。

感性理解，其实只有 \mathcal O(n^2) 个操作是有效的，而其他操作都不会影响 01 串的合法性。于是可以时刻维护 f_{i,j} 表示是否存在 01 串 c 满足 c_{\min(i,j)} \gt c_{\max(i,j)}，只有当询问的 f_{a_i,b_i} 为真时才重新 dp 并更新所有的 f_{a_i,j} 和 f_{b_i,j}，否则直接输出上一次询问的结果即可。

时间复杂度 \mathcal O(n^32^n)。

const int N=15,W=1<<15;
int n,m,V,f[N][N],g[W],h[W];
ll dp[W],ans=1;
bool get(int s,int x,int y){
    return ((s>>x)&1)>((s>>y)&1);
}
void solve(){
    cin>>n>>m,V=1<<n;
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) f[i][j]=1;
    for(int s=0;s<V;s++) g[s]=s;
    for(int i=0;i<=n;i++) h[((1<<i)-1)<<(n-i)]=1;
    for(int c=1;c<=m;c++){
        int x,y;
        cin>>x>>y;
        x=(x+ans)%n,y=(y+ans+ans)%n;
        if(x>y) swap(x,y);
        if(!f[x][y]){
            cout<<ans<<endl;
            continue;
        }
        for(int i=0;i<n;i++) f[x][i]=f[i][x]=f[y][i]=f[i][y]=0;
        for(int s=0;s<V;s++){
            if(get(g[s],x,y)) g[s]^=(1<<x)^(1<<y);
            for(int i=0;i<n;i++){
                if(get(g[s],min(i,x),max(i,x))) f[x][i]=f[i][x]=1;
                if(get(g[s],min(i,y),max(i,y))) f[y][i]=f[i][y]=1;
            }
        }
        for(int s=0;s<V;s++) dp[s]=0;
        dp[0]=1;
        for(int s=1;s<V;s++){
            if(!h[g[s]]) continue;
            for(int i=0;i<n;i++) if(s&(1<<i)) dp[s]+=dp[s^(1<<i)];
        }
        ans=dp[V-1];
        cout<<ans<<endl;
    }
}