AcWing 889. 满足条件的01序列
原题链接
简单
作者:
WULI
,
2020-09-02 01:46:21
,
所有人可见
,
阅读 384
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll p=1e9+7;
ll quick_pow(ll x,ll y)
{
ll ans=1;
while(y){
if(y&1)ans=(ans*x)%p;
x=(x*x)%p;
y>>=1;
}
return ans%p;
}
ll C(ll a,ll b)
{
ll res=1;
for(ll i=1,j=a;i<=b;i++,j--){
res=res*j%p;
res=res*quick_pow(i,p-2)%p;
}
return res;
}
ll Lucas(ll a,ll b)
{
if(a<p&&b<p)return C(a,b);
return C(a%p,b%p)*Lucas(a/p,b/p)%p;
}
int main()
{
int n;
cin>>n;
cout<<((Lucas(2*n,n)-Lucas(2*n,n-1))%p+p)%p<<endl;//取模防止结果为负数
return 0;
}