2020杭电多校联合训练（第五场）1001 （费马小定理+数学期望）

题面

Generate three integers a, b, and c in [1,n] with equal probability independently, and use them as the three right-angle side length of a right-angled tetrahedron. Find the expectation of the reciprocal square of the distance from the right-angle apex to the slope (Euclidean distance).

For each test case, output a line containing the answer mod 998244353.

Input
In the first line, you should read an integer T denoting the number of test cases.

In every test case, the only line will include an integer n.

It is guaranteed that T is no larger than 2×106 and n is no larger than 6×106.

Output
For each test case, output the only line containing just one integer denoting the answer mod 998244353.

Sample Input
3
1
2
3

Sample Output
3
124780546
194103070

思路

代码实现

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define rep(i,f_start,f_end) for (int i=f_start;i<=f_end;++i)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define MT(x,i) memset(x,i,sizeof(x) )
#define rev(i,start,end) for (int i=0;i<end;i++)
#define inf 0x3f3f3f3f
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x&-x)
#define MOD 1000000007
#define exp 1e-8
#define N 1000005 
#define fi first 
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int ,int> PII;
typedef pair<int ,PII> PIII;
ll gcd (ll a,ll b) {return b?gcd (b,a%b):a; }
inline int read() {
    char ch=getchar(); int x=0, f=1;
    while(ch<'0'||ch>'9') {
        if(ch=='-') f = -1;
        ch=getchar();
    } 
    while('0'<=ch&&ch<='9') {
        x=x*10+ch-'0';
        ch=getchar();
    }   return x*f;
}

const int mod=998244353;
const int maxn=6000010;
ll pre[maxn],sum[maxn];

ll fast_pow (ll x) {
    ll ans=1,y=mod-2;
    while (y) {
        if (y&1) ans=x*ans%mod;
        x=x*x%mod;
        y>>=1;
    } 
    return ans;
}

int main () {
   
   rev (i,1,maxn)  {
       pre[i]=fast_pow (i);
       sum[i]=(sum[i-1]+pre[i]*pre[i]%mod)%mod;
   }


   int t;
   cin>>t;
   while (t--) {
       int n;
       scanf ("%d",&n);
       printf ("%lld
",3*sum[n]*pre[n]%mod);
   }

    return 0; 
}