题目传送门：城市规划
题解
如果无向连通图数量是 (F(x)) ，那么如果 (exp(F(x))=G(x)) 的话， (G(x)) 就是无向图数量。
所以，直接使用 (F(x)=ln (G(x))) 。完了。
总结：
- 简单的多项式 (exp) 组合意义。
代码
可以得到如下代码（写个多项式 (ln) 就行了）：
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = (1 << 18) + 5, Mod = 1004535809, G = 3;
int ad(int x, int y) { return ((x + y) > Mod) ? (x + y - Mod) : (x + y); }
int dc(int x, int y) { return ((x - y) < 0) ? (x - y + Mod) : (x - y); }
int ml(int x, int y) { return (ll) x * y % Mod; }
int ksm(int x, ll y) {
int ret = 1;
for (; y; y >>= 1, x = ml(x, x))
if (y & 1) ret = ml(ret, x);
return ret;
}
int rev[N], g[25], ig[25];
void Init() {
for (int i = 0; i <= 21; ++i) g[i] = ksm(G, (Mod - 1) >> i);
for (int i = 0; i <= 21; ++i) ig[i] = ksm(g[i], Mod - 2);
}
void GetRev(int up) {
for (int i = 0; i < up; ++i)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (up >> 1) : 0);
}
int GetUp(int deg) {
int ret = 1;
while (ret <= deg) ret <<= 1;
return ret;
}
void Clear(int *F, int L, int R) { //[L, R)
for (int i = L; i < R; ++i) F[i] = 0;
}
void Copy(int *G, const int *F, int L, int R) { //[L, R)
for (int i = L; i < R; ++i)
G[i] = F[i];
}
void NTT(int *F, int up, int ty) {
for (int i = 0; i < up; ++i)
if (i < rev[i]) swap(F[i], F[rev[i]]);
int cnt = 1;
for (int l = 2; l <= up; l <<= 1) {
int h = l >> 1, w = (ty > 0) ? g[cnt] : ig[cnt];
for (int b = 0; b < up; b += l) {
int wi = 1;
for (int p = b; p < b + h; ++p) {
int tt = ml(F[p + h], wi);
F[p + h] = dc(F[p], tt);
F[p] = ad(F[p], tt);
wi = ml(wi, w);
}
}
++cnt;
}
if (ty < 0) {
int tt = ksm(up, Mod - 2);
for (int i = 0; i < up; ++i) F[i] = ml(F[i], tt);
}
}
void Inv(const int *F, int *G, int up) {
if (up == 1) {
G[0] = ksm(F[0], Mod - 2);
return ;
}
Inv(F, G, up >> 1);
Clear(G, up >> 1, up << 1);
static int T[N];
Copy(T, F, 0, up);
Clear(T, up, up << 1);
GetRev(up << 1);
NTT(T, up << 1, 1);
NTT(G, up << 1, 1);
for (int i = 0; i < (up << 1); ++i)
G[i] = dc(ml(2, G[i]), ml(ml(G[i], G[i]), T[i]));
NTT(G, up << 1, -1);
}
void Der(int *F, int up) {
for (int i = 0; i <= up - 2; ++i)
F[i] = ml(F[i + 1], i + 1);
F[up - 1] = 0;
}
void Int(int *F, int up) {
for (int i = up - 2; i >= 0; --i)
F[i + 1] = ml(F[i], ksm(i + 1, Mod - 2));
F[0] = 0;
}
void Ln(const int *F, int *G, int up) {
static int T[N];
Copy(T, F, 0, up);
Der(T, up);
Inv(F, G, up);
Clear(G, up, up << 1);
Clear(T, up, up << 1);
NTT(G, up << 1, 1);
NTT(T, up << 1, 1);
for (int i = 0; i < (up << 1); ++i)
G[i] = ml(G[i], T[i]);
NTT(G, up << 1, -1);
Int(G, up);
}
int n, A[N], B[N], fac[N];
int main() {
Init();
scanf("%d", &n);
fac[0] = 1;
for (int i = 1; i <= n; ++i) fac[i] = ml(fac[i - 1], i);
A[0] = 1;
A[1] = 1;
for (int i = 2; i <= n; ++i) A[i] = ml(ksm(2, (ll) i * (i - 1ll) / 2ll), ksm(fac[i], Mod - 2));
Ln(A, B, GetUp(n));
printf("%d
", ml(B[n], fac[n]));
return 0;
}