标签：frac 函数 int LL 生成 binom inv mod
城市规划
\[设G(n)表示n个点的有标号无向图数量,我们知道，G(n)=2^{\binom{n}{2}}\\
设F(n)表示n个点的有标号无向联通图数量,显然\\
\text{我们枚举一号店所在的联通块大小，剩下部分是任意图，合起来就是n个点的有标号无向图个数，然后暴力拆二项式系数}\\
\begin{aligned}
G(n)&=\sum_{i=1}^n{\binom{n-1}{i-1}F(i)G(n-i)}\\
2^{\binom{n}{2}}&=\sum_{i=1}^n{\frac{(n-1)!}{(n-i)!(i-1)!}F(i)2^{\binom{n-i}{2}}}\\
\frac{2^{\binom{n}{2}}}{(n-1)!} &=\sum_{i=1}^n{\frac{2^{\binom{n-i}{2}}}{(n-i)!}\frac{F(i)}{(i-1)!}}\\
\end{aligned}
\\
设A(n)=\frac{2^{\binom{n}{2}}}{(n-1)!}\\
设B(n)=\frac{2^{\binom{n}{2}}}{n!}\\
设C(n)=\frac{F(n)}{(n-1)!}\\
A=B*C\\
C=A*B^{-1}\\
我们做一遍多项式求逆，再乘上(n-1)!就可以求出f
\]
代码
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 1004535809, G = 3, Gi = 334845270;
const int maxn = 8e5 + 5;
LL fsp(LL a, LL b = mod - 2)
{
LL s = 1;
while (b)
{
if (b & 1)
s = s * a % mod;
b >>= 1;
a = a * a % mod;
}
return s;
}
int r[maxn];
void NTT(LL *a, int limit, int type)
{
for (int i = 0; i < limit; i++)
if (i < r[i])
swap(a[i], a[r[i]]);
for (int mid = 1; mid < limit; mid <<= 1)
{
LL Wn = fsp(type == 1 ? G : Gi, (mod - 1) / (mid << 1));
for (int j = 0; j < limit; j += (mid << 1))
{
LL w = 1;
for (int k = 0; k < mid; k++, w = Wn * w % mod)
{
LL x = a[j + k], y = w * a[j + k + mid] % mod;
a[j + k] = (x + y) % mod;
a[j + k + mid] = (x - y + mod) % mod;
}
}
}
}
LL a[maxn], x[maxn], y[maxn];
LL b[2][maxn];
void mul(LL *a, LL *b, LL *ans, int n, int m)
{
memset(x, 0, sizeof(x));
memset(y, 0, sizeof(y));
for (int i = 0; i <= n; i++)
x[i] = a[i];
for (int i = 0; i <= m; i++)
y[i] = b[i];
LL limit = 1, L = 0;
while (limit <= n + m)
limit <<= 1, L++;
for (int i = 0; i < limit; i++)
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1));
NTT(x, limit, 1), NTT(y, limit, 1);
for (int i = 0; i < limit; i++)
ans[i] = x[i] * y[i] % mod;
NTT(ans, limit, -1);
LL inv = fsp(limit);
for (int i = 0; i < limit; i++)
ans[i] = ans[i] * inv % mod;
}
void invv(LL *a, LL *ans,int n)
{
int bas = 1;
int cur = 0;
b[cur][0] = fsp(a[0]);
while (bas <= (n << 1))
{
cur ^= 1;
memset(b[cur], 0, sizeof(b[cur]));
for (int i = 0; i < bas; i++)
{
b[cur][i] = (b[cur^ 1][i ] << 1) % mod;
}
mul(b[cur ^ 1], b[cur ^ 1], b[cur ^ 1], bas, bas);
mul(b[cur ^ 1], a, b[cur ^ 1], bas, bas);
for (int i = 0; i < bas; ++i)
b[cur][i] = (b[cur][i] - b[cur ^ 1][i]+mod) % mod;
bas <<= 1;
}
for(int i=0;i<=n;i++)ans[i]=b[cur][i];
}
LL fac[maxn],inv[maxn];
LL A[maxn],B[maxn],D[maxn];
LL C(int n,int m){
if(m>n)return 0;
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
fac[0]=inv[0]=1;
for(int i=1;i<=200000;i++){
fac[i]=fac[i-1]*i%mod;
inv[i]=fsp(fac[i]);
}
int n;
cin >> n;
D[0]=1;
for (int i = 1; i <= n; i++)
{
A[i]=fsp(2,(1ll*i*(i-1)/2)%(mod-1))*inv[i-1]%mod;
D[i]=fsp(2,(1ll*i*(i-1)/2)%(mod-1))*inv[i]%mod;
}
invv(D,D,n);
for(int i=n+1;i<=maxn-100;i++)D[i]=0;
mul(A,D,B,n,n);
cout<<B[n]*fac[n-1]%mod;
return 0;
}
标签：frac,
函数,
int,
LL,
生成,
binom,
inv,
mod
From： https://www.cnblogs.com/artalter/p/16771070.html