FFT/NTT中档题总结
2024-10-11 20:44:22
被DeepinC%怕了,把一些题放到这里来
T1Normal
其实这道题放到中档题也不太合适,个人感觉真的很难,机房里好像都是颓的题解
因为期望的可加性,把每个点的贡献单独处理,即求期望深度
考虑$y$对$x$的贡献:当且仅当$x->y$的路径上第一个点就选$y$,$y$才能成为$x$的祖先
所以$y$对$x$的贡献就是:$P=\frac{1}{dis(x,y)+1}$,$E=1$
所以最终答案就是$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\frac{1}{dis(i,j)+1}$
用点分治+$FFT$便可以$O(nlog_2^2(n))$解决
T2染色
题解在二项式反演总结里
T3城市规划
昨天推了一波式子,就被skyh和Deepinc狂%,但其实我的式子的组合数是错的
设$f[i]$代表$i$个点联通的方案数:
设$g[i]=2^{\frac{i*(i-1)}{2}}$
$f[i]=g[i]*\sum\limits_{j=1}^{i}C_{i-1}^{j-1}*f[j]*g[i-j]$
便是一个裸的分治FFT了
最新文章
- 关于DOM的一些笔记(一)
- 【原】iOS动态性(三) Method Swizzling以及AOP编程:在运行时进行代码注入
- qau-国庆七天乐——A
- Dooioo Deal
- os模块
- 翻译之basename()
- linux的命令(1)
- 懂说话,让冲突、尴尬时刻都bye-bye
- typedef struct 是什么意思
- 常用Linux操作命令
- 如何配置Open Live Writer程序以便更好的为博客服务
- Windows 下最佳的 C++ 开发的 IDE 是什么?
- <;<;Sklearn 与 TensorFlow 机器学习实用指南>;>;
- Android Studio安卓导出aar包与Unity 3D交互
- Map相关问题
- 9.10 h5日记
- Mybatis通过colliection属性递归获取菜单树
- 2018.09.17 atcoder Tak and Hotels(贪心+分块)
- Python学习札记(三十九) 面向对象编程 Object Oriented Program 10
- 小M的作物 最小割最大流