J:Easy Integration_牛客博客

nowcoder-contest/5666/J

1 题目描述

Given n, find the value of $\int_{0}^{1}(x-x^2)^n dx$ 。
It can be proved that the value is a rational number $\frac{p}{q}$ .
Print the result as $(p\cdot q^{−1})$ mod998244353.

2 分析

本题是一个积分题， $q^{-1}$ 的意思是求出q的逆元，要这么理解，然后乘以p，再mod。

关键是我们求这个积分，这个积分可以进行如下化简：
$=\int_{0}^{1}x^n\cdot (1-x)^n dx \\ =\frac{x^{n+1}}{n+1}|_{0}^{1}+\int_{0}^{1}\frac{x^{n+1}}{n+1}\cdot n \cdot (1-x)^{n-1}dx\; 分部积分 \\ =\frac{n}{n+1}\int_{0}^{1}x^{n+1}\cdot (1-x)^{n-1}dx \; 这样不断分部积分\\ =\frac{n!}{(n+1)(n+2)...(2n)}\cdot \int_{0}^{1}x^{2n}dx \\ =\frac{(n!)^2}{(2n+1)!}$
于是我们可以预处理所有阶乘mod998244353的值，逆元可以用费马小定理或者扩欧来做。

3 代码

#include<bits/stdc++.h>
using namespace std;  
int const N=2e6+10;  
int const M=998244353;
int f[N],n;  
int ksm(int x,int y){
    int res=1;  
    while (y) {
        if(y&1) res=1LL*res*x%M;  
        y>>=1; 
        x=1LL*x*x%M;  
    }
    return res;  
}
int main(){
    f[0]=1;  
    for(int i=1;i<N;i++)
        f[i]=1LL*f[i-1]*i%M;  
    while (scanf("%d",&n)==1){
        printf("%d\n",1LL*f[n]*f[n]%M *ksm(f[2*n+1],M-2)%M);  
    }
    return 0; 
}