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

题目链接

https://ac.nowcoder.com/acm/contest/5666/J

题面

题意

对于给定$n(n\leq10^6)$求$\int_{0}^{1}\left(x-x^{2}\right)^{n} \mathrm{d} x$，答案取$mod,mod=998244353$

思路

首先题目说答案一定是一个分数，并给定了$mod$，显然要用到逆元

刚开始想着求原函数，结果很傻发现求不出来，求着求着发现和二项展开类似，结果回去反推样例，发现样例1,2,3分别对应的是1/6，1/30，1/140，然后提出一个系数$\frac{1}{n+1}$，发现1/3，1/10，1/35正好满足$\quad C_{2 n+1}^{n+1}$,然后get答案就是$\frac{1}{(n+1) \cdot C_{2 n+1}^{n+1}}$

下面给出赛后直接推积分的过程：

$\int_{0}^{1}\left(x-x^{2}\right)^{n} d x=\int_{0}^{1} x^{n}(1-x)^{n} d x$

$=\frac{1}{n+1} \int_{0}^{1}\left(x^{n+1}\right)^{\prime}(1-x)^{n} d x$

$=\left.x^{n+1} \cdot(1-x)^{n}\right|_{0} ^{1}-\int_{0}^{1} x^{n+1}\left[(1-x)^{n}\right]^{\prime} d x$

$=\frac{n \int_{0}^{1} x^{n+1}(1-x)^{n-1} d x}{n+1}$

依次类推$\cdots$
$=\frac{n\cdot(n-1) \cdots 1\cdot \int_{0}^{1} x^{2 n} d x}{(n+1) \cdot(n+2) \cdots 2 n}$

$=\frac{n !}{(n+1) \cdots(2 n+1)}$

上下同时乘$n!$得：$\frac{(n!)^{2}}{(2 n+1) !}$

又$\because \quad C_{2 n+1}^{n+1}=\frac{(2 n+1) !}{(n+1) ! n !}$

$\therefore$ 原式$=\frac{1}{(n+1) \cdot C_{2 n+1}^{n+1}}$

得到了原式的分式就很简单了，直接输出其逆元，因为有组合数，且$n$达$1e6$，所以用阶乘取模$O(n)$递推组合数即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int M = 2e6 + 10;
const int mod = 998244353;
LL fac[M];
LL pow_mod(LL a, LL b) {
  LL ans = 1;
  while (b) {
    if (b & 1)
      ans = (ans * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return ans;
}
LL inv(LL a) { return pow_mod(a, mod - 2); }
void init() {
  LL p = mod;
  fac[1] = 1;
  for (int i = 2; i <= M; i++) {
    fac[i] = fac[i - 1] * i % p;
  }
}
LL C(LL n, LL m) {
  return fac[m] * pow_mod(fac[n], mod - 2) % mod * pow_mod(fac[m - n], mod - 2) % mod;
}
void solve() {
  LL n;
  init();
  while (~scanf("%lld", &n)) {
    LL ans = 1;
    ans = (n+1) * C(n + 1, n * 2 + 1) % mod;
    printf("%lld\n", inv(ans));
  }
}
signed main() {
  solve();
  return 0;
}