杭电多校第五场 1001 Tetrahedron 题解

题目大意

给你一个n，abc三个数为$[1,n]$中等概率出现的数，求$\large \frac{1}{h^2}$的期望。

解题思路

不得不说，这场是真的变态。

这题有很多解法，建系，向量，海伦公式都可以。

这边就选用向量法来做。

（因为稍微简单一点。。

由体积可以推出，$\large \frac{abc}{6}=\frac{Sh}{3}$。

即$abc=2Sh$。

而$S = |\vec{AB} \times \vec{BC}|$。

设$\vec{a}=\vec{DA}，\vec{b}=\vec{DB}，\vec{c}=\vec{DC}$。
$$
\vec{AB} \times \vec{BC} = (\vec{b} - \vec{a}) \times (\vec{c} - \vec{b})=\vec{b} \times \vec{c} - \vec{a} \times \vec{c} - \vec{a} \times \vec{b}
$$
因为上面三个面互相垂直，所以他们的平面的法向量也是互相垂直的。

所以，平方得
$$
|\vec{AB} \times \vec{BC}|^2 = |\vec{b} \times \vec{c} - \vec{a} \times \vec{c} - \vec{a} \times \vec{b}|^2=|\vec{b} \times \vec{c}|^2+|\vec{a} \times \vec{c}|^2+|\vec{a} \times \vec{b}|^2=\frac{b^2c^2}{4}+\frac{a^2c^2}{4}+\frac{a^2b^2}{4}
$$
带入$abc = 2Sh$得，$\large \frac{1}{h^2}=\frac{1}{a^2} + \frac{1}{b^2} +\frac{1}{c^2}$。

因为abc三个数可以任意取，之间没有关系，所以三个数的期望是一样的，得$E(\large \frac{1}{h^2})=3 E(\large \frac{1}{a^2})$。

之后的期望就好求了，需要预处理逆元的前缀和。

但是这个逆元的前缀和不能用快速幂来求，会T。

（但是比赛的时候是能过的。

所以需要用递推来求逆元。

详解见大佬博客。

（用的递推都差点超了。。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int mod = 998244353, maxn = 6e6 + 5;
ll fiv[maxn], sum[maxn];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t; scanf("%d",&t);
	fiv[1] = 1;
	for (int i = 2; i <= 6e6; i++) {
		fiv[i] = (mod - mod / i) * fiv[mod % i] % mod;//递推求逆元
	}
	for (int i = 1; i <= 6e6; i++) {
		sum[i] = (sum[i - 1] + fiv[i]*fiv[i]) % mod;
	}
	while (t--) {
		int n; scanf("%d",&n);
		ll ans = (3 * (sum[n] % mod * fiv[n]) % mod) % mod;
		cout << ans << endl;
	}
	return 0;
}