首页 > 其他 > 详细

COGS 2353 2355 2356 2358 有标号的DAG计数

时间:2019-04-22 20:04:46      阅读:77      评论:0      收藏:0      [点我收藏+]

标签:直接   cnblogs   htm   itl   个数   加减   pos   二分图   $2   

不用连通

枚举入度为0的一层

卷积

发现有式子:

由$n^2-i^2-(n-i)^2=2*i*(n-i)$

可得$2^{i*(n-i)}=\frac{{\sqrt 2}^{(n^2)}}{{\sqrt 2}^{(i^2)}*{\sqrt 2}^{(n-i)^2}}$

设$g(n)={\sqrt 2}^{(n^2)}$

则,$2^{i*(n-i)}=\frac{g(n)}{g(i)*g(n-i)}$

指数相乘变成指数相加减,把$g(n)$除过去即可

 

连通

弱联通:变成无向边是连通的

f(n)表示n个点的DAG个数,g(n)表示n个点的弱连通DAG个数

$f(n)=\sum_{i=0}^{n-1} C(n-1,i)*g(n-i)*f(i)$

不妨设$g[0]=0

则$\frac{f(n)}{(n-)!}=\sum_{i=0}^{n} \frac{g(n-i)}{(n-i-1)!}*\frac{f(i)}{i!}$

所以,如果把F和G看成f和g的EGF

不妨设$g[0]=0

有$F‘=G‘*F$

当$G=lnF$时候,恰好成立

所以,$G=ln F$

 

PS:不连通转连通都可以直接放上Ln了事

luoguP4841 城市规划

 

COGS 2392 2393 2395 有标号的二分图计数

 

COGS 2353 2355 2356 2358 有标号的DAG计数

标签:直接   cnblogs   htm   itl   个数   加减   pos   二分图   $2   

原文:https://www.cnblogs.com/Miracevin/p/10752485.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号