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

题目描述

  Given , find the value of .
  It can be proved that the value is a rational number .
  Print the result as .

输入描述

  The input consists of several test cases and is terminated by end-of-file.
  Each test case contains an integer .
  . The number of test cases does not exceed .

输出描述

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

示例1

输入

1
2
3

输出

166374059
432572553
591816295

备注

  For , .

分析

  令 ，利用分部积分法求解。

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

代码

/******************************************************************
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;
}