题目
思路&算法
我们设点数为(n)的简单图的数量为(f_n)， 点数为(n)的简单连通图有(g_i)个
于是我们知道，从(n)个点中选(2)个点有(n choose 2)种选法， 而对于两个点可以连边或不连， 于是(f_n = 2^{n choose 2})
同时， (f_n)还满足(f_n = sumlimits_{i = 1}^{n}{n-1 choose {i-1}}g_if_{n-i})， 因为我们可以考虑钦定某一点为联通块中的一点， 然后从剩余的点中找(i-1)个点， 练成一个联通块， 剩下随便， 然后(i)取遍(1 sim n)中的所有数后的和为(f_n)。
于是， 我们来愉快的推式子
[2^{n choose 2} = sum_{i = 1}^{n}{{n-1} choose {i-1}}g_if_{n-i}
]
把(f_n = 2^{n choose 2})带入
[egin{align*}
2^{n choose 2} &= sum_{i = 1}^{n}{{n-1} choose {i-1}}2^{{n-i;} choose {2}}g_i\
2^{n choose 2} &= sum_{i = 1}^{n}frac{{(n-1)!}/{(i-1)!}}{(n-i)!}g_i2^{{n-i;} choose 2}\
2^{n choose 2} &= sum_{i = 1}^{n}frac{{(n-1)!}}{(n-i)!(i-1)!}g_i2^{{n-i;} choose {2}}\
2^{n choose 2} &= (n-1)!sum_{i = 1}^{n}frac{1}{(i-1)!(n-i)!}g_i2^{{n-i;} choose {2}}\
frac{2^{{n} choose 2}}{(n-1)!} &= sum_{i=1}^{n}frac{1}{(n-i)!(n-1)!}g_i2^{{n-i;} choose {2}}\
frac{2^{{n} choose 2}}{(n-1)!} &= sum_{i=1}^{n} left(frac{1}{n-i}2^{{n-i;} choose {2}}
ight)left(frac{1}{(i-1)!}g_i
ight)
end{align*}
]
这是一个卷积
我们令
(A(x) = sumlimits_{i = 1}^{n}frac{1}{(i-1)!}2^{i choose 2}x^i)， (B(x) = sumlimits_{i = 1}^{n}frac{1}{(i-1)!}g_{i-1}x^i)， (C(x) = sumlimits_{i = 0}^{n-1}frac{1}{i!}2^{i choose 2}x^i)
于是(C(x) = A(x)B(x))
然后(B(x) = A(x)C^{-1}(x))
代码
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 520010;
const LL mod = 1004535809LL;
inline LL power(LL a, LL n, LL mod)
{ LL Ans = 1;
a %= mod;
while (n)
{ if (n & 1) Ans = (Ans * a) % mod;
a = (a * a) % mod;
n >>= 1;
}
return Ans;
}
struct Mul
{ int rev[N];
int Len, Bit;
LL wn[N];
void getReverse()
{ for (int i = 0; i < Len; i++)
rev[i] = (rev[i>>1] >> 1) | ((i&1) * (Len >> 1));
}
void NTT(LL * a, int opt)
{ getReverse();
for (int i = 0; i < Len; i++)
if (i < rev[i]) swap(a[i], a[rev[i]]);
int cnt = 0;
for (int i = 2; i <= Len; i <<= 1)
{ cnt++;
for (int j = 0; j < Len; j += i)
{ LL w = 1LL;
for (int k = 0; k < (i>>1); k++)
{ LL x = a[j + k];
LL y = (w * a[j + k + (i>>1)]) % mod;
a[j + k] = (x + y) % mod;
a[j + k + (i>>1)] = (x - y + mod) % mod;
w = (w * wn[cnt]) % mod;
}
}
}
if (opt == -1)
{ reverse(a + 1, a + Len);
LL num = power(Len, mod-2, mod);
for (int i = 0; i < Len; i++)
a[i] = (a[i] * num) % mod;
}
}
void getLen(int l)
{ Len = 1, Bit = 0;
for (; Len <= l; Len <<= 1) Bit++;
}
void init()
{ for (int i = 0; i < 22; i++)
wn[i] = power(3, (mod-1) / (1LL << i), mod);
}
} Calc;
LL tmp1[N], tmp2[N];
void cpy(LL * A, LL * B, int len1, int len2)
{ for (int i = 0; i < len1; i++) A[i] = B[i];
for (int i = len1; i < len2; i++) A[i] = 0;
}
void getInv(LL * A, LL * B, int Len)
{ B[0] = power(A[0], mod-2, mod);
for (register int i = 2; i <= Len; i <<= 1)
{ int l = i << 1;
cpy(tmp1, A, i, l);
cpy(tmp2, B, i>>1, l);
Calc.Len = l;
Calc.NTT(tmp1, 1);
Calc.NTT(tmp2, 1);
for (register int j = 0; j < l; j++)
tmp1[j] = ((2LL * tmp2[j]) % mod + mod - ((tmp2[j] * tmp2[j]) % mod * tmp1[j]) % mod) % mod;
Calc.NTT(tmp1, -1);
for (register int j = 0; j < i; j++)
B[j] = tmp1[j];
}
}
LL A[N], B[N], Ans[N];
LL fac[N];
int main()
{ int n;
scanf("%d", &n);
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = (fac[i-1] * (LL) i) % mod;
Calc.getLen(n);
int len = Calc.Len;
Calc.init();
A[0] = 1;
for (int i = 1; i < n; i++)
A[i] = (power(2LL, (LL) i * (LL) (i-1) / 2LL, mod) * power(fac[i], mod-2, mod)) % mod;
B[0] = 0;
for (int i = 1; i <= n; i++)
B[i] = (power(2LL, (LL) i * (LL) (i-1) / 2LL, mod) * power(fac[i-1], mod-2, mod)) % mod;
getInv(A, Ans, len);
Calc.Len = len << 1;
Calc.NTT(Ans, 1);
Calc.NTT(B, 1);
for (int i = 0; i < Calc.Len; i++)
Ans[i] = (Ans[i] * B[i]) % mod;
Calc.NTT(Ans, -1);
printf("%lld
", (Ans[n] * fac[n-1]) % mod);
return 0;
}