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

文章目录[x]
  1. 1:题目链接
  2. 2:题面
  3. 3:题意
  4. 4:思路
  5. 5:参考代码




J

题目链接

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

题面

题意

对于给定,答案取

思路

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

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

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

依次类推

上下同时乘得:

原式

得到了原式的分式就很简单了,直接输出其逆元,因为有组合数,且,所以用阶乘取模递推组合数即可。

参考代码

#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;
}

 


点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像