设 $f(S)$ 表示考虑过的集合为 $S$ 的方案数。
如果当前的最大独立集为 $A$ ，$B$ 代表所有与 $A$ 集合中的点有边相连的点的集合，那么当前状态下 $S=A\cup B$ 。
设 $P_u$ 表示与 $u$ 距离不超过 $1$ 的点集。
考虑转移，首先确定一点 $u$ ，使得其满足 $mx(S\cup P_u)=mx(S)+1$ ，其中 $mx(S)$ 表示集合 $S$ 实质意义下的最大独立集的大小，也就是说 $mx(S)=|A|$ 。
转移的时候，如果 $mx(S\cup P_u)<mx(S)+1$ ，首先 $mx(S)+1$ 意思很明显，新加入的 $u$ 进入了独立集，$mx(S\cup P_u)<mx(S)+1$ 意味着按照原来的 $f(S\cup P_u)$ 种选法无法得到最优解，因为 $mx(S)+1$ 显然更大。于是将 $f(S\cup P_u)$ 清零然后更新 $mx(S\cup P_u),f(S\cup P_u)$ 即可。
如果 $mx(S\cup P_u)>mx(S)+1$ ，说明 $mx(S)+1$ 这种选择顺序对 $mx(S\cup P_u)$ 来言就不是最优的，不转移就好啦~
如果 $mx(S\cup P_u)=mx(S)+1$ ，直接加上当前的来自 $f(S)$ 的贡献就好啦。
对于现在需要加入的这些点，显然 $u$ 必须在现在加入，然后 $P_u-(P_u\cap S)$ 集合中的点可以放在 $u$ 后面任意一个位置加入，方案数即为 $A_{n-|S|-1}^{|P_u-(P_u\cap S)|-1}$ 。
得到转移：
$$
f(S\cup P_u)=f(S)\times A_{n-|S|-1}^{|P_u-(P_u\cap S)|-1}
$$
于是每一次只需要枚举集合 $S$ 与点 $u$ ，时间复杂度为 $O(n2^n)$ 。
当然感觉上面的有点…… 蜜汁难懂？
这里再说一种 $O(n^22^n)$ 的算法。
设 $f(S,i)$ 表示考虑过的集合为 $S$ ，集合 $S$ 的最大独立集大小为 $i$ 的方案数。
转移的时候不用 $mx$ 了，直接：
$$
f(S\cup P_u,i+1)=f(S\cup P_u,i+1)+f(S,i)\times A_{n-|S|-1}^{|P_u-(P_u\cap S)|-1}
$$
由于还需要多枚举一个 $i$ ，时间复杂度为 $O(n^22^n)$ 。
由于是 $\rm{DP}$ 计算的方案数，最后需要乘上 $\frac{1}{n^1}$ 。
Code：
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=21;
const int M=(1<<20)+2;
const ll mod=998244353;
ll dp[M],fac[N],inv[N];
int n,m,limit,mx[M],siz[M],P[N];
template <typename _Tp> inline void IN(_Tp&x) {
char ch;bool flag=0;x=0;
while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
if(flag) x=-x;
}
inline int modpow(int x,int y,int res=1) {
for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod;
return res;
}
inline ll A(int n,int m) {
if(m<0||n<0||m>n) return 0;
return 1ll*fac[n]*inv[n-m]%mod;
}
int main() {
IN(n),IN(m);
fac[0]=1,limit=(1<<n)-1;
for(int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
for(int i=0;i<=n;++i) inv[i]=modpow(fac[i],mod-2);
for(int i=1;i<=n;++i) P[i]|=(1<<(i-1));
for(int sta=1;sta<=limit;++sta)
for(int i=0;i<n;++i) siz[sta]+=(bool)(sta&(1<<i));
for(int i=1,u,v;i<=m;++i) IN(u),IN(v),P[u]|=(1<<(v-1)),P[v]|=(1<<(u-1));
dp[0]=1;
for(int sta=0;sta<=limit;++sta) if(dp[sta]) {
for(int i=1;i<=n;++i) if(!(sta&(1<<(i-1)))) {
int nxt=sta|P[i];
if(mx[nxt]>mx[sta]+1) continue;
if(mx[nxt]<mx[sta]+1) mx[nxt]=mx[sta]+1,dp[nxt]=0;
(dp[nxt]+=1ll*dp[sta]*A(n-siz[sta]-1,siz[P[i]-(P[i]&sta)]-1)%mod)%=mod;
}
}
printf("%lld\n",1ll*dp[limit]*inv[n]%mod);
return 0;
}
0 条评论