almost 3 years ago

前言

(出题人你出数学题就算了,还出数学题套数学题。。。

题目大意


数据范围:

分析

我们先来看第一问,怎么求
我们考虑光的反射可以转化成把镜面复制一份,那么我们就可以把平面划分成无数个三角形,就是求从原点出发可以到达多少个原点的复制点。(下图中红点即为原点及其复制点)


我们考虑给这个系统一个坐标,分别表示点在第条左斜线上,第条右斜线上,第条横线上。
稍微观察一下我们可以发现,因此只用存二维坐标,接着我们考虑一个复制点由另一个复制点复制过来,横着复制或竖着复制,坐标变化分别是,因此复制点必定满足,由于到了一个复制点后就不能到另一个,因此,再根据题意,对称的算一种,因此我们不妨设。根据题意要经过次反射,即经过左斜边+右斜边+横边=,因此就是,暴力枚举,解出,判断是否满足条件即可。第一问我们就解决了,时间
再来看看第二问,我们要算出这个奇怪的式子:

考虑是等价的,我们的式子就可以化成:

我们先来把展开一下,考虑的约数,我们要唯一表示这个,可以让尽量大,尽量小, 即满足,也就是直到不能扩展为止,这样很明显构成了一一对应关系,那么有:

反演一下:

再把提到前面去:

展开得差不多了,我们把它带到整个式子里面去:

再次把提到前面去:

常识性的再化简:

设:

都是可以内算出来的,那么原式化成了:

我们现在只要在低于的时间内求出的前缀和即可,那不就是杜教筛嘛。

反正复杂度是低于线性的,就是能过,所以这道题就搞完了。。。大功告成!分析出复杂度的神犇可以在下面留言。。。

← 集训的一道组合计数的题 HNOI2010 →
 
comments powered by Disqus