博主的 BiBi 时间

感觉学到了几个卡常小技巧。（这题卡空间又卡时间可还行）

话说在 \(\mathtt{usOJ}\) 上只有 \(50pts\)。（其他都可过）

Solution

我们令 \(f[S]\) 为总集合为 \(S\) 时的答案，\(g[S]\) 是 \(S\) 集合的 \(w\) 值之和的 \(p\) 次方。

这里有一个在本蒟蒻眼中看起来并不显然的 \(DP\)：

其实就是把 \(S-S‘\) 看作新划分的一个州，把前面的分式提进去就是新划分的州的贡献。因为 \(S\) 的状态一样，所以可以把一些划分方案相加，再相乘展开其实就是答案。

然后可以把式子转化为：

其中 \(S0\bigcup S1=S,S0\bigcap S1=\emptyset\)。

关于条件二，我们套路地加上一维表示这个集合中 \(1\) 的个数。

然后对着乘就可以用 \(FWT\) 了。

Code

#include <cstdio>

const int mod = 998244353, N = 25, M = 450, siz = (1 << 21) + 5;

int n, m, p, len, u[M], v[M], w[N], deg[N], fa[N], bit[siz], cnt, val[siz], g[N][siz], f[N][siz], inv[siz];
bool ok[siz];

int read() {
    int x = 0, f = 1; char s;
    while((s = getchar()) > ‘9‘ || s < ‘0‘) if(s == ‘-‘) f = -1;
    while(s >= ‘0‘ && s <= ‘9‘) x = (x << 1) + (x << 3) + (s ^ 48), s = getchar();
    return x * f;
}

inline void add(int &x, const int y) {
    x += y;
    if(x >= mod) x -= mod;
    if(x < 0) x += mod;
}

inline int mul(const int a, const int b) {return 1ll * a * b - 1ll * a * b / mod * mod;} 

void FWT(int *f) {
    for(int i = 2; i <= len; i <<= 1)   
        for(int j = 0, p = i >> 1; j < len; j += i)
            for(int k = j; k < j + p; ++ k)
                add(f[k + p], f[k]);
}

void IFWT(int *f) {
    for(int i = 2; i <= len; i <<= 1)   
        for(int j = 0, p = i >> 1; j < len; j += i)
            for(int k = j; k < j + p; ++ k)
                add(f[k + p], -f[k]);
}

int qkpow(int x, int y) {
    int r = 1;
    while(y) {
        if(y & 1) r = mul(r, x);
        x = mul(x, x); y >>= 1;
    }
    return r;
}

int Find(const int x) {return x == fa[x] ? x : Find(fa[x]);}

void unite(const int x, const int y) {
    int u = Find(x), v = Find(y);
    fa[u] = v;
}

int main() {
    n = read(), m = read(), p = read(); len = 1 << n;
    for(int i = 1; i <= m; ++ i) u[i] = read(), v[i] = read();
    for(int i = 1; i <= n; ++ i) w[i] = read();
    for(int S = 0; S < len; ++ S) {
        cnt = 0;
        for(int i = 1; i <= n; ++ i) {
            if((1 << (i - 1)) & S) val[S] += w[i], ++ cnt;
            deg[i] = 0; fa[i] = i;
        }
        bit[S] = cnt;
        for(int i = 1; i <= m; ++ i)
            if(((1 << (u[i] - 1)) & S) && ((1 << (v[i] - 1)) & S)) {
                if(Find(u[i]) != Find(v[i])) unite(u[i], v[i]), -- cnt;
                ++ deg[u[i]]; ++ deg[v[i]];
            }
        if(cnt != 1) ok[S] = 1;
        cnt = 0;
        for(int i = 1; i <= n; ++ i) cnt += (deg[i] & 1);
        if(cnt) ok[S] = 1;
        if(ok[S]) g[bit[S]][S] = qkpow(val[S], p);
        inv[S] = qkpow(qkpow(val[S], mod - 2), p);
    }
    for(int i = 0; i <= n; ++ i) FWT(g[i]);
    f[0][0] = 1; FWT(f[0]);
    for(int i = 1; i <= n; ++ i) {
        for(int j = 0; j <= i - 1; ++ j)
            for(int k = 0; k < len; ++ k)
                add(f[i][k], mul(f[j][k], g[i - j][k]));
        IFWT(f[i]);
        for(int j = 0; j < len; ++ j) f[i][j] = (bit[j] == i) ? mul(f[i][j], inv[j]) : 0;
        if(i != n) FWT(f[i]);
    }
    printf("%d\n", f[n][len - 1]);
    return 0;
}

「WC 2018」州区划分

原文：https://www.cnblogs.com/AWhiteWall/p/13110704.html