Description

刚刚解决完电力网络的问题，阿狸又被领导的任务给难住了 刚才说过，阿狸的国家有n个城市，现在国家需要在某些城市对之间建立一些贸易路线，使得整个国家的任意两个城市都直接或间接的连通。为了省钱，每两个城市之间最多只能有一条直接的贸易路径。对于两个建立路线的方案，如果存在一个城市对，在两个方案中是否建立路线不一样，那么这两个方案就是不同的，否则就是相同的。现在你需要求出一共有多少不同的方案。 好了，这就是困扰阿狸的问题。换句话说，你需要求出n个点的简单(无重边无自环)无向连通图数目。 由于这个数字可能非常大，你只需要输出方案数mod 1004535809(479 * 2 ^ 21 + 1)即可。

Input

仅一行一个整数n(<=130000)

Output

仅一行一个整数，为方案数 mod 1004535809

Sample Input

3

Sample Output

4

HINT

对于100%的数据，n <= 130000

[ Submit][ Status][ Discuss]  分析： 天坑：n个点的无向连通图个数

递推式暴力计算的复杂度是 O(n2) O ( n 2 ) 所以我们要想一个办法降低复杂度

引用第一个递推式

f[n]=2C(n,2)−∑i=1n−1f[i]∗C(n−1,i−1)∗2C(n−i,2) f [ n ] = 2 C ( n , 2 ) − ∑ i = 1 n − 1 f [ i ] ∗ C ( n − 1 , i − 1 ) ∗ 2 C ( n − i , 2 )

2C(n,2)=f[n]+∑i=1n−1f[i]∗C(n−1,i−1)∗2C(n−i,2) 2 C ( n , 2 ) = f [ n ] + ∑ i = 1 n − 1 f [ i ] ∗ C ( n − 1 , i − 1 ) ∗ 2 C ( n − i , 2 )

合并一下：

2C(n,2)=∑i=1nf[i]∗C(n−1,i−1)∗2C(n−i,2) 2 C ( n , 2 ) = ∑ i = 1 n f [ i ] ∗ C ( n − 1 , i − 1 ) ∗ 2 C ( n − i , 2 )

不大清楚，把C拆开看一下：

2C(n,2)=∑i=1nf[i]∗(n−1)!(i−1)!(n−i)!∗2C(n−i,2) 2 C ( n , 2 ) = ∑ i = 1 n f [ i ] ∗ ( n − 1 ) ! ( i − 1 ) ! ( n − i ) ! ∗ 2 C ( n − i , 2 )

两边同除 (n−1)! ( n − 1 ) ! ：

2C(n,2)(n−1)!=∑i=1nf[i](i−1)!∗2C(n−i,2)(n−i)! 2 C ( n , 2 ) ( n − 1 ) ! = ∑ i = 1 n f [ i ] ( i − 1 ) ! ∗ 2 C ( n − i , 2 ) ( n − i ) !

感觉很像是一个卷积的形式，设：

F(x)=∑i=0∞f[i](i−1)!xi F ( x ) = ∑ i = 0 ∞ f [ i ] ( i − 1 ) ! x i

G(x)=∑i=0∞2C(i,2)i!xi G ( x ) = ∑ i = 0 ∞ 2 C ( i , 2 ) i ! x i

H(x)=∑i=0∞2C(i,2)(i−1)!xi H ( x ) = ∑ i = 0 ∞ 2 C ( i , 2 ) ( i − 1 ) ! x i

显然：

H(x)=F(x)∗G(x) H ( x ) = F ( x ) ∗ G ( x )

把式子放到mod p p 意义下： H(x)≡F(x)∗G(x)(mod⋅p)H(x)≡F(x)∗G(x)(mod·p)

F(x)≡G(x)−1∗H(x)(mod⋅p) F ( x ) ≡ G ( x ) − 1 ∗ H ( x ) ( m o d · p )

我们只要求出G的逆，与H卷起来即可

多项式求逆

B(x)=B′(x)(2−B′(x)A(x))(mod⋅p),B(x)=A−1(x) B ( x ) = B ′ ( x ) ( 2 − B ′ ( x ) A ( x ) ) ( m o d · p ) , B ( x ) = A − 1 ( x )

tip

费马小定理： xy≡xy(mod⋅φ(p))(mod⋅p)(当p是质数,φ(p)=p−1) x y ≡ x y ( m o d · φ ( p ) ) ( m o d · p ) ( 当 p 是 质 数 , φ ( p ) = p − 1 ) 所以最好的方法就是指数不要取模

求多项式的逆：

void inverse(int n,ll *a,ll *b,ll *c)

a是原多项式，b是a的逆

我这个zz一开始预处理了 2i 2 i ，但是只处理到了 2n 2 n 显然 C(n,2) C ( n , 2 ) 是不止这个范围的。。。orz

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; const ll p=1004535809; const ll o=3; //原根 const int N=3000010; ll jc[N],inv_jc[N]; int n,fn; ll f[N],g[N],b[N],c[N]; ll KSM(ll a,ll b) { ll t=1; a%=p; while (b) { if (b&1) t=(t*a)%p; b>>=1; a=(a*a)%p; } return t%p; } ll C(int n) { return (ll)n*(n-1)/2; } void prepare() { jc[0]=1; inv_jc[0]=1; for (int i=1;i<=n;i++) { jc[i]=(jc[i-1]*(ll)i)%p; inv_jc[i]=KSM(jc[i],p-2)%p; } } void NTT(int n,ll *a,int opt) { int i,j=0,k; for (i=0;i<n;i++) { if (i>j) swap(a[i],a[j]); for (int l=n>>1;(j^=l)<l;l>>=1); } for (i=2;i<=n;i<<=1) { ll wn=KSM(o,(p-1)/i); int m=i>>1; for (j=0;j<n;j+=i) { ll w=1; for (k=0;k<m;k++,w=(w*wn)%p) { ll z=(a[j+k+m]*w)%p; a[j+k+m]=(a[j+k]-z+p)%p; a[j+k]=(a[j+k]+z)%p; } } } if (opt==-1) reverse(a+1,a+n); } void solve(int n,ll *a,ll *b,ll *c) { if (n==1) { b[0]=KSM(a[0],p-2); //直接求逆 return; } solve(n>>1,a,b,c); int k=n<<1; for (int i=0;i<n;i++) c[i]=a[i]; for (int i=n;i<k;i++) c[i]=0; NTT(k,c,1); NTT(k,b,1); for (int i=0;i<k;i++) { b[i]=(ll)(2-c[i]*b[i]%p)*b[i]%p; if (b[i]<0) b[i]+=p; } NTT(k,b,-1); ll inv=KSM(k,p-2); for (int i=0;i<n;i++) b[i]=(b[i]*inv)%p; for (int i=n;i<k;i++) b[i]=0; } int main() { scanf("%d",&n); prepare(); fn=1; while (fn<=n*2) fn<<=1; for (int i=0;i<=n;i++) f[i]=(KSM(2,C(i))*inv_jc[i])%p; for (int i=1;i<=n;i++) g[i]=(KSM(2,C(i))*inv_jc[i-1])%p; solve(fn,f,b,c); //多项式求逆 NTT(fn,b,1); NTT(fn,g,1); for (int i=0;i<fn;i++) b[i]=(b[i]*g[i])%p; NTT(fn,b,-1); ll inv=KSM(fn,p-2); ll ans=(b[n]*inv%p*jc[n-1]%p)%p; printf("%lld\n",ans); return 0; }