Loj#2540.「PKUWC 2018」随机算法 | wzf2000's blog

Loj#2540.「PKUWC 2018」随机算法

Loj#2540.「PKUWC 2018」随机算法 题解

题意:

  • 求随机排列计算最大独立集的正确率。
  • $n\le 20$。

题解:

  • 考虑用 $dp[S]$ 表示当前已确定点集为 $S$ 的点的相对顺序最大独立集大小为 $mx[S]$ 的方案数。
  • 其中与最大独立集中的点相关的点已加入 $S$。
  • 每次转移加入一个点 $i$ 到最大独立集。
  • 令 $to[i]$ 表示与 $i$ 有连边的点集。
  • 那么转移方程:$dp[s\cup to[i]\cup\{i\}]+=dp[s]\times A_{|to[i]|-|to[i]\&S|}^{n-|S|-1}$。
  • 时间复杂度 $O(2^nn)$。

代码:

#include <bits/stdc++.h>
#define gc getchar()
using namespace std;
typedef long long ll;
const int mod=998244353;
const int N=21;
int n,m,to[N],bit[N],dp[1<<N],Max[1<<N],num[1<<N],jc[N],inv[N],jc_inv[N];
int read()
{
    int x=1;
    char ch;
    while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
    int s=ch-'0';
    while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
    return s*x;
}
int A(int n,int m)
{
    return (ll)jc[n]*jc_inv[n-m]%mod;
}
int main()
{
    jc[0]=1;
    for (int i=1;i<N;i++) jc[i]=(ll)jc[i-1]*i%mod;
    inv[1]=1;
    for (int i=2;i<N;i++) inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
    jc_inv[0]=1;
    for (int i=1;i<N;i++) jc_inv[i]=(ll)jc_inv[i-1]*inv[i]%mod;
    bit[0]=1;
    for (int i=1;i<N;i++) bit[i]=bit[i-1]<<1;
    n=read(),m=read();
    for (int i=1;i<=m;i++)
    {
        int x=read()-1,y=read()-1;
        to[x]|=bit[y],to[y]|=bit[x];
    }
    for (int i=0;i<bit[n];i++)
        for (int j=0;j<n;j++)
            if (i>>j&1) num[i]++;
    dp[0]=1;
    for (int i=0;i<bit[n];i++)
        if (dp[i])
            for (int j=0;j<n;j++)
                if (!(i>>j&1))
                {
                    int k=i|to[j]|bit[j];
                    if (Max[i]+1>Max[k]) Max[k]=Max[i]+1,dp[k]=0;
                    if (Max[i]+1==Max[k])
                        dp[k]=(dp[k]+(ll)dp[i]*A(n-num[i]-1,num[to[j]]-num[to[j]&i]))%mod;
                }
    printf("%d\n",(ll)dp[bit[n]-1]*jc_inv[n]%mod);
    return 0;
}