【题解】CF1466H Finding satisfactory solutions
题意：
由于洛谷目前的中文题面过于简洁，导致看完中文题面之后本题就已经解决了一半，所以我来简单翻译一下英文题面。
有 $n$ 个人，第 $i$ 个人初始的时候手上有物品 $i$。
他们之间可以交换物品，每个人恰好拿到一个物品。而每个人有对物品的偏好，第 $i$ 个人的偏好用排列 $\{s_{i,n}\}$ 来表示。第 $i$ 个人相较物品 $y$ 更喜欢物品 $x$，当且仅当在排列 $\{s_{i,n}\}$ 中 $x$ 在 $y$ 之前。
对于一个物品交换的排列 $p$，表示第 $i$ 个物品最后到了 $p_i$ 的手上。对于一个非空的，人的子集 $S$，如果子集内部的人，使用子集内所有人初始手上的物品进行交换，可以达到以下结果：
- 不存在一个人 $x\in S$，在子集内交换后得到物品 $y\in S$，且第 $x$ 个人比起 $y$ 更喜欢 $p_x$。
- 至少存在一个人 $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$ 个点的有向图，有两类边：
- 如果 $j$ 在排列 $\{s_{i,n}\}$ 中比 $p_i$ 靠前，存在黑边 $i \to j$。
- 白边 $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;
}