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

· · 题解

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

首先可以打出这样一个暴力求 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);
}

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