loj2540 「PKUWC 2018」随机算法

pkusc 快到了……做点题涨涨 rp。

记 (f(S,i)) 表示 (S) 这个集合是决计不能选的（要么属于独立集，要么和独立集相连），或称已经考虑了的，(i) 表示此集合对应的最大独立集大小。那么枚举一下哪些点 (j) 不在 (S) 里，记 (w_i) 表示 (i) 和与之相邻的点集，则 (f(S cup w_j,i+1) leftarrow f(S cup w_j,i+1) + f(S,i) times A_{n-|S|-1}^{|w_j-(w_j cap S)|-1})。

然而对于一个集合 (S)，它的最大独立集大小是确定的，那么就来一个数组 (mx_S) 来记录其最大独立集大小。当最大独立集大小更新之时，(dp_S) 就清零然后再计数就行了。复杂度从 (O()跑得过()) 变成了 (O()更跑得过())，也就是(O(n^22^n)) 变成了 (O(n2^n))……。

改进前：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, m, w[25], uu, vv, jie[25], inv[25], dp[25][1050005], cnt[1050005];
const int mod=998244353;
int A(int x, int y){
    // if(x<y)  return 0;
    return (ll)jie[x]*inv[x-y]%mod;
}
int main(){
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        scanf("%d %d", &uu, &vv);
        uu--; vv--;
        w[uu] |= 1<<vv;
        w[vv] |= 1<<uu;
    }
    jie[0] = jie[1] = inv[0] = inv[1] = 1;
    for(int i=2; i<=n; i++){
        jie[i] = (ll)jie[i-1] * i % mod;
        inv[i] = (ll)(mod - mod / i) * inv[mod%i] % mod;
    }
    for(int i=0; i<n; i++)
        w[i] |= 1<<i;
    for(int i=2; i<=n; i++)
        inv[i] = (ll)inv[i-1] * inv[i] % mod;
    for(int i=0; i<(1<<n); i++)
        for(int j=0; j<n; j++)
            if(i&(1<<j))
                cnt[i]++;
    dp[0][0] = 1;
    for(int i=0; i<n; i++)
        for(int s=0; s<(1<<n); s++)
            if(dp[i][s])
                for(int j=0; j<n; j++)
                    if(!(s&(1<<j)))
                        dp[i+1][s|w[j]] = (dp[i+1][s|w[j]] + (ll)dp[i][s] * A(n-cnt[s]-1, cnt[w[j]-(w[j]&s)]-1)%mod) % mod;
    for(int i=n; i; i--)
        if(dp[i][(1<<n)-1]){
            cout<<(ll)dp[i][(1<<n)-1]*inv[n]%mod<<endl;
            return 0;
        }
    return 0;
}

改进后：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, m, w[25], uu, vv, jie[25], inv[25], dp[1050005], cnt[1050005];
int mx[1050005];
const int mod=998244353;
int A(int x, int y){
    // if(x<y)  return 0;
    return (ll)jie[x]*inv[x-y]%mod;
}
int main(){
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        scanf("%d %d", &uu, &vv);
        uu--; vv--;
        w[uu] |= 1<<vv;
        w[vv] |= 1<<uu;
    }
    jie[0] = jie[1] = inv[0] = inv[1] = 1;
    for(int i=2; i<=n; i++){
        jie[i] = (ll)jie[i-1] * i % mod;
        inv[i] = (ll)(mod - mod / i) * inv[mod%i] % mod;
    }
    for(int i=0; i<n; i++)
        w[i] |= 1<<i;
    for(int i=2; i<=n; i++)
        inv[i] = (ll)inv[i-1] * inv[i] % mod;
    for(int i=0; i<(1<<n); i++)
        for(int j=0; j<n; j++)
            if(i&(1<<j))
                cnt[i]++;
    dp[0] = 1;
    for(int s=0; s<(1<<n); s++)
        if(dp[s])
            for(int i=0; i<n; i++)
                if(!(s&(1<<i))){
                    int t=s|w[i];
                    if(mx[t]<mx[s]+1)   mx[t] = mx[s] + 1, dp[t] = 0;
                    if(mx[t]==mx[s]+1)
                        dp[t] = (dp[t] + (ll)dp[s] * A(n-cnt[s]-1, cnt[w[i]-(w[i]&s)]-1)%mod) % mod;
                }
    cout<<(ll)dp[(1<<n)-1]*inv[n]%mod<<endl;
    return 0;
}