题解 P6307 【「Wdsr-1」贤者之石】

囧仙

2020-04-11 23:55:58

Solution

啊,这是美⑨出的第一道题,笔法略差,多多包涵。 (感谢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. 其实不用挖掉,我当时思博了) 代码太丑不放了。。