记录编号	406432	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]前缀和不小于零	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.198 s
提交时间	2017-05-18 18:23:21	内存使用	0.29 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
struct fc{ll p,a;}a[4];//x=a %p
void ex_gcd(ll &x,ll &y,ll a,ll b,ll c){
	if (!b) return void(x=c/a);
	ex_gcd(y,x,b,a%b,c);
	y-=a/b*x;
}
void merge(fc &a,fc b){
	ll p=a.p*b.p,x,y,ans;
	ex_gcd(x,y,a.p,b.p,b.a-a.a);
	x%=b.p;
	ans=((x*a.p+a.a)%p+p)%p;
	a=(fc){p,ans};
}
int getmi(int n,int p){
	int ans=0;
	for (;n;n/=p,ans+=n);
	return ans;
}
int getval(int n,int p){//求n!%p忽略0 
	if (n<p){
		int ans=1;
		for (int i=1;i<=n;i++) ans=(ll)ans*i%p;
		return ans;
	}
	int ans=(n/p)&1?-1:1;
	ans*=getval(n/p,p);
	//整除部分由威尔逊定理可知,(p-1)!=1 %p 
	n%=p;
	for (int i=1;i<=n;i++) ans=(ll)ans*i%p;
	return ans<0?ans+p:ans;
}
ll mul(ll x,ll y,ll p){
	ll ans=0;
	for (;y;y>>=1,x=(x<<1)%p)
		if (y&1) ans=(ans+x)%p;
	return ans;
}
ll power(ll x,ll y,ll p){
	ll ans=1;
	for (;y;y>>=1,x=mul(x,x,p))
		if (y&1) ans=mul(ans,x,p);
	return ans;
}
ll inv(ll x,ll p){return power(x,p-2,p);}
int catalan(int n,int p){
	if (getmi(n*2,p)!=getmi(n,p)+getmi(n+1,p)) return 0;
	return (ll)getval(n*2,p)*inv((ll)getval(n,p)*getval(n+1,p)%p,p)%p;
}
int n,m,p;
int main()
{
	freopen("overzero.in","r",stdin);
	freopen("overzero.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		scanf("%d",&p);
		a[i]=(fc){p,catalan(n,p)};
	}
	ll ans=0,p=1;
	for (int i=1;i<=m;i++) p*=a[i].p;
	for (int i=1;i<=m;i++)
		ans=(ans+mul(mul(a[i].a,inv(p/a[i].p,a[i].p),p),p/a[i].p,p))%p;
	printf("%lld\n",ans);
	return 0;
}