【2020年牛客暑假第一场】J题 Easy integration

传送门：https://ac.nowcoder.com/acm/contest/5666/J

题意

题目描述 Given n, find the value of$\int_{0}^{1}(x-x^2)^ndx$ It can be proved that the value is a rational number$\frac{p}{q}$ Print the result as$(p⋅q^{-1})mod$ $998244353$.

输入描述 The input consists of several test cases and is terminated by end-of-file.

Each test case contains an integer n.

$1\leq n \leq10^6$. The number of test cases does not exceed $10^5$.

输出描述 For each test case, print an integer which denotes the result.

输入 $1$ $2$ $3$

输出 $166374059$ $432572553$ $591816295$

思路

根据$\int_{0}^{1}(x-x^2)^ndx$可得$\int_{0}^{1}x^{n}(1-x)^ndx$。 利用n次分部积分法可得计算式$$\frac{1*2*…*(n-1)*n}{(n + 1)*(n+2)*….*(2n)*(2n+1)}$$ 上下同乘$n!$得 $$\frac{(n!)^2}{(2n+1)!}$$

先对阶乘做一个预处理，然后就成分子除以分母，可以用逆元（费马小定理）求。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

##define INF 0x7f7f7f
##define mem(a,b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)
//const ll mod = 1e9 + 7;
// const int maxn = 1e5 + 10;

const ll mod = 998244353;
int n;

ll f[2000005];

ll FPM(ll x,ll power)
{
    ll ans = 1;
    while(power)
    {
        if(power & 1)
        {
            ans = (ans * x) % mod;
        }
        x = (x * x) % mod;
        power >>= 1;
    }
    return ans % mod;
}

void F()
{
    f[0] = 1;
    for(int i = 1;i <= 2000001; i++)
    {
        f[i] = f[i - 1] * i % mod;
    }
}

void solve()
{
    F();
    while(scanf("%d",&n)!=EOF)
    {
        ll ans = f[n] * f[n] % mod;
        ans = (ans * FPM(f[2 * n + 1], mod - 2)) % mod;
        printf("%lld\n",ans % mod);
    }
}

signed main()
{
    //ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
##else
    //ios::sync_with_stdio(false);
    int T = 1;
    //cin >> T;
    while(T--)
        solve();
##endif
    return 0;
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/07/12/2020-nowcoder-shujia-1-j/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！