数论题目（快速幂+贝塔函数+乘法逆元）

题目来源： https://ac.nowcoder.com/acm/contest/5666/J

比赛开始看到这题还以为是逐项找规律，最后发现规律错了...... 哎，看了大佬解答才知道这是一个贝塔函数的运用（数学博大精深），得到一个递推式后还没完。关键还需要用到快速幂和大数乘法。推荐使用大数相乘，相除，除法用快速幂（费马定理）。由费马定理可知，当n为质数时，a^ (n - 1) =1 (mod n)，拆一个a出来可得 a * a ^ (n - 2) =1 (mod n)，故当n为质数时，a的乘法逆元 x = a ^ (n - 2)。（如果ax≡1 (mod p),且gcd(a,p)=1（a与p互质），则称a关于模p的乘法逆元为x），用这个乘法逆元来代替除法。
简单而言就是:(n!)^2/(2n+1)!（推导见图片）,取模998244353。
具体解法思路就是：x2 = f[n] * f[n]%mod，x2来代替(n!)^2；x1 = f[2 * n + 1]%mod，x1来代替(2n+1)!。其中（f『』数组算阶乘），用费马定理对x2做一下转换
处理，最后乘法逆元得结果。

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;

const ll mod = 998244353;
const ll N=1010000;
ll f[2 * N + 2];
ll x1;
ll x2;
ll n;

    void jiechen()              //预处理将对应的阶乘先存下来 
    {
        f[1] = 1;
        f[2] = 2;
        for(int i=3;i<=(2*N+1);i++)
        f[i] = (f[i - 1] * i) % mod;
    }

    ll pow_mod(ll a, ll b, ll p) //a的b次方对p取余 
    {
        ll ret = 1;
        while (b) 
        {
            if (b&1)
            ret=(ret * a)%p;
            a=(a * a) % p;
            b>>= 1;
        }
        return ret;        //取余之后的快速幂 
    }                    

    int main()
    {
        jiechen();
        while (cin>>n)
        {
            x2 = f[n] * f[n]%mod;
            x1 = f[2 * n + 1]%mod;
            x2 = pow_mod(x2, mod - 2, mod)%mod;
            x2 = x2 * x1 % mod;                //费马定理求逆元 
            cout<<pow_mod(x2, mod - 2, mod)<<endl;
        }
    }