Easy Integration 2020牛客多校第一场

题意

思路

  手动算出n=1,2,3时答案为6,30,140的倒数,用oeis查询得到答案。

  但正解是用分部积分:

   我们预处理出1e6以内的阶层和逆元,注意逆元可以只处理maxn,然后逆推压复杂度。

AC代码

include<iostream>

using namespace std;
typedef long long ll;
const int maxn=2e6+5;
int n;
ll ans;
ll p=998244353;
ll num[maxn],numv[maxn];
ll mypow(ll x,ll n,ll m){

ll res=1;
while(n){
    if(n&1) res=res\*x%m;
    x=x\*x%m;
    n>>=1;
}
return res;

}
ll inv(ll x){

return mypow(x,p-2,p);

}
ll c(int n,int m){

if(m>n) return 0;
return (num\[n\]\*inv(num\[m\])%p)\*inv(num\[n-m\])%p;

}
ll lucas(ll n,ll m){

if(m==0) return 1;
return lucas(n/p,m/p)\*c(n%p,m%p)%p;

}
void init(){

num\[0\]=1;
for(int i=1;i<=maxn;i++){
    num\[i\]=(num\[i-1\]\*i)%p;
}
numv\[maxn\]=inv(num\[maxn\]);
for(int i=maxn-1;i>=1;i--){
    numv\[i\]=numv\[i+1\]\*(i+1)%p;
}

}
int main()
{

//cout<<inv(30)<<endl;
init();
while(cin>>n){
    ans=(num\[n\]\*num\[n\])%p;
    ans=ans\*numv\[2\*n+1\]%p;
    cout<<ans<<'\\n';
}
return 0;

}

评论

暂无评论