Luogu 4841 城市规划

BZOJ 3456 权限题

太菜了推不出式子

我们设$f(n)$表示$n$个点的无向连通图的数量，那么有

$$f(n) = 2^{\binom{n}{2}} - \sum_{i = 1}^{n - 1}\binom{n - 1}{i - 1}f(i)2^{\binom{n - i}{2}}$$

思路就是全部减去不合法的，枚举$1$号点所在的联通块的大小，剩下随便生成一张无向图。

拆开组合数，简单变形一下

$$f(n) = 2^{\binom{n}{2}} - (n - 1)!\sum_{i = 1}^{n - 1}\frac{2^{\binom{n - i}{2}}}{(n - i)!}\frac{f(i)}{(i - 1)!}$$

记$h(i) = \frac{f(i)}{(i - 1)!}$，$g(i) = \frac{2^{\binom{i}{2}}}{i!}$

$$(n - 1)!h(n) = 2^{\binom{n}{2}} - (n - 1)!\sum_{i = 1}^{n - 1}g(i)h(n - i)$$

发现这个式子可以用分治FFT优化，直接上就做完了。

时间复杂度$O(nlog^2n)$。

Code：

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int N = 3e5 + ;

const ll P = 1004535809LL;

int n, lim, pos[N];

ll f[N], g[N], fac[N], inv[N], a[N], b[N];

template <typename T>

inline void read(T &X) {

    X = ; char ch = ; T op = ;

    for (; ch > ''|| ch < ''; ch = getchar())

        if (ch == '-') op = -;

    for (; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

inline ll fpow(ll x, ll y) {

    ll res = ;

    for (; y > ; y >>= ) {

        if (y & ) res = res * x % P;

        x = x * x % P;

    }

    return res;

}

template <typename T>

inline void swap(T &x, T &y) {

    T t = x; x = y; y = t;

}

inline void prework(int len) {

    int l = ;

    for (lim = ; lim <= len; lim <<= , ++l);

    for (int i = ; i < lim; i++)

        pos[i] = (pos[i >> ] >> ) | ((i & ) << (l - ));

} 

inline void ntt(ll *c, int opt) {

    for (int i = ; i < lim; i++)

        if (i < pos[i]) swap(c[i], c[pos[i]]);

    for (int i = ; i < lim; i <<= ) {

        ll wn = fpow(, (P - ) / (i << ));

        if (opt == -) wn = fpow(wn, P - );

        for (int len = i << , j = ; j < lim; j += len) {

            ll w = ;

            for (int k = ; k < i; k++, w = w * wn % P) {

                ll x = c[j + k], y = w * c[j + k + i] % P;

                c[j + k] = (x + y) % P, c[j + k + i] = (x - y + P) % P;

            }

        }

    }

    if (opt == -) {

        ll invP = fpow(lim, P - );

        for (int i = ; i < lim; i++) c[i] = c[i] * invP % P;

    }

}

inline ll getC(int x) {

    if (x < ) return ;

    return (1LL * x * (x - ) / );

}

void solve(int l, int r) {

    if (l == r) {

        f[l] = (fpow(, getC(l) % (P - )) - f[l] * fac[l - ] % P + P) % P;

        f[l] = f[l] * inv[l - ] % P;

        return;

    }

    int mid = ((l + r) >> );

    solve(l, mid);

    prework(r - l + );

    for (int i = ; i < lim; i++) a[i] = b[i] = 0LL;

    for (int i = l; i <= mid; i++) a[i - l] = f[i];

    for (int i = ; i <= r - l; i++) b[i - ] = g[i];

    ntt(a, ), ntt(b, );

    for (int i = ; i < lim; i++) a[i] = a[i] * b[i] % P;

    ntt(a, -);

    for (int i = mid + ; i <= r; i++)

        f[i] = (f[i] + a[i - l - ] % P) % P;

    solve(mid + , r);

}

int main() {

    read(n);

    fac[] = 1LL;

    for (int i = ; i <= n; i++) fac[i] = fac[i - ] * i % P;

    inv[n] = fpow(fac[n], P - );

    for (int i = n - ; i >= ; i--) inv[i] = inv[i + ] * (i + ) % P;

    for (int i = ; i <= n; i++)

        g[i] = fpow(2LL, getC(i) % (P - )) * inv[i] % P;

    solve(, n);

    printf("%lld\n", f[n] * fac[n - ] % P);

    return ;

}

巴特西

Luogu 4841 城市规划

最新文章

热门文章