博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
COGS 2396 2397 [HZOI 2015]有标号的强连通图计数
阅读量:6837 次
发布时间:2019-06-26

本文共 432 字,大约阅读时间需要 1 分钟。

题意:求n个点有向图其中SCC是一个的方案数

 

考虑求出若干个不连通的每个连通块都是SCC方案数然后再怎么做一做。(但是这里不能用Ln,因为推不出来)

设$f_n$为答案,

$g_n$为n个点的有向图,分成若干个连通块,每个连通块都是一个SCC,且当连通块大小为奇数时候贡献1系数,偶数时候贡献-1系数。(这里把系数放进去可以避免再来一个函数的麻烦!)

$h_n$表示n个点有向图个数$h_n=2^{n*(n-1)}$

$h_n=\sum_{i=1}^nC(n,i)\times g(i)\times 2^{n\times(n-i)}\times h(n-i)$

$g_n=f_n-\sum_{i=1}^{n-1}C(n-1,i-1)\times g(n-i)$

然后把C拆开,变成EGF,$2^{n\times(n-i)}$可以用之前套路处理

即可得到答案

转载于:https://www.cnblogs.com/Miracevin/p/10767523.html

你可能感兴趣的文章
Win10上 visual studio设置为本地IIS运行网站时 必须以管理员身份加载项目的解决方法...
查看>>
记录常见的HTTP请求错误
查看>>
Java字符串替换函数replace、replaceFirst、replaceAll
查看>>
Ubuntu下搭建Android开发环境
查看>>
汇编指令
查看>>
yum安装mysql后root用户的临时密码
查看>>
mysql 原理~ 乐观锁和悲观锁
查看>>
策略模式
查看>>
neo4j使用
查看>>
MVC WebAPI 的基本使用
查看>>
Oracle 字符集的查看和修改
查看>>
Selection
查看>>
索引的几种使用方式
查看>>
Excel2007给表格设置成只读加密属性 让他人无法修改
查看>>
android wifi USB总线
查看>>
20145337 《Java程序设计》第二周学习总结
查看>>
关于常量池
查看>>
DevExpress BarCode的属性设置
查看>>
php 基础知识
查看>>
PAT乙级-1057. 数零壹(20)
查看>>