HDU6814杭电多校第5场Tetrahedron（其实就两个式子，超简单版）

题意&＃xff1a;

三个面都是直角的三棱锥&＃xff0c;三个棱长分别为$a,b,c$&＃xff08;在$[1,n]$中任取&＃xff09;。设顶点到底面的距离$h$&＃xff0c;求1h2\frac{1}{h^2}h21​的期望。

解析&＃xff1a;

我看官方讲解推导实在太麻烦了&＃xff0c;于是写一下这篇博客说一下自己的推法。

既然三棱锥三个角都是直角&＃xff0c;我们直接把顶点当作坐标原点&＃xff0c;三条棱当作三个方向的轴&＃xff0c;$h$的求解就转换成了点到面的距离。

三维直角坐标系中点(x0,y0,z0)(x_0,y_0,z_0)(x0​,y0​,z0​)到面$Ax\&＃43;By\&＃43;Cz\&＃43;D\&＃61;0$的距离公式&＃xff1a;
h&＃61;∣Ax0&＃43;By0&＃43;Cz0&＃43;D∣A2&＃43;B2&＃43;C2h&＃61;\frac{|Ax_0&＃43;By_0&＃43;Cz_0&＃43;D|}{\sqrt{A^2&＃43;B^2&＃43;C^2}} h&＃61;A2&＃43;B2&＃43;C2

​∣Ax0​&＃43;By0​&＃43;Cz0​&＃43;D∣​
底面是一个过$(0,0,a),(b,0,0),(0,c,0)$的面&＃xff0c;面的公式求都不用求
$$acx\&＃43;aby\&＃43;bcz-abc\&＃61;0$$
顶点是坐标原点&＃xff0c;直接套公式
h&＃61;abca2b2&＃43;b2c2&＃43;a2c2h&＃61;\frac{abc}{a^2b^2&＃43;b^2c^2&＃43;a^2c^2} h&＃61;a2b2&＃43;b2c2&＃43;a2c2abc​
那么
1h2&＃61;1a2&＃43;1b2&＃43;1c2\frac{1}{h^2}&＃61;\frac{1}{a^2}&＃43;\frac{1}{b^2}&＃43;\frac{1}{c^2} h21​&＃61;a21​&＃43;b21​&＃43;c21​
$a,b,c$等价&＃xff0c;E(1h2)&＃61;3×E(1a2)E(\frac{1}{h^2})&＃61;3\times E(\frac{1}{a^2})E(h21​)&＃61;3×E(a21​)

线性求下逆元&＃xff0c;再求前缀和&＃xff0c;最后输出的时候别忘了期望还要除以概率&＃xff0c;$pre[n]\times inv[n]\%mod$

AC代码&＃xff1a;

#include
#include
#define pb push_back
#define fir first
#define sec second
#define ms(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define sp system("pause")
#define multi int T;scanf("%d",&T);while(T--)
using namespace std;
typedef long long ll;
typedef double db;
const int N&＃61;6e6&＃43;5;
const ll mod&＃61;998244353;
const db pi&＃61;acos(-1.0);
ll inv[N],pre[N];
ll qpow(ll a,ll b){ll res&＃61;1;while(b){if(b&1) res&＃61;res*a%mod;a&＃61;a*a%mod;b>>&＃61;1;}return res;
}
void invv(int n,int p)//1~n在模p意义下逆元
{inv[0]&＃61;inv[1]&＃61;1;for(int i&＃61;2;i<&＃61;n;i&＃43;&＃43;)inv[i]&＃61;((-p/i*inv[p%i])%p&＃43;p)%p;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("D:\\work\\data.in","r",stdin);#endifinvv(6e6,mod);for(ll i&＃61;1;i<&＃61;6e6;i&＃43;&＃43;){pre[i]&＃61;(pre[i-1]&＃43;3*inv[i]*inv[i])%mod;} multi{int n;scanf("%d",&n);printf("%lld\n",pre[n]*inv[n]%mod);}
}