题目传送门 qwq

设 $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;
}
分类: 文章

Qiuly

QAQ

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注