记录编号	143100	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]礼物(魏铭)	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.088 s
提交时间	2014-12-12 23:02:27	内存使用	6.51 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int SIZEP=100010;
vector<LL> Prime_Table;
LL Quick_Pow(LL a,LL n,LL mod){
	LL ans=1;
	while(n){
		if(n&1) ans=(ans*a)%mod;
		a=(a*a)%mod;
		n>>=1;
	}
	return ans;
}
void Extend_GCD(LL a,LL b,LL &x,LL &y,LL &d){//ax+by=d
	if(b==0){x=1,y=0,d=a;}
	else{Extend_GCD(b,a%b,y,x,d);y-=(a/b)*x;}
}
LL Inverse(LL a,LL m){//a在模m意义下的逆元
	LL x,y,d;
	Extend_GCD(a,m,x,y,d);
	return x;
}
LL China(LL m[],LL a[],LL n,LL M){//模m[i]余a[i],i从1到n,m[i]两两互质,乘积为M
	LL ans=0;
	for(int i=1;i<=n;i++){
		LL w=M/m[i];
		ans+=w*Inverse(w,m[i])*a[i];
		ans%=M;
	}
	return (ans+M)%M;
}
class Number{
public:
	LL m,p,r,c;
	//m是素数p的幂,当前数值中含p^c,其余模m余s
	void operator = (pair<LL,LL> t){//指定模的值,并初始化为1
		m=t.first,p=t.second;
		r=1,c=0;
	}
	void print(void){printf("(%lld*%lld^%lld mod %lld)",r,p,c,m);}
};
void print(Number n){n.print();}
Number operator * (Number a,LL t){
	while(t%a.p==0) a.c++,t/=a.p;
	a.r=(a.r*t)%a.m;
	return a;
}
Number operator * (Number a,Number b){//要求a.p=b.p
	a.c+=b.c;
	a.r=(a.r*b.r)%a.m;
	return a;
}
Number operator / (Number a,Number b){//要求必须整除,且模同一个数
	a.r=(a.r*Inverse(b.r,a.m))%a.m;
	a.c-=b.c;
	return a;
}
Number Calc_Frac(const LL f[],LL n,LL m,LL p){//n!模m,m是p的幂,f中存放0!~m!(除去所有p的因子)
	Number ans;ans=make_pair(m,p);
	ans=(ans*f[n%m])*Quick_Pow(f[m],n/m,m);//先把非p的倍数都算上
	if(n>=p){
		//然后我们计算p的倍数们
		ans=ans*Calc_Frac(f,n/p,m,p);//p的所有倍数除掉一个p
		ans.c+=n/p;//将这些p的幂算上
	}
	return ans;
}
void Sieve_Prime(vector<LL> &prime){//筛素数
	static bool flag[SIZEP]={0};
	for(LL i=2;i<SIZEP;i++){
		if(!flag[i]){
			prime.push_back(i);
			for(LL j=i*i;j<SIZEP;j+=i) flag[j]=true;
		}
	}
}
void Fractorization(LL n,Number f[],LL &tot){
	tot=0;
	for(int i=0;i<(int)Prime_Table.size();i++){
		LL &p=Prime_Table[i];
		if(n%p) continue;
		tot++;f[tot]=make_pair(1,p);
		while(n%p==0){
			f[tot].c++;
			f[tot].m*=p;
			n/=p;
		}
	}
}
LL P;
LL fnum;
Number fact[SIZEP];
LL N,M;//买N件礼品送给M个人
LL W[SIZEP];
Number Calc_Prime(int k){//模第k个素因子
	LL p=fact[k].p,m=fact[k].m;
	static LL f[SIZEP];
	f[0]=1;
	for(LL i=1;i<=m;i++){
		f[i]=f[i-1];
		if(i%p) f[i]=(f[i]*i)%m;
	}
	Number ans;ans=make_pair(m,p);
	for(int i=1;i<=M;i++)
		ans=ans*Calc_Frac(f,W[i],m,p);
	ans=Calc_Frac(f,N,m,p)/ans;
	return ans;
}
void Process(void){
	if(W[M]<0){
		printf("Impossible\n");
		return;
	}
	static LL m[SIZEP],a[SIZEP];
	for(int i=1;i<=fnum;i++){//计算这个
		Number now=Calc_Prime(i);
		m[i]=fact[i].m;
		a[i]=(now.r*Quick_Pow(fact[i].p,now.c,m[i]))%m[i];
	}
	printf("%lld\n",China(m,a,fnum,P));
}
void Initialize(void){
	scanf("%lld",&P);
	Fractorization(P,fact,fnum);
	scanf("%lld%lld",&N,&M);
	LL s=N;
	for(int i=1;i<=M;i++){
		scanf("%lld",&W[i]);
		s-=W[i];
	}
	W[M+1]=s;
	M++;//多加一个物品,让形式更优美
}
int main(){
	freopen("nt2011_gift.in","r",stdin);
	freopen("nt2011_gift.out","w",stdout);
	Sieve_Prime(Prime_Table);
	Initialize();
	Process();
	return 0;
}