题解 P6307 【「Wdsr-1」贤者之石】
囧仙
2020-04-11 23:55:58
啊,这是美⑨出的第一道题,笔法略差,多多包涵。
(感谢ysj大佬完善的题面,原题面在此:[here](https://www.luogu.com.cn/problem/U111813))
如果你没有思路,你可以通过电脑枚举k个点的情况,然后看结果找规律,如果您够~~无耻~~睿智,可以丢到oeis上查一下,然后真的能查到,[对方一脸嫌弃的给你了个链接](http://oeis.org/A000332)。
~~或者你可以直接看样例找规律,你就是拉马努金!(暴论~~
当然还是要给出严谨做法的。。
首先我们来看如何确定点阵中的正三角形。
点阵里的正三角形有两种:
![](https://patchoulii-knowledge.github.io/post-images/1585618934094.png)
第一种就是类似于$\bigtriangleup XYZ$这样的。
第二种就是类似于$\bigtriangleup DEF$这样的。
我们发现$\bigtriangleup DEF$ 可以唯一确定一个$\bigtriangleup XYZ$
那么 $\bigtriangleup DEF$就是$\bigtriangleup XYZ$的确定条件再加一个条件。
不可避免的我们就要找到$\bigtriangleup XYZ$的确定条件。
那咋搞呢? 我们可以 **投影** 啊!!
把三角形的三边投影到大三角形的底边上!类似这样的:
![](https://patchoulii-knowledge.github.io/post-images/1585619505762.png)
这样你就可以用$(P,Q,R)$ 来确定一个三角形啦!
但是还有一个小问题。。。就是那个大的三角形(就是$\bigtriangleup ABC$)有可能会锅。。。($P,Q$两点重合)
当然你组合好的话仍然可以整,对于我这样的渣渣想不出来咋办呢?
那我们可以延长啊,延长$AB,AC$至$B',C'$,使得$BB'=1,CC'=1$,这时$B'C'$上有$k+1$个点。
那不就完了,来,看图:
![](https://patchoulii-knowledge.github.io/post-images/1585619894874.png)
诶,是不是完美的解决了问题?
这样你就可以用$(P,Q,R)$ 来确定$\bigtriangleup XYZ$啦!
$P,Q,R$ 这条边上有$k+1$ 个,所以 $\bigtriangleup XYZ$ 这样的三角形有 $C_{k+1}^3$ 个。
那$\bigtriangleup DEF$这样的三角形是不是可以进行一样的操作呢?
答案是肯定的!来,看图:
![](https://patchoulii-knowledge.github.io/post-images/1585620194300.png)
这样你就可以用$(P,Q,O,R)$ 来确定$\bigtriangleup DEF$啦!
同理,$\bigtriangleup DEF$ 这样的三角形有 $C_{k+1}^4$ 个。
那结果就很显然啦:
$$
P_k=\frac{C_{k+1}^{3}+C_{k+1}^{4}}{C_{\frac{k\left( k+1 \right)}{2}}^{3}}=\frac{C_{k+2}^{4}}{C_{\frac{k\left( k+1 \right)}{2}}^{3}}=\frac{2}{k^2+k-4}
$$
本来美⑨是想到这里为止了,但是作为T2,这实在是太水啦!于是她有一个大胆的想法。。就有了这一题。
所以她想用两个小问,第一小问求$P_k$。。蛋是,ysj巨神告诉我:
![](https://patchoulii-knowledge.github.io/post-images/1585706619445.png)
于是就算了,虽然这个式子有点珂怕,但是你仍然珂以骗到分
放缩:
$$
\sum_{k=m}^{\infty}{\frac{2}{k^2+k-4}}>2\sum_{k=m}^{\infty}{\frac{1}{k^2+k}}=2\sum_{k=m}^{\infty}{\frac{1}{k}-\frac{1}{k+1}=\frac{2}{m}}
$$
$$
\sum_{k=m}^{\infty}{\frac{2}{k^2+k-4}}<2\sum_{k=m}^{\infty}{\frac{1}{k^2+k-6}}=2\sum_{k=m}^{\infty}{\frac{1}{5}\left( \frac{1}{k-2}-\frac{1}{k+3} \right) =\frac{2}{5}\left( \frac{1}{m-2}+\frac{1}{m-1}+\frac{1}{m}+\frac{1}{m+1}+\frac{1}{m+2} \right)}
$$
骗分其实很好骗,你输出$\frac{2}{m}$ 就好了。。。那么大数据的那几个点的分你有了。。
(P.S. 其实这道题数据小的点比较难搞。一开始骗分能骗到76分!!然后美⑨加强了数据,本来想加强精度的,比如保留⑨位有效数字什么的,但是既然ysj说算了别卡了,那就算了)
我们可以参照上面的思路,强行裂项!!!
下面需要一些数学技巧。。你可以先百度一下PolyGamma函数
$$
\sum_{k=m}^{\infty}{\frac{2}{k^2+k-4}}=2\sum_{k=m}^{\infty}{\frac{1}{\left( k+\frac{1+\sqrt{17}}{2} \right) \left( k+\frac{1-\sqrt{17}}{2} \right)}}=\frac{2}{\sqrt{17}}\sum_{k=m}^{\infty}{\left( \frac{1}{k+\frac{1-\sqrt{17}}{2}}+\frac{1}{k+\frac{1+\sqrt{17}}{2}} \right)}
$$
$$
=\frac{2}{\sqrt{17}}\left[ \psi \left( \frac{1+\sqrt{17}}{2}+m \right) -\psi \left( \frac{1-\sqrt{17}}{2}+m \right) \right]
$$
介个东西好像不好搞啊。。
我们回忆一下余元公式,两边求导试试?(这个不会的私信我把。。或者你百度一下余元公式?)
那么可以推导出
$$
\psi \left( x \right) -\psi \left( 1-x \right) =-\frac{\pi}{\tan \pi x}
$$
到时候我会补锅,你们先凑合看看这个吧:
[洛谷上的博客](https://www.luogu.com.cn/blog/you-xiao-mei-jiu/qian-xi-euler-ji-fen)
[GitHub上的博客](https://patchoulii-knowledge.github.io/post/qian-xi-g-han-shu/)
想要凑出ao的结果,那就令
$$
\left( \frac{1+\sqrt{17}}{2}+m \right) +\left( \frac{1-\sqrt{17}}{2}+m \right) =0
$$
那就很容易得出 $m=0$
那我们令$m=0$ 看看?
$$
\sum_{k=0}^{\infty}{\frac{2}{k^2+k-4}}=\frac{2}{\sqrt{17}}\left[ \psi \left( \frac{1+\sqrt{17}}{2} \right) -\psi \left( \frac{1-\sqrt{17}}{2} \right) \right] =-\frac{2}{\sqrt{17}}\frac{\pi}{\tan \left( \pi \left( \frac{1+\sqrt{17}}{2} \right) \right)}=\frac{2\pi}{\sqrt{17}}\tan \left( \frac{\sqrt{17}}{2}\pi \right)
$$
啊呀,好看的一逼那是。
那就很好搞了。。
$$
\sum_{k=m}^{\infty}{\frac{2}{k^2+k-4}}=\sum_{k=0}^{\infty}{\frac{2}{k^2+k-4}}-\sum_{k=0}^{m-1}{\frac{2}{k^2+k-4}}=\frac{2\pi}{\sqrt{17}}\tan \left( \frac{\sqrt{17}}{2}\pi \right) -\sum_{k=0}^{m-1}{\frac{2}{k^2+k-4}}
$$
但是有一个小坑啊。。$P_1=0$ 而不是 $-1$
那我们把它挖掉就好惹:
$$
Ans=\frac{2\pi}{\sqrt{17}}\tan \left( \frac{\sqrt{17}}{2}\pi \right) +\frac{3}{2}-\sum_{k=2}^{m-1}{\frac{2}{k^2+k-4}}
$$
$$
=1.7984105510168780039-\sum_{k=2}^{m-1}{\frac{2}{k^2+k-4}}
$$
完了? 完了!
(p.s. 其实不用挖掉,我当时思博了)
代码太丑不放了。。