CF Gym101933K King's Colors
2024-08-27 06:12:37
题目分析
题目要求在树上涂上恰好\(K\)种颜色的方案数。
设\(f(k)\)表示恰好涂上\(k\)种颜色的方案数(答案即为\(f(K)\))。
设\(g(k)\)表示至多涂上\(k\)种颜色的方案数。
显然有:\(g(k)=\sum\limits_{i=1}^k\dbinom{k}{i}f(i)\)
那么二项式反演后:\(f(k)=\sum\limits_{i=1}^k(-1)^{k-i}\dbinom{k}{i}g(i)\)
考虑如何求\(g(i)\)。
如果是序列上的问题,显然就是\(i*(i-1)^{n-1}\),那么树上呢?
考虑一个节点是否有父节点,有则乘上\((i-1)\),否则乘上\(i\),与序列同理。
那么答案就是\(\sum\limits_{i=1}^K(-1)^{K-i}\binom{K}{i}i*(i-1)^{n-1}\)
就做完啦。
最新文章
- VirtualBox动态添加虚拟硬盘
- XAF ListView 移除顶部工具栏
- 小米、MIUI、sqlite3: not found--miui安装sqlite3
- fstab文件
- HDU 4630 No Pain No Game 树状数组+离线查询
- (三)spark集群DHCP IP变化后的处理
- javascript OOP编辑思想的一个实践参考
- 151111 sqlite3数据库学习
- Linux系统重启network服务失败
- 新浪微博 2.4sdk 一闪而过
- silverlight 和winform的结合使用
- 【Machine Learning】单参数线性回归 Linear Regression with one variable
- Angularjs^1.2.9 搜索关键字高亮显示
- Vue.js的从入门到放弃进击录(二)
- php开发微信公众号获取信息LBS
- 基于TI CC2650的IPv6 over BLE(BLEach) demo
- cf1051d 简单的状态压缩dp
- eclipse的springboot插件
- swift 的相机扫描
- 1.Python爬虫入门一之综述