O(n)WA求助
  • 板块P1375 小猫
  • 楼主xueruo
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/6/2 19:57
  • 上次更新2023/10/23 14:04:46
查看原帖
O(n)WA求助
638718
xueruo楼主2023/6/2 19:57

#include<iostream>
#include<cstdio> 
#define int long long
#define F(i,j,n) for(register int i=j;i<=n;++i)
using namespace std;
const int N=1e6+5;
int mod=1000000007;
int n;
int f[N],inv[N];
signed main(){
	cin>>n;
	f[0]=1;
	register int p=mod;
	inv[0]=inv[1]=1;
	for(register int i=2;i<=n+2;i++)inv[i]=(p-p/i)*inv[p%i]%p;
	
//	F(i,0,n)printf("inv[%lld]=%lld ",i,inv[i]);
//	puts("");
	
	for(int i=1;i<=n;i++)
		f[i]=f[i-1]*((4*i-2)*inv[i+1])%mod;
	cout<<f[n];
	return 0;
}
2023/6/2 19:57
加载中...