Easy Integration(积分)

题目链接：https://ac.nowcoder.com/acm/contest/5666/J
解题思路：
要是你知道沃里斯公式，就知道这是个结论，但要是你不知道就老老实实积分吧。

再做一遍换元，然后作二项式展开。

最后写出W1,W2,W3...找找规律解决。

这道题还可以用分部积分法来做。(是不是求着求着就发现其实结构相似)

最后推出来的公式里有分母中n！阶乘的逆元的话打个表就搞定了。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6;
const ll MOD=998244353;
ll inv[maxn+10],fac[2*maxn+10];

ll q_pow(ll a, ll b, ll m){
    ll ans = 1;
    while(b > 0){
        if(b & 1){
            ans = ans * a % m;
        }
        a = a * a % m;
        b >>= 1;
    }
    return ans;
}

void pre()
{
    inv[0]=1ll;
    fac[0]=1ll;
    for(int i=1;i<=2*maxn+1;i++) {
        fac[i] = fac[i-1]*i % MOD;
    }
    for(int i=1;i<=maxn;i++){
        inv[i]=q_pow(fac[i], MOD-2, MOD);
    }
}

int main()
{
    pre();
    ll n, ans;
    while(scanf("%lld",&n)!=EOF){
        ans = q_pow(((fac[2*n+1] * inv[n]) % MOD * inv[n]) % MOD, MOD-2, MOD);
        printf("%lld\n",ans);
    }
}