竞赛讨论区 > 来自出题人的假题解
头像
弱到自闭的kench
编辑于 2018-08-12 10:22
+ 关注

来自出题人的假题解

表情包镇楼

rkvz9-qk343.gif

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

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)
所以图片1.png
我们考虑如何计算那个东西
乘法非常难看,我们将它取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)
蔡队垫后
photo_2018-08-11_10-07-08.jpg

全部评论

(2) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐