好题Islands
2024-09-04 08:25:55
Orz yjc 吊打候选队
不好的思路是枚举森林的m块,这样DP显然会涉及n当做某一维,最多只能卷积优化一下
生成函数什么的n太大不用想
考虑m,k比较小,能不能把n变成一个系数,而不是维度
所以就是m的选择以及度数的情况,剩下的n接上去.
https://blog.csdn.net/qq_39972971/article/details/94048092
这个森林的prufer序列,也可以用n+1作为大根来连接m个儿子(这样比较自然)
本质显然是一样的
转化为序列问题
枚举总共的度数是i的话
给m个颜色分配i个盒子,每个颜色出现次数<=k
f[i][j],转移如果枚举第i种颜色用了多少个以及占用哪些盒子,O((mk)^2)
枚举最后一个盒子放哪种颜色?>k不合法?恰好对应唯一的=(k+1)的情况!直接减掉!
类似HEOI2014平衡以及YALI集训考试题
至于组合数,**出题人mod不一定是质数
C(j-1,k)可以预处理
而C(n,m)m又比较小项数不多,对mod质因数分解,记录分子分母质因子的出现次数即可
最新文章
- [poj1741][tree] (树/点分治)
- 通过3个Hello World应用来了解ASP.NET 5应用是如何运行的（2）
- [k]优雅的css
- 如何安装Oracle Instant Client
- NYOJ题目114某种序列
- HDU 1213 How Many Tables （并查集）
- JTextAreaDemo
- Video Target Tracking Based on Online Learning—TLD单目标跟踪算法详解
- Android远程桌面助手(B1413)
- scrapy安装
- MQTT 嵌入式端通讯协议解析（转）
- MVC知识点记录
- SpringBoot使用外置的Servlet容器
- gitlab 使用现有 nginx 服务器
- LoadRunner-创建场景
- SQLServer中对时间和长度的处理
- tomcat服务器访问网址组成
- 近看到的机器学习、NLP相关书单
- tomcat的server.xml配置及context配置直接引用工程
- [转]jQuery ListBox Plugin(ListBox插件)