【题解】CF1466H Finding satisfactory solutions

题目链接:CF1466H Finding satisfactory solutions

题意:

由于洛谷目前的中文题面过于简洁,导致看完中文题面之后本题就已经解决了一半,所以我来简单翻译一下英文题面。

有 $n$ 个人,第 $i$ 个人初始的时候手上有物品 $i$。
他们之间可以交换物品,每个人恰好拿到一个物品。而每个人有对物品的偏好,第 $i$ 个人的偏好用排列 $\{s_{i,n}\}$ 来表示。第 $i$ 个人相较物品 $y$ 更喜欢物品 $x$,当且仅当在排列 $\{s_{i,n}\}$ 中 $x$ 在 $y$ 之前。
对于一个物品交换的排列 $p$,表示第 $i$ 个物品最后到了 $p_i$ 的手上。对于一个非空的,人的子集 $S$,如果子集内部的人,使用子集内所有人初始手上的物品进行交换,可以达到以下结果:

  1. 不存在一个人 $x\in S$,在子集内交换后得到物品 $y\in S$,且第 $x$ 个人比起 $y$ 更喜欢 $p_x$。
  2. 至少存在一个人 $x\in S$,在子集内交换后得到物品 $y\in S$,且第 $x$ 个人比起 $p_x$ 更喜欢 $y$。

则称这样一个子集 $S$ 是“不稳定”的。一个物品交换的排列 $p$ 是“稳定”的,当且仅当不存在一个“不稳定”的子集。
现给出一个物品交换的排列 $p$,求有多少种 $\{\{s_{1,n}\},\{s_{2,n}\}\cdots,\{s_{n,n}\}\}$ 使得 $p$ 是“稳定”的。
(可以证明,对于一组 $\{\{s_{1,n}\},\{s_{2,n}\}\cdots,\{s_{n,n}\}\}$,恰好存在一个 $p$ 是“稳定”的)
$1\le n\le 40$。

“不稳定”的定义可以认为是,如果一个子集内部的人,可以在内部进行交换之后,使得没有人拿到的物品变劣,且至少有一个人拿到的物品变优,则这个子集就不乐意了。

首先不妨考虑一下,为什么对于一组 $\{\{s_{1,n}\},\{s_{2,n}\}\cdots,\{s_{n,n}\}\}$,其“稳定”的 $p$ 有且仅有一组。

首先,我们不妨先让每一个人选择自己最喜欢的物品(在图上连边),则我们会得到一棵基环内向树森林。考虑有哪些人所得到的物品可能需要变化。

如果环上的某一个人 $x$ 所得的物品变化了,则这个环就会变成一个“不稳定”的子集,因为其他人都没有变劣,而 $x$ 得到的物品变优了。

因此,环上边是不能删除的。所以不妨直接把环上的点,和连到环上的边删除,递归进行问题。

最后我们一定会得到若干环,这就是唯一合法的 $p$。

那么从这个角度转化一下题意,可以把题意转化为:

给定 n 和排列 $\{p_n\}$。对于 $1 \le i \le n$,有排列 $\{s_{i,n}\}$。

考虑 $n$ 个点的有向图,有两类边:

  1. 如果 $j$ 在排列 $\{s_{i,n}\}$ 中比 $p_i$ 靠前,存在黑边 $i \to j$。
  2. 白边 $i \to p_i$。

这张图是合法的,当且仅当所有环中都不存在黑边。

求有多少种 $\{\{s_{1,n}\},\{s_{2,n}\}\cdots,\{s_{n,n}\}\}$ 使得这张图是合法的。

这是因为,如果环上存在黑边,则这个环上的点按照这个环来交换物品之后,黑边上的人会变优,白色边上的点不变劣,这就出现了一个“不稳定”的子集。

现在考虑从 $p$ 入手。显然 $p$ 由若干环构成,根据上述表述,我们知道最后如果把每个环看作一个点,会连出一张 $\text{DAG}$。

对于一张 $\text{DAG}$,他自然对应很多种 $\{\{s_{1,n}\},\{s_{2,n}\}\cdots,\{s_{n,n}\}\}$。具体来说,如果设一个点 $i$ 连出的黑边条数为 $d_i$,则一张 $\text{DAG}$ 对应的排列集合个数应该是:

$$ \prod_{i=1}^n d_i! \times (n-d_i-1)! $$

这是因为黑边连向的元素在 $\{s_{i,n}\}$ 中一定在 $p_i$ 之前,但他们之间可以任意排列。没有出现的边所代表的元素也可以任意排列。

于是,我们不难得到一个状压 $\text{dp}$。设 $\text{dp}_S$ 表示将 $S$ 的生成子图连成一个 $\text{DAG}$ 的权值之和。那么有:

$$ \text{dp}_S=\sum_{T\subset S} (-1)^{|S-T|-1}\text{dp}_{T}\times f(T,S-T) $$

其中 $f(A,B)$ 表示将集合 $B$ 连向集合 $A$ 所贡献的权值和。实际上就是枚举最后一层有哪些元素,然后前面往最后一层连边。

前面的 $(-1)^{|S-T|-1}$ 是容斥系数,这是因为对于每一种方案,会枚举出最后一层的所有子集,这个要通过容斥来去掉。

不难发现,$f(A,B)$ 与 $A,B$ 具体是多少没有关系,而只与 $|A|,|B|$ 相关。且由于 $B$ 中每个元素向 $A$ 连边都是独立的,所以我们可以直接 $|B|$ 次方。

于是就只需要算一个节点向一个大小为 $s$ 的集合连边的权值和 $f(s)$。

不妨枚举连了多少条边,可得:

$$ f(s)=\sum_{i=0}^s \binom{s}{i} i!(n-i-1)! $$

推一推组合式子可以得到:

$$ f(s)=\dfrac{n!}{n-s} $$

这样,我们就得到了一个 $\mathcal{O}(3^c)$ 的解法。但是这明显不够,我们还需要继续优化。

容易发现的一点是,对于相同大小的环,我们并不关系到底是哪几个环,因为所有贡献只和大小相关。

因此可以直接把状态压缩为“每种大小的环分别有多少个”,做上述转移的时候,在枚举子集之后乘上一个组合数。

这样,状态就被压缩了,对于 $n$ 个点,状态个数 $\max g(n)$ 是以下问题的解:

$\sum_{i=1}^n c_i\times i = n$,$\text{maximize }\prod_{i=1}^n (c_i+1)$

这个东西在 $n=40$ 的时候只有 $1440$,所以跑的很快。

//Code By CXY07 - It's My Fiesta.
#include<bits/stdc++.h>
using namespace std;

//#define FILE
#define int long long
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define popc(x) __builtin_popcount(x)
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'

const int MAXN = 50;
const int SIZ = 2010;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;

int n, m, lim;
int p[MAXN], _cnt[MAXN], cnt[MAXN];
int cir[MAXN], c, fac[MAXN], cur[MAXN], pre[MAXN];
int C[MAXN][MAXN], F[MAXN][MAXN];
int dp[SIZ];

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); }
    return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) { return read(x) && read(y...); }

void Init() {
    static bool vis[MAXN];
    fac[0] = 1;
    for(int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;
    function< int (int, int) > DFS = [&](int x, int siz) {
        if(vis[x]) return siz;
        vis[x] = true; return DFS(p[x], siz + 1);
    };
    for(int i = 1; i <= n; ++i) 
        if(!vis[i]) _cnt[DFS(i, 0)]++;
    for(int i = 1; i <= n; ++i)
        if(_cnt[i]) { cir[++c] = i; cnt[c] = _cnt[i]; }
    C[0][0] = 1;
    for(int i = 1; i <= n; ++i) {
        C[i][0] = 1;
        for(int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }
    for(int i = 0; i < n; ++i) {
        F[i][0] = F[i][1] = 1;
        for(int j = 1; j <= n; ++j) if(j != n - i) (F[i][1] *= j) %= mod;
        for(int j = 2; j <= n; ++j) F[i][j] = (F[i][j - 1] * F[i][1]) % mod;
    }
    for(int i = 1; i <= c; ++i) lim = lim * (cnt[i] + 1) + cnt[i];
}

int encode(int *a) {
    int res = 0;
    for(int i = 1; i <= c; ++i) res = res * (cnt[i] + 1) + a[i];
    return res;
}

void decode(int a) {
    for(int i = c; i >= 1; --i) {
        cur[i] = a % (cnt[i] + 1);
        a /= (cnt[i] + 1);
    }
}

void nxt(int *a) {
    a[1]++;
    for(int i = 1; i <= c; ++i) {
        if(a[i] > cnt[i]) a[i] = 0, a[i + 1]++;
        else break;
    }
}

signed main () {
#ifdef FILE
    freopen("CF1466H.in", "r", stdin);
    freopen("CF1466H.out", "w", stdout);
#endif
    read(n);
    for(int i = 1; i <= n; ++i) read(p[i]);
    Init(); dp[0] = 1;
    for(int i = 0, j, sumi, sumj, cnti, cntj, coe; i <= lim; ++i) {
        decode(i); memset(pre, 0, sizeof pre);
        sumi = cnti = 0;
        for(int p = 1; p <= c; ++p) cnti += cur[p], sumi += cur[p] * cir[p];
        while(1) {
            j = encode(pre); if(i == j) break;
            sumj = cntj = 0, coe = 1;
            for(int p = 1; p <= c; ++p) cntj += pre[p], sumj += pre[p] * cir[p];
            for(int p = 1; p <= c; ++p) coe = coe * C[cur[p]][pre[p]] % mod;
            if(!((cnti - cntj) & 1)) coe = mod - coe;
            (dp[i] += dp[j] * coe % mod * F[sumj][sumi - sumj]) %= mod;
            nxt(pre);
        }
    }
    printf("%lld\n", dp[lim]);
    return 0;
}
添加新评论