【LOJ】 #2540. 「PKUWC2018」随机算法

题解

感觉极其神奇的状压dp

\(dp[i][S]\)表示答案为i，然后不可选的点集为S

我们每次往答案里加一个点，然后方案数是，设原来可以选的点数是y，新加入一个点后导致了除了新加的点之外x个点不能选，那么方案就是把x个数在y - 1（由于空余位置的第一个要放我们选的那个点）个位置里任意排列，方案数是\(A^{y - 1}_{x}\)

复杂度是\(O(n^2 2^n)\)但是由于我们及时的break掉它跑的飞快= =

代码

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <queue>

#include <cmath>

#define enter putchar('\n')

#define space putchar(' ')

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define pii pair<int,int>

#define eps 1e-7

#define MAXN 3005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 + c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {putchar('-');x = -x;}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

const int MOD = 998244353;

int N,M;

int fac[25],invfac[25],inv[25];

int AD[25],dp[25][(1 << 20) + 5],cnt[(1 << 20) + 5],A[25][25];

bool vis[(1 << 20) + 5];

int lowbit(int x) {

    return x & (-x);

}

int mul(int a,int b) {

    return 1LL * a * b % MOD;

}

int inc(int a,int b) {

    return a + b >= MOD ? a + b - MOD : a + b;

}

void Init() {

    inv[1] = 1;

    for(int i = 2 ; i <= 20 ; ++i) inv[i] = mul(inv[MOD % i],MOD - MOD / i);

    invfac[0] = fac[0] = 1;

    for(int i = 1 ; i <= 20 ; ++i) fac[i] = mul(fac[i - 1],i),invfac[i] = mul(invfac[i - 1],inv[i]);

    read(N);read(M);

    int u,v;

    for(int i = 1 ; i <= M ; ++i) {

	read(u);read(v);

	AD[u] |= 1 << v - 1;

	AD[v] |= 1 << u - 1;

    }

    for(int i = 1 ; i <= N ; ++i) AD[i] |= 1 << i - 1;

    for(int i = 1 ; i < (1 << N) ; ++i) cnt[i] = cnt[i - lowbit(i)] + 1;

}

void Solve() {

    vis[0] = 1;

    int c = 0;

    for(int i = 1 ; i < (1 << N) ; ++i) {

	for(int j = 1 ; j <= N ; ++j) {

	    if(i >> (j - 1) & 1) {

		if(!(AD[j] & (i ^ (1 << j - 1)))) {

		    vis[i] |= vis[i ^ (1 << j - 1)];

		}

		break;

	    }

	}

	if(vis[i]) c = max(c,cnt[i]);

    }

    for(int i = 0 ; i <= N ; ++i) {

	for(int j = 0 ; j <= i ; ++j) {

	    A[i][j] = mul(fac[i],invfac[i - j]);

	}

    }

    dp[0][0] = 1;

    for(int i = 0 ; i < N ; ++i) {

	for(int S = 0 ; S < (1 << N) ; ++S) {

	    if(!dp[i][S]) continue;

	    for(int j = 1 ; j <= N ; ++j) {

		if((1 << j - 1) & S) continue;

		dp[i + 1][S | AD[j]] = inc(dp[i + 1][S | AD[j]],

					   mul(dp[i][S],A[N - cnt[S] - 1][cnt[S | AD[j]] - cnt[S] - 1]));

	    }

	}

    }

    int ans = 0;

    for(int S = 0 ; S < (1 << N) ; ++S) {

	ans = inc(ans,dp[c][S]);

    }

    out(mul(ans,invfac[N]));enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Init();

    Solve();

}

巴特西

【LOJ】 #2540. 「PKUWC2018」随机算法

题解

代码

最新文章

热门文章