自动搬运

查看原文

来自洛谷，原作者为

	BreakPlus empty should not be filled

搬运于2025-08-24 23:01:31，当前版本为作者最后更新于2024-07-28 10:00:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一个经典 trick：考虑值域为 $\{0,1\}$ 的时候怎么做。

发现非常简单粗暴：可以直接枚举 $2^n$ 种可能性，然后模拟 $m$ 次操作，再检验操作完毕后是否有序。因此进行一个 $\mathcal{O}(m2^n)$ 的预处理。

在值域变大的情况下，我们可以将其拆成多个值域为 $\{0,1\}$ 的情况。即，对于任意 $2 \le i \le V$，将 $a$ 中 $<i$ 的数视作 $0$，$\ge i$ 的数视作 $1$，对于构造出的 $\{0, 1\}$ 序列应依然满足题意要求，而判断其是否满足是可以利用上面所预处理的内容。

设 $f_{i,j}$ 表示值域为 $i$，当前二进制数为 $j$ 的情况。转移就是每次转移到 $j$ 的一个合法子集（或超集，即倒着做，依然能得到正确结果）。

利用高维前缀和可以做到 $\mathcal{O}(nV2^n)$。

令 $g(x)$ 为 $V=x$ 的答案，$h(x)$ 为序列中恰好有 $x$ 种数的答案（相当于 $V=x$，且 $1 \sim x$ 中所有数均出现，不难发现 $x \le n$ 才有值），发现 $g(x) = \sum \limits_{k} \binom{x}{k}h(k)$，即 $g(x)$ 是关于 $x$ 的 $n$ 次多项式。

可以算 $g(x)$ 拉插一下（比较常见的套路），也可以直接算 $h(x)$ 然后算组合数。

时间复杂度 $\mathcal{O}((n^2+m)2^n)$。

ll n,V,m,p[505],q[505],f[20][1<<18],w[20];
bool vis[1<<18], t[30];
void addmod(ll &x){ if(x >= mod) x -= mod; }
void solve(){
	n=read(), V=read(), m=read();
	for(ll i=1;i<=m;i++){
		p[i]=read()-1, q[i]=read()-1;
	}
	for(ll i=0;i<(1<<n);i++){
		for(ll j=0;j<n;j++) t[j]=((i>>j)&1);
		for(ll j=1;j<=m;j++){
			if(t[p[j]] > t[q[j]]) swap(t[p[j]], t[q[j]]);
		}
		vis[i] = 1;
		for(ll j=1;j<n;j++) if(t[j-1] > t[j]) vis[i]=0;
	}
	f[0][0] = 1;
	for(ll i=1;i<=n;i++){
		for(ll j=0; j<(1<<n); j++) f[i][j] = f[i-1][j];
		for(ll j=0; j<n; j++)
			for(ll k=0; k<(1<<n); k++){
				if((k>>j)&1) continue;
				addmod(f[i][k^(1<<j)] += f[i][k]);
			}
		for(ll k=0; k<(1<<n); k++)
			if(!vis[k]) f[i][k] = 0;
	}
	ll ans = 0;
	for(ll i=0;i<=n;i++){
		for(ll j=0; j<(1<<n); j++) addmod(w[i+1] += f[i][j]);
	}
	for(ll i=1;i<=n+1;i++){
		ll xs = 1;
		for(ll j=1; j<=n+1; j++) if(j!=i) xs = xs * qpow(i-j+mod, mod-2) % mod;
		for(ll j=1; j<=n+1; j++) if(j!=i) xs = xs * (V-j+mod) % mod;
		ans = (ans + xs * w[i]) % mod; 
	}
	printf("%lld\n", ans);
}