BZOJ3456: 城市规划-白红宇

BZOJ3456: 城市规划

阅读量：5050 次

发布时间：2019-06-12

本文共 1828 字，大约阅读时间需要 6 分钟。

n<=1.3e5的无向简单连通图个数。mod 1004535809。

听说是很多人的多年坑。。？还好我见识少

首先用容斥递推，$f(i)$表示$i$个点答案。如果不考虑连通就是$2^{\frac{i(i-1)}{2}}$，然后枚举所有不连通的情况（我就不会了）。

枚举最后一个点所在集合大小$j$，我需要在剩下$i-1$个点里面挑$j-1$个来陪他，然后这坨点联通的方案就$f(j)$，其他点乱连，就$2^{\frac{(i-j)(i-j-1)}{2}}$。

好！$f(i)=2^{\frac{i(i-1)}{2}}-\sum_{j=1}^{i-1}C_{i-1}^{j-1}f(j)2^{\frac{(i-j)(i-j-1)}{2}}$。

C拆掉，$f(i)=2^{\frac{i(i-1)}{2}}-\sum_{j=1}^{i-1}\frac{f(j)(i-1)!2^{\frac{(i-j)(i-j-1)}{2}}}{(j-1)!(i-j)!}$

按照套路，两边除$(i-1)!$，$\frac{f(i)}{(i-1)!}=\frac{2^{\frac{i(i-1)}{2}}}{(i-1)!}-\sum_{j=1}^{i-1}\frac{f(j)2^{\frac{(i-j)(i-j-1)}{2}}}{(j-1)!(i-j)!}$

有相似的形式，很好！！！令$g(i)=\frac{f(i)}{(i-1)!}$，其中$g(0)=0$，$h(i)=\frac{2^{\frac{i(i-1)}{2}}}{i!}$，其中$h(0)=0$，$s(i)=\frac{2^{\frac{i(i-1)}{2}}}{(i-1)!}$，其中$s(0)=0$。

搞出他们三人的生成函数，可知$g=s-g*h$，得$g=\frac{s}{1+h}$，好！多项式求逆再乘一次。

1 //#include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 //#include
           6 #include
           
             7 //#include
            
              8 //#include
             
               9 #include
              
               10 using namespace std;11 12 int n,m;13 #define maxn 26222214 const int mod=1004535809,G=3; int rev[maxn];15 16 int powmod(int a,int b)17 {18 int ans=1;19 while (b)20 {21 if (b&1) ans=1ll*ans*a%mod;22 a=1ll*a*a%mod; b>>=1;23 }24 return ans;25 }26 27 void dft(int *a,int n,int type)28 {29 int wei=-1,tnt=n; while (tnt) wei++,tnt>>=1;30 for (int i=0;i
               
                >j)&1)<<(wei-j-1);34 }35 for (int i=0;i
                
                 >1,ans);70 for (int i=0;i<(n>>1);i++) tmp[i]=a[i]; for (int i=(n>>1);i
                 
                  >1);i
                  
                   >1],i); else tt[i]=powmod(two[i>>1],i-1);84 s[0]=0; for (int i=1;i<=n;i++) s[i]=1ll*tt[i]*inv[i-1]%mod;85 h[0]=1; for (int i=1;i<=n;i++) h[i]=1ll*tt[i]*inv[i]%mod;86 87 m=n+n; for (n=1;n<=m;n<<=1); m>>=1;88 nee(h,n,u); mul(u,s,g);89 printf("%lld\n",1ll*g[m]*fac[m-1]%mod);90 return 0;91 }

View Code

转载于:https://www.cnblogs.com/Blue233333/p/8482316.html

你可能感兴趣的文章