自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:19:32，当前版本为作者最后更新于2020-04-09 13:56:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这是一篇全程乱搞的题解，，

首先可以打出这样一个暴力求 $n$ 个点三角阵中，能组成正三角形的个数 $a_n$：

inline double dist(node a,node b){
    double dx = a.x-b.x,dy = a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}

int n,cnt = 1;
int ans;

int main(){
    double sy = 0,sx = 0,d1,d2,d3;
    scanf("%d",&n);
    a[1] = node(0,0);
    for(int i=2;i<=n;++i){
        sy -= sqrt(3)/2,sx -= 0.5;
        for(int j=0;j!=i;++j)
           a[++cnt] = node(sx+j,sy); 
    }
    for(int i=1;i<=cnt;++i)
    for(int j=i+1;j<=cnt;++j)
    for(int k=j+1;k<=cnt;++k){
        d1 = dist(a[i],a[j]),d2 = dist(a[i],a[k]),d3 = dist(a[j],a[k]);
        if(fabs(d1-d2)<eps&&fabs(d2-d3)<eps&&fabs(d1-d3)<eps) ++ans;
    }
    printf("%d",ans);
}

由于总共选的方案数为

$$b_n= \binom{n(n+1)/2}{3}$$ $$=\frac{n^6+3n^5-3n^4-11n^3+2n^2+8n}{48}$$

是一个六次多项式，所以 $a_n$ 一定是低于六次的多项式，拉格朗日插值可以求出

$$a_n= \frac{n^4 + 2n^3 - n^2 - 2n}{24}$$

再做多项式除法得到

$$p_n=\frac{2}{n^2+n-4}$$

（此式在 $n\ge 2$ 时正确）

那么问题转化为求

$$\sum_{n=0}^\infty \frac{2}{n^2+n-4}$$

我不会算，wolframalpha 了一下得出答案是

$$\frac{2\pi \tan\left(\frac{\sqrt{17}}{2} \pi \right)}{\sqrt{17}} $$

然后暴力减去前 $m$ 项的值即可，时间复杂度 $\Theta(m)$。
ps：这个东西的前缀和，可以用几个 Gamma 函数来表示，似乎是 $\Theta(1)$ 的？

#pragma GCC optimize (2)
#pragma GCC optimize ("unroll-loops")
#include<cstdio>
#include<iostream>
#include<cmath>
#define double long double
using namespace std;

const double pi = acos(-1);

inline double f(double x){
    return 2/(x*(x+1)-4);
}

double ans = (2*pi*tan(sqrt(17)*pi/2))/sqrt(17);
int n,cnt;

int main(){
    scanf("%d",&n);
    for(register int i=0;i!=n;++i) ans -= f(i);
    while(ans<1) ans *= 10,--cnt;
    while(ans>10) ans /= 10,++cnt;
    printf("%.4Lfx10^%d",ans,cnt);
}

于是这题就被我们不带脑子干掉了