链接
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; }
|