来自出题人的假题解

表情包镇楼

打个小广告：我的个人博客

D . 插排树

看题，很明显的就是求入度为0的点到出度为0的点的最长路
最长路是啥？好吃吗？？
dij/spfa均可做
要来点骚的？？？
floyd把小于号改大于号

F . /***/ 青蛙

做法：dp
超时？？
骚优化啊qwq
不会优化？
//我才不会告诉你跑floyd能做23333
你问我资不******做标题？
我可以回答你一个***

F . 三轮

三轮一题慢慢的都是泪啊qwq
本来是道压轴的题
想考察分治fft的
结果数据出了大锅
牛客的机器居然莫名其妙的跑的快？？？
在CCF老爷机上nm暴力会超时的点牛客居然过了？？！
差评一个
下面开始扯骚解23333
首先构造生成函数：
Fi(x)=1+x^Vi+x^2Vi+x^3Vi+...
然后发现这个东西是等比数列，直接上求和公式
Fi(x)=(1-x^inf)/(1-x^Vi)
我们考虑x取不同的值，这里假设x>0
当x>1时，Fi(x)=(1-inf)/(1-x^Vi)，这个东西显然无法计算
当x<1时，x^inf=0，Fi(x)=1/(1-x^Vi)
所以
我们考虑如何计算那个东西
乘法非常难看，我们将它取ln，最后exp回来
关于函数的ln有这样一个定义：ln(1-x)=-∑(x^i)/i
我们可以枚举Vi的倍数来计算贡献
然后我们发现Vi同样的可以一起计算贡献
O(m/1+m/2+m/3+...+m/m)=O(mlogm)
然后最后exp回来
总时间复杂度O(mlogm)
蔡队垫后