wqy的C题
2024-09-05 04:17:01
wqy的C题
毒瘤!
题意:
你有一张 $ n $ 个点 $ m $ 条边的无向图。
你想在这张图上添加 $ n $ 条有向边,每一条有向边连接两个点 $ u,v $ ,你需要保证 $ u,v $ 在原图上不联通,且每一个点刚好作为一条有向边的起始点和另一条有向边的终止点。
注意一个点到自身也算联通。
解法:
1.10pts 观察到有一个点是完全图,所以直接输出 $ 0 $ 就有10分
2.40pts 当 $ m=0 $ 的时候,考虑错排公式的推导过程,这个图就可以转化成一个错排经典模型
3.50pts = 40pts + 10pts。
4.100pts 考虑容斥。当连通块大小不是1的时候,我们设 $ f_{i,j} = \sum^{size_i}{k=0}f{i-1,j-k}g_{size_i,k} $
其中 $ g_{i,j} $ 表示大小为 $ i $ 的连通块中已定 $ j $ 个点的方案数。
然后考虑 $ g_{i,j} $ 怎么算。首先选 $ j $ 个点,然后还要是的它们连向自己所在的连通块,所以 $ g_{i,j}=C_i^ji(i-1) \cdots (i-j+1) $ 。前面的组合数表示选出若干个点,后面是排列求方案数。
我们可以 $ O(1) $ 的预处理阶乘 ,那么 $ g_{i,j} = C_i^j \frac{i!}{(i-j)!}$
时间复杂度是 $ n \sum size_i = O(n^2) $ 。
CODE:
//待填坑
最新文章
- python-->;基础-->;005-->;类的三大成员:方法+属性+字段
- NPOI教程
- MVC自定义视图规则
- JavaScript学习之窗口
- gulp 建立一个简单的自动化
- java.lang.ClassNotFoundException
- oracle 文件导出
- js奇葩错误 字符串传递问题
- 转: OpenResty最佳实践
- C# - 集合类 - 集合类型
- J2EE、J2SE、J2ME
- String VS Cstring(字符串)
- Intellij Idea配置说明(从Eclipse转Idea)
- 《TCP-IP详解卷1:协议》【PDF】下载
- [问与答]怎样在 Android Stuido中删除一个project
- HDU-1709 The Balance(生成函数)
- [Swift]LeetCode349. 两个数组的交集 | Intersection of Two Arrays
- The absolute uri: http://java.sun.com/jsp/jstl/core cannot be resolved in either web.xml or the jar files deployed with this application问题解决方案参考
- bat如何实现自动创建文件夹(以当前时间命名)
- MySQL分页limit速度太慢的优化方法