进食后人
  • 板块P1375 小猫
  • 楼主naturelyf
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/20 09:59
  • 上次更新2024/11/20 14:44:55
查看原帖
进食后人
476473
naturelyf楼主2024/11/20 09:59

如果你 WA 最后一个点,看看是不是数组开小了吧,组合数求的时候有 2n2n

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+100,P=1e9+7;
int fac[N],inv[N];
int qmi(int a,int b){
	int res=1;
	while(b){
		if(b&1)res=res*a%P;
		b>>=1;
		a=a*a%P;
	}
	return res;
}
void init(){
	fac[0]=1;
	for(int i=1;i<N;i++)
		fac[i]=fac[i-1]*i%P;
	inv[N-1]=qmi(fac[N-1],P-2);
	for(int i=N-2;i>=0;i--)
		inv[i]=inv[i+1]*(i+1)%P;
}
int C(int n,int m){
	if(m>n)return 0;
	if(m==0)return 1;
	return fac[n]*inv[m]%P*inv[n-m]%P;
}
signed main(){
	init();
	int n;
	cin>>n;
	cout<<(C(n*2,n)-C(n*2,n-1)+P)%P;
	return 0;
}
2024/11/20 09:59
加载中...