文章目录[x]
- 1:题目链接
- 2:题面
- 3:题意
- 4:思路
- 5:参考代码
题目链接
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;
}