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

题目

2020牛客暑期多校训练营（第一场）J题 [题目链接](链接：https://ac.nowcoder.com/acm/contest/5666/J) 

题解

The value is (n!)^2 / (2n+1)!
暂时不太懂

逆元

    (a + b) % p = (a%p + b%p) %p;
    (a - b) % p = (a%p - b%p) %p;
    (a * b) % p = (a%p * b%p) %p;
    (a / b) % p = (a%p / b%p) %p; 除法是不满足分配律的

    # 乘法逆元
        满足 a * x ≡ 1 (mod p) , 即a 与 x互为逆元 乘法逆元的充要条件是 a与x 互质 gcd(a,p)= 1
        求解逆元 可以用 费马小定理 、 扩展欧几里得 、线性递推
    # 费马小定理
        a 是 一个整数 p 是一个质数
        a^p ≡ a (mod p) 如果a是p 的倍数
    *(逆元使用此性质)   a^(p-1) ≡ 1 (mod p) 如果a 不是p 的倍数
        ---------------------------------------------------------------
        a * a^(p-2) ≡ 1 (mod p) 真正求出来的逆元是 a^(p-2) % p 通常使用快速幂
        同余式 ： a ≡ p (mod n) 表示a 和b 对模n 同余, 即正整数a-b能被n整除

快速幂

 ll power(ll a,ll b,ll p)
 {
     int ans = 1 % p;
     for(;b;b>>=1){
         if(b&1) ans = ans * a % p;
         a = a * a% p;
     }
     return ans;
 }

AC代码

#include <iostream>
#define ll long long
using namespace std;

const ll N = 2000010;
const ll mod = 998244353;
ll n;
ll q[N];
//快速幂模板
 ll power(ll a,ll b,ll p)
 {
     int ans = 1 % p;
     for(;b;b>>=1){
         if(b&1) ans = ans * a % p;
         a = a * a% p;
     }
     return ans;
 }
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0); 
    q[0] = 1;
    for(int i = 1;i< N;i++)
        q[i] = (q[i-1] * i ) % mod; 

    while( cin >> n)
    {
        cout<< q[n] * q[n] % mod * power(q[2*n+1], mod -2 ,mod) %mod<<endl; 
     } 

    return 0;
}