P4841

每日一题。

Solution

观察模数可以发现原根为３，猜想做法为NTT，首先n个点的无向图的个数为$2^{\frac{n \times(n-1)}{2}}$（好像并无卵用），但是这样并不保证联通，那就设法使其联通，设n个点的无向连通图的个数为$f_n$，无向图的个数为$g_n$，则：
$$
g_n=\sum_{i=1}^{n}C_{n - 1}^{i-1}f_i*g_{n-i}
$$
若不好理解的话可以看作枚举1号节点连通块的大小，统计方案数。

然后我们将g展开。
$$
2^{C_{n}^{2}}=\sum_{i=1}^nC_{n - 1}^{i-1}f_i2^{C_{n - i}^{2}}\\
\frac{2^{C_{n}^{2}}}{(n-1)!}=\sum_{i=1}^n\frac{f_i}{(i-1)!}\frac{2^{C_{n-i}^2}}{(n-i)!}
$$
形式像卷积，那么定义：
$$
\begin{aligned}
F_x &= \sum_{n = 1}\frac{f_n}{(n-1)!}x^n\\
G_x &= \sum_{n=1}\frac{2^{C_n^2}}{n!}x^n\\
H_x &= \sum_{n=1}\frac{2^{C_n^2}}{(n-1)!}x^n
\end{aligned}
$$
则 $HF=G(mod x ^{n+1})$，H，G已知，再对G求个逆，$HG^{-1}$就得到了$F$

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while('0' > c || c > '9') { if(c == '-') flag = 1; c = getchar();}
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...Arg>
inline void read(T &res, Arg &...com){ read(res), read(com...);}
template <class T>
void write(T res)
{
    if(res > 9) write(res / 10);
    putchar(res % 10 + '0');
}
const int N = 4e5 + 5, mod = 1004535809;
int n;
int fac[N], inv[N];
inline int qpow(int x, int k)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = res * x % mod;
        x = x * x % mod;
        k >>= 1;
    }   
    return res;
}
inline void init()
{
    fac[0] = inv[0] = fac[1] = inv[1] = 1;
    for(int i = 2;i < N;i ++) 
        fac[i] = i * fac[i - 1] % mod, inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    for(int i = 2;i < N;i ++) inv[i] = inv[i] * inv[i - 1] % mod;
}
int f[N], g[N], H[N], le[N];
int tot, bit;
int r[N];
inline void calc(int bit)
{
    for(int i = 0;i < (1 << bit);i ++)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (bit - 1));
}
inline void NTT(int x[], int bit, int op)
{
    calc(bit);
    int tot = 1 << bit;
    for(int i = 0;i < tot;i ++) 
        if(i < r[i]) swap(x[i], x[r[i]]);
    for(int mid = 1, len, gn; mid < tot; mid <<= 1)
    {
        len = mid << 1;
        gn = qpow(3, (mod - 1) / len);
        if(~op) gn = qpow(gn, mod - 2);
        for(int i = 0;i < tot;i += len)
            for(int j = 0, a, b, g = 1;j < mid;j ++, g = g * gn % mod)
            {
                a = x[i + j], b = g * x[i + j + mid] % mod;
                x[i + j] = (a + b) % mod;
                x[i + j + mid] = (a - b + mod) % mod;
            }
    }
    if(~op) return ;
    op = qpow(tot, mod - 2);
    for(int i = 0;i < tot;i ++) x[i] = x[i] * op % mod;
}
inline int Mod(int x)
{
	return (x %= mod) < 0 ? x + mod : x;
}
inline void get_inv(int len, int a[], int b[])
{
	static int c[N];
	if(len == 1) return b[0] = qpow(a[0], mod - 2), void();
	get_inv(len >> 1, a, b);
	int bit = 0, tot;
	while((1 << bit) < (len << 1)) bit ++;
	tot = (1 << bit);
	for(int i = 0;i < tot;i ++)
		if(i < len) c[i] = a[i];
		else c[i] = 0;
	NTT(c, bit, 1), NTT(b, bit, 1);
	for(int i = 0;i < tot;i ++)
		b[i] = Mod(Mod(2ll - c[i] * b[i] % mod) * b[i]);
	NTT(b, bit, -1);
	for(int i = len;i < tot;i ++) b[i] = 0;
}
signed main()
{
    init();
    read(n);
    tot = 1;
    while(tot <= n) tot <<= 1, bit ++;
    for(int i = 1;i <= n;i ++)
        H[i] = qpow(2, i * (i - 1) / 2) * inv[i - 1] % mod;
    for(int i = 0;i <= n;i ++)
        g[i] = inv[i] * qpow(2, i * (i - 1) / 2) % mod;
    get_inv(tot, g, le);
    NTT(H, bit, 1), NTT(le, bit, 1);
    for(int i = 0;i < tot;i ++) f[i] = H[i] * le[i] % mod;
    NTT(f, bit, -1);
    write(f[n] * fac[n - 1] % mod);
    return 0;
}