2020牛客暑期多校训练营（第一场）J

题目描述

Given $n$ , find the value of $\int_0^1 (x - x^2)^n \mathrm d x$ .
It can be proved that the value is a rational number $\frac{p}{q}$ .
Print the result as $p \cdot q^{-1} \bmod 998244353$ .

输入描述

The input consists of several test cases and is terminated by end-of-file.
Each test case contains an integer $n$ .
$1 \leqslant n \leqslant 10^6$ . The number of test cases does not exceed $10^5$ .

输出描述

For each test case, print an integer which denotes the result.

示例1

输入

1
2
3

输出

166374059
432572553
591816295

备注

For $n = 1$ , $\int_{0}^1 (x - x^2) \mathrm{d} x = \frac{x^2}{2} - \frac{x^3}{3} |_0^1 = \frac{1}{6}$ .

分析

令 $I=\int_0^1 (x - x^2)^n \mathrm d x=\int_0^1x^n(1-x)^n\mathrm dx$ ，利用分部积分法求解。

$\begin{aligned}I&=\int_0^1x^n(1-x)^x\mathrm dx\\&=\frac{n}{n+1}\int_0^1x^{n+1}(1-x)^{n-1}\mathrm dx\\&=\frac{n(n-1)}{(n+2)(n+1)}\int_0^1x^{n+2}(1-x)^{n-2}\mathrm dx\\&\quad\quad\quad\quad\quad\quad\quad\quad\quad\vdots\\&=\frac{n(n-1)(n-2)\cdots}{(2n+1)(2n)\cdots(n+1)}\\&=\frac{(n!)^2}{(2n+1)!} \end{aligned}$

预处理阶乘后，只需要计算逆元即可得到答案。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第一场） Problem J
Date: 8/10/2020 
Description: Integration
*******************************************************************/
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=1000004;
const ll mod=998244353;
ll fac[N<<1];
int n;
void init();
ll qpow_mod(ll,ll);
int main()
{
    init();
    while(~scanf("%d",&n)) 
    {
        ll up=fac[n]*fac[n]%mod;//分子
        ll down=qpow_mod(fac[2*n+1],mod-2);//分母
        printf("%lld\n",up*down%mod);
    }
    return 0;
}
void init()//预处理
{
    fac[0]=1;
    const int SIZE=1000000*2+1;
    for(register int i=1;i<=SIZE;i++) 
    {
        fac[i]=fac[i-1]*(ll)i;
        fac[i]%=mod;
    }
}
ll qpow_mod(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1; 
    }
    return res;
}