2020 Multi-University Training Contest 5解题报告

A - Tetrahedron

题意

给你一个直角四面体,这个直角四面体的三条棱的长度是[1,n]中的随机整数,我们设这个直角四面体的底面上的高为h,求 1/h² 的数学期望是多少。

思路

直角四面体有如下关系:1/h²=1/a² + 1/b² + 1/c²。

因为a,b,c都是[1,n]中等概率生成的随机数,所以E(1/h²)=E(3 * 1/a²)=3 * E(1/a²)。

E(1/a²)=(1/1² 1/n + 1/2² 1/n + 1/3² 1/n + …+ 1/n² 1/n)

=1/n * (1/1² + 1/2² + 1/3² + …+ 1/n²)

可以对逆元进行线性打表,并计算平方前缀和。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=6e6+5,mod=998244353;
ll inv[maxn],sum[maxn];

void ni()
{
    inv[0]=inv[1]=1;
    for(int i=2;i<maxn;i++)
    {
        inv[i]=(mod-(mod/i))*inv[mod%i]%mod;
    }

}

void gsum()
{
    for(int i=1;i<maxn;i++)
    {
        sum[i]=(sum[i-1]+inv[i]*inv[i]%mod)%mod;
    }
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    ni();
    gsum();
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        cout<<(3*inv[n]*sum[n])%mod<<endl;
    }
    return 0;
}

小仙女