链接
https://ac.nowcoder.com/acm/contest/5666/J
题意
已知 $\int_0 ^1(x-x^2)^ndx$ 解为分数形式 $\frac{p}{q}$，求 $(p*q^{-1}) \bmod 998244353$
思路
$\begin{aligned}
\int _0 ^1(x-x^2)^ndx & =\int _0 ^1(1-x)^nx^ndx \
& =\frac{(1-x)^n x^{n+1}}{n+1}\bigg|_0^1+\frac{n}{n+1}\int _0 ^1(1-x)^{n-1}x^{n+1}dx \
& =\frac{n}{n+1}\int 0 ^1(1-x)^{n-1}x^{n+1}dx \
& =\frac{n!}{P{2n+1}^{n+1}} \
& =\frac{(n!)^2}{(2n+1)!}
\end{aligned}$
得：$p=1,q=\frac{(2n+1)!}{(n!)^2}$
代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int N=1e6+5;
ll fac[N+N],infac[N];
ll ksm(ll a,int b) {
ll res=1;
while(b) {
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int main() {
fac[0]=1;
for(int i=1;i<=2000001;i++) fac[i]=fac[i-1]*i%mod;
infac[1000000]=ksm(fac[1000000],mod-2);
for(int i=1000000-1;i>=1;i--) infac[i]=infac[i+1]*(i+1)%mod;
int n;
while(~scanf("%d",&n)) {
printf("%lld\n",ksm(fac[2*n+1]*infac[n]%mod*infac[n]%mod,mod-2));
}
return 0;
}
|