2020暑期D1-J（代码+反思）

简单图证：

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;

const LL mod = 998244353;
const LL N = 1010000;
LL fib[2 * N + 2];
LL x1;
LL x2;
LL n;

void set(LL X)
{
fib[1] = 1;
fib[2] = 2;
for(int i=3;i<=(2*N+1);i++)
fib[i] = (fib[i - 1] * i) % mod;
}

LL pow_mod(LL a, LL b, LL p) {//a的b次方取余p
LL ret = 1;
while (b) {
if (b & 1)
ret = (ret * a) % p;
a = (a * a) % p;
b >>= 1;
}
return ret;
}

int main()
{
LL i = 1;
set(N);
while (scanf("%lld", &n)!=EOF)
{
x2 = fib[n] * fib[n]%mod;
x1 = fib[2 * n + 1]%mod;
x2 = pow_mod(x2, mod - 2, mod)%mod;
x2 = x2 * x1 % mod;
printf("%lld\n", pow_mod(x2, mod - 2, mod));
}
}

原：

void set(int a)
{
fib[1] = 6;
fib[2] = 30;
fib[3] = 140;


for (int i = 4; i <= a; i++)
{
    fib[i] = (2 * (2 * i + 1) * fib[i - 1] / i)%mod;
}


}

慎用除法。（乘数过大超出范围导致必须取mod，mod后导致无法整除，以致数据错误）
推荐使用大数相乘，若需除法推荐快速幂（费马定理）
由费马定理可知，当n为质数时
b ^ (n - 1) ≡ 1 (mod n)
拆一个b出来可得 b * b ^ (n - 2) ≡ 1 (mod n)
故当n为质数时，b的乘法逆元 x = b ^ (n - 2)
pow_mod(a,mod-2,mod);(a求逆元)

https://www.cnblogs.com/slp0622/p/8998522.html（快速幂+快速乘）

故使用阶乘数组以用乘法+逆元来代替除法。
void set（LL X）{}