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;
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论