题解：P10813 【MX-S2-T4】换

2025/11/12 upd：修改笔误。

好题，融入了一些自己的思路历程，可能看得会更舒服一点。

分析题目所给的操作，很难发现什么有用的性质，交换路径与

a

序列密切相关，如果不清楚交换路径，根本无法继续分析

a

单调不降的要求。

然后发现

n\le 18,m\le 500

，

n

的范围更像是状压的复杂度，允许

O(2^n)

枚举，

m

显得有些神秘，但是计算一下

m\times 2^n=131072000

，刚好跑得了，猜测是正解复杂度的一部分。

V

很大，到了

10^9

级别，说明它不能作为一个系数乘到复杂度里面，但是又和

a

元素的值域相关，而题目的操作只关心

a

的相对大小，猜测是有点钦定相对大小，用组合数分配的味道，

n

很小，计算形如

\binom {V}{n}

的组合式可以

O(n)

算。

n\le 18

有很强烈的指示性，但现在似乎还没有任何有关

2^n

的东西。

接下来的一步比较有跳跃性，考虑换一种判定一个

a

合法的方式，枚举

x\in [0,V]

，将

a_i< x

的换成

0

，反之换为

1

，如果对于每个

x

，其生成的 01 序列都合法，那么就合法。

如果想到了这个，那么离做出这题就不远了。

可能的 01 序列一共有

2^n

中，可以预处理

g_S\in \{0,1\}

，表示

S

是否是合法的 01 序列，时间复杂度

O(m \times 2^n)

。

继续考虑判定的过程，发现

x\in [0,V]

是有点宽松的，有些

x

的连续段的作用效果本质一样（生成了相同的 01 序列），其实只需要离散一下，用

x\in a

来判定即可。

考虑生成一个合法

a

序列的过程，初始时每个位置都是空的，显然合法，考虑从小到大填数，假设当前填的是

x

，每次选若干个位置填成

x

，相应的 01 序列也会发生有规律的变化（那几个位置都变为

1

），如果生成的过程中所有历经的 01 序列都是合法的，那么就能生成一个合法的

a

序列。

那么就可以考虑设计出一个 dp 转移来计数。

设

f_{i,S}

表示从大到小插入了

i

种数（只关心相对大小），当前位置的选定情况（同时也是 01 序列的情况，因为新填入的位置在 01 序列上一定为

1

）为

S

时的方案数，有转移：

\displaystyle f_{i,S}=g_S\times \sum_{T\subset S} f_{i-1,T}

这个 dp 转移是离线的，直接跑

n

次高位前缀和就行了，这里使用 fwt 实现。

那么答案就是

\displaystyle \sum_{i=1}^n \binom{V}{i} f_{i,U}

，其中

U

是全集，代表

a

的所有位置均已填数，生成了完整的

a

，原 dp 求出的是离散的方案数，还需要结合值域

V

和种类数

i

，用组合数求出真正的方案数。

时间复杂度

O(m\times 2^n+n^2\times 2^n+ n\log V)

，跑得还怪快的。

CPP

#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)
#define pr pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define bg(x) (x).begin()
#define ed(x) (x).end()

#define N 19
#define S (1<<18)+5
#define M 505
#define int long long

const int mod=1e9+7;
int n,v,m,p[M],q[M],a[N],f[N][S];
int g[S],tmp[S],tot;

inline int qpow(int a,int b=mod-2){
    int ans=1;

    while(b){
        if(b&1){
            ans=ans*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }

    return ans;
}

inline int C(int n,int m){
    if(n<m){
        return 0;
    }

    int ans=1,fac=1;

    rep(i,1,m){
        ans=ans*(n-i+1)%mod;
        fac=fac*i%mod;
    }

    return ans*qpow(fac)%mod;
}

inline void init(){
    tot=(1<<n)-1;

    rep(s,0,tot){
        rep(i,1,n){
            a[i]=(s>>(i-1))&1;
        }

        rep(i,1,m){
            if(a[p[i]]>a[q[i]]){
                swap(a[p[i]],a[q[i]]);
            }
        }

        g[s]=is_sorted(a+1,a+1+n);
    }
}

inline void fwt(int *f,int n){
    int len=2,nx=1;

    while(len<=n){
        int i=0;
        while(i<n){
            rep(j,0,nx-1){
                f[i+j+nx]=(f[i+j+nx]+f[i+j])%mod;
            }

            i+=len;
        }

        len<<=1;
        nx<<=1;
    }
}

signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>v>>m;

    rep(i,1,m){
        cin>>p[i]>>q[i];
    }

    init();

    f[0][0]=g[0];

    rep(i,1,n){
        rep(s,0,tot){
            tmp[s]=f[i-1][s];
        }

        fwt(tmp,1<<n);

        rep(s,0,tot){
            f[i][s]=(tmp[s]-f[i-1][s]+mod)%mod*g[s];
        }
    }

    int ans=0;

    rep(i,1,n){
        ans=(ans+C(v,i)*f[i][tot]%mod)%mod;
    }

    cout<<ans;

    return 0;
}

题解：P10813 【MX-S2-T4】换

文章操作

相关推荐

评论

题解：P10813 【MX-S2-T4】换