洛谷4841 城市规划

带标号无向连通图计数，使用多项式ln。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <assert.h>
#include <sstream>
#include <cstdio>
typedef long long int int_t;
using std::cin;
using std::cout;
using std::endl;
//1004535809
//const int_t mod = 998244353;
const int_t mod = 1004535809;
const int_t g = 3;
int_t power(int_t base, int_t index);
int_t upper2n(int_t x);
int_t bitReverse(int_t bits, int_t size2);
template <int_t arg>
void transform(int_t *A, int_t size);
void poly_inv(int_t *A, int_t *inv, int_t n);
void poly_log(int_t *A, int_t n);
const int_t LARGE = 1 << 22;
int_t C2(int_t x){
    return x * (x - 1) % mod * power(2,-1) % mod;
}
//4 38
 
int main()
{
//  freopen("count.in","r",stdin);
//  freopen("count.out","w",stdout);
    static int_t A[LARGE];
    static int_t fact[LARGE + 1];
    fact[0] = 1;
    int_t n;
    cin >> n;
    for(int_t i = 1;i <= n ;i++){
        fact[i] = fact[i - 1] * i % mod;
    }
    for(int_t i = 0;i <= n ;i++){
        A[i] = power(2 , i*(i-1)/2) * power(fact[i] , -1)%mod;
    }
    poly_log(A,n+1);
    for(int_t i = 0 ;i <= n  ;i ++){
        A[i] = A[i] * fact[i] % mod;
    }
    cout << A[n] << endl;
    return 0;
}
void poly_log(int_t *A, int_t n)
{
    int_t size = upper2n(2 * n);
    static int_t inv[LARGE];
    std::fill(inv, inv + size, 0);
    poly_inv(A, inv, n);
    for (int_t i = 0; i < n; i++)
    {
        A[i] = (A[i + 1] * (i + 1)) % mod;
    }
    transform<1>(A, size);
    transform<1>(inv, size);
    for (int_t i = 0; i < size; i++)
    {
        A[i] = (A[i] * inv[i]) % mod;
    }
    transform<-1>(A, size);
    for (int_t i = n - 1; i >= 1; i--)
    {
        A[i] = A[i - 1] * power(i, -1) % mod * power(size, -1) % mod;
    }
    A[0] = 0;
}
void poly_inv(int_t *A, int_t *inv, int_t n)
{
    static int_t Ax[LARGE];
    if (n == 1)
    {
        inv[0] = power(A[0], -1);
        return;
    }
    poly_inv(A, inv, n / 2 + n % 2);
    int_t size = upper2n(n * 3 - 1);
    for (int_t i = 0; i < size; i++)
    {
 
        if (i < n)
        {
            Ax[i] = A[i];
        }
        else
        {
            Ax[i] = 0;
        }
    }
    transform<1>(inv, size);
    transform<1>(Ax, size);
    for (int_t i = 0; i < size; i++)
    {
        inv[i] = (2 * inv[i] - inv[i] * inv[i] % mod * Ax[i] % mod + mod) % mod;
    }
    transform<-1>(inv, size);
    for (int_t i = 0; i < n; i++)
    {
        inv[i] = (inv[i] * power(size, -1)) % mod;
    }
    for (int_t i = n; i < size; i++)
    {
        inv[i] = 0;
    }
}
template <int_t arg >
void transform(int_t *A, int_t size)
{
    int_t size2 = log2(size);
    for (int_t i = 0; i < size; i++)
    {
        int_t x = bitReverse(i, size2);
        if (x > i)
        {
            std::swap(A[i], A[x]);
        }
    }
    for (int_t i = 2; i <= size; i *= 2)
    {
        int_t mr = power(g, arg * (mod - 1) / i);
        for (int_t j = 0; j < size; j += i)
        {
            int_t curr = 1;
            for (int_t k = 0; k < i / 2; k++)
            {
                int_t u = A[j + k];
                int_t t = A[j + k + i / 2] * curr % mod;
                A[j + k] = (u + t) % mod;
                A[j + k + i / 2] = (u - t + mod) % mod;
                curr = (curr * mr) % mod;
            }
        }
    }
}
 
int_t bitReverse(int_t bits, int_t size2)
{
    int_t result = 0;
    for (int_t i = 1; i < size2; i++)
    {
        result |= (bits & 1);
        result <<= 1;
        bits >>= 1;
    }
    return result | (bits & 1);
}
int_t upper2n(int_t x)
{
    int_t result = 1;
    while (result < x)
        result *= 2;
    return result;
}
int_t power(int_t base, int_t index)
{
    int_t result = 1;
    if (index < 0)
    {
        index *= -1;
        base = power(base, mod - 2);
    }
    while (index)
    {
        if (index & 1)
        {
            result = (result * base) % mod;
        }
        index >>= 1;
        base = (base * base) % mod;
    }
    return result;
}