【J-Easy Integration】题解（不使用Wallis' Integral版）

这道题先换元 $x=sin^2t$ 后使用Wallis' Integral可以得到通项公式，步骤比较短，这里不再赘述。
这里写一个不使用Wallis' Integral的推导（PS：虽说是不使用Wallis' Integral，实际上还是采用了类似于推导Wallis' Integral的Recurrence relation的思路）

正文：
Let $u(x) = x$ , $v(x) = (x - x^2)^n$ , then $du = 1$ and $dv = n(1 - 2x)(x-x^2)^{n-1}$ .

$\begin{align} I_n & = \int_0^1 (x - x^2)^n dx \\ & = -\int_0^1 nx(1-2x)(x-x^2)^{n-1}dx \\ & = \int_0^1 x(x-x^2)^{n-1}dx - 2n\int_0^1(x-x^2)^ndx \\ & = \int_0^1x(x-x^2)^{n-1}dx - 2n \cdot I_n \end{align}$

Let $T_n = \int_0^1 x(x-x^2)^ndx$ , $u = \frac{1}{2}x^2$ , $v = (x-x^2)^n$ , then $du = x$ , $dv = n(1-2x)(x-x^2)^{n-1}$ .

$\begin{align} T_n & = -\frac{n}{2} \int_0^1 x(x-2x^2)(x-x^2)^{n-1}dx \\ & = -\frac{n}{2} \int_0^1 x(x-x^2)^ndx + \frac{n}{2} \int_0^1 x^3(x-x^2)^{n-1}dx \\ & = -\frac{n}{2}T_n + \frac{n}{2} \int_0^1 x(x-(x-x^2))(x-x^2)^{n-1} \\ & = -\frac{n}{2}T_n + \frac{n}{2}\int_0^1 x^2(x-x^2)^{n-1}dx - \frac{n}{2}T_n \\ &= -nT_n + \frac{n}{2}T_{n-1} - \frac{n}{2}I_n \end{align}$ .

Then

$I_n = nT_{n-1} - 2nI_n \Rightarrow I_n = \frac{n}{2n+1} \cdot T_{n-1}$ .

$T_n = -nT_n + \frac{n}{2} T_{n-1} - \frac{n}{2}I_n \Rightarrow T_n = \frac{n}{2(n+1)}(T_{n-1} - I_n)$ .

因为目标是写出程序即可，不推通项公式也很好算，这个只需要预先初始化好 $I_1,\ I_2,\ T_1$ 就可以开始推了。

C++：

#include <bits/stdc++.h>

#define lo(i, n, m) for (int i = n; i < m; i++)
#define loe(i, n, m) for (int i = n; i <= m; i++)
#define rlo(i, n, m) for (int i = n - 1; i >= m; i--)
#define rloe(i, n, m) for (int i = n; i >= m; i--)
#define pb push_back
#define mk make_pair
#define scd(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define sclf(x) scanf("%lf", &x)
#define scll(x) scanf("%lld", &x)
#define clr(a, b) memset((a), (b), sizeof(a))
#define fi first
#define se second
typedef long long ll;
using namespace std;
// const int INF = 0x3f3f3f3f;
// const int INF = 0x7fffffff;
// const LL INF = 0x3f3f3f3f3f3f3f3f;
// const LL INF = 0x7fffffffffffffff;
const int NIL = -1;
template <class T>
inline T mx(T a, T b) {return a > b ? a : b;}
template <class T>
inline T mi(T a, T b) {return a < b ? a : b;}
template <class T>
inline void sw(T &a, T &b) {
    T t = a; a = b; b = t;
}
template <class T>
inline T mabs(T x) {return x < 0 ? -x : x;}
inline char gc() {
    char ret;
    while ((ret = getchar()) == ' ' || ret == '\n' || ret == '\t');
    return ret;
}
template <class T>
inline T sq(T x) {return x * x;}
const int lim = 1e6 + 10;
const ll mod = 998244353ll;
ll I[lim] = {0, 166374059, 432572553, 591816295}, T[lim];
inline ll add(ll a, ll b) {
    return (a + b) % mod;
}
inline ll sub(ll a, ll b) {
    return ((a - b) % mod + mod) % mod;
}
inline ll mul(ll a, ll b) {
    return a * b % mod;
}
inline ll Div(ll a, ll b) {
    static bool doinit = true;
    const static int sz = 1e5 + 10;
    const static ll p = mod;
    static int inv[sz];
    if (doinit) {
        inv[1] = 1;
        for (int i = 2; i < sz; ++i)
            inv[i] = (long long)(p - p / i) * inv[p % i] % p;
        doinit = false;
    }
    if (b < sz) {
        return (long long)a * inv[b] % p;
    } else {
        int pw = p - 2;
        long long ret = (a % p + p) % p;
        do {
            if (pw & 1) ret = ret * b % p;
            b = (long long)b * b % p;
        } while (pw >>= 1);
        return ret;
    }
}
int main() {
    int n;
    T[1] = Div(1, 12);
    T[2] = Div(1, 60);
    loe(i, 3, 1000000) {
        I[i] = Div(T[i - 1], add(mul(2, i), 1));
        I[i] = mul(I[i], i);
        T[i] = sub(T[i - 1], I[i]);
        T[i] = mul(T[i], Div(i, mul(2, add(i, 1))));
    }
    while (~scd(n)) {
        printf("%lld\n", I[n]);
    }
    return 0;
}