hdu6814 Tetrahedron 线性求逆元 + 快速幂求逆元

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6814

pown数组用于线性求逆元，需注意初始化，行号35

公式，行号37

理解不了，只能死记硬背了

参考文献：https://www.cnblogs.com/zjp-shadow/p/7773566.html

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>

#define ll long long
using namespace std;

const int m = 998244353;
const int maxn = 6e6 + 10;

int n;
ll sum[maxn];
ll pown[maxn];

ll fast_pow(ll base,ll k)//base^k // long long - must
{
    ll res = 1;
    while(k){
        if(k & 1){//奇偶 
            res *= base % m;
        }
        base *= base;                
        base %= m;res %= m;
        
        k >>= 1;
    }        
    return res % m;
}

int main(){
    int T;scanf("%d",&T);    
    //pre_solve;
    pown[1] = sum[1] = 1;// 
    for(int i = 2 ; i <= 6e6 ; i++){
        pown[i] = (m - m / i) * pown[m % i] % m;//线性求逆元 
        //pown[i] = fast_pow(i % m, m - 2) % m;
        sum[i] = (sum[i - 1] + pown[i] * pown[i] % m) % m;//可利用到pown数组结果 
        //sum[i] = (sum[i - 1] + fast_pow(i * i % m, m - 2)) % m ;//计算期望
    }
        
    while(T--){
        scanf("%d",&n);
        printf("%lld
",3 * sum[n] * pown[n] % m);
    }
    // 1/h^2 = 1/a^2 + 1/b^2 + 1/c^2 ; a,b,c [1,n]
    // b/a % p = b*a^(p-2) % p 小费马定理 
    
    return 0;
}