Description

【题意】# [国家集训队] 礼物
一年一度的圣诞节快要来到了。每年的圣诞节小 E 都会收到许多礼物，当然他也会送出许多礼物。不同的人物在小 E 心目中的重要性不同，在小 E 心中分量越重的人，收到的礼物会越多。
小 E 从商店中购买了 $n$ 件礼物，打算送给 $m$ 个人，其中送给第 $i$ 个人礼物数量为 $w_i$。请你帮忙计算出送礼物的方案数（两个方案被认为是不同的，当且仅当存在某个人在这两种方案中收到的礼物不同）。由于方案数可能会很大，你只需要输出模 $P$ 后的结果。

【输入格式】
输入的第一行包含一个整数 $P$，表示模数。  
第二行包含两个整数 $n$ 和 $m$，分别表示小 E 从商店购买的礼物数和接受礼物的人数。  
第 $3$ 到第 $(m + 2)$ 行，每行一个整数，第 $(i + 2)$ 行的整数 $w_i$ 表示送给第 $i$ 个人的礼物数量。

【输出格式】
若不存在可行方案，则输出 `Impossible`，否则输出一个整数，表示模 $P$ 后的方案数。

【样例输入 #1】
100
4 2
1
2

【样例输出 #1】
12

【样例输入 #2】
100
2 2
1
2

【样例输出 #2】
Impossible

【 样例 1 解释】
以 `/` 分割，`/` 前后分别表示送给第一个人和第二个人的礼物编号。$12$ 种方案详情如下：
```plain
1/23 1/24 1/34
2/13 2/14 2/34
3/12 3/14 3/24
4/12 4/13 4/23
```
【数据规模与约定】
设 $P= \prod_{i=1}^t p_i^{c_i}$，$p_i$ 为质数。
对于 $15\%$ 的数据，$n\leq 15$，$m\leq 5$，$p_i^{c_i}\leq 10^5$。
在剩下的 $85\%$ 数据中，约有 $60\%$ 的数据满足 $t\leq 2$，$c_i=1$，$p_i\leq 10^5$，约有 $30\%$ 的数据满足 $p_i\leq 200$。
对于 $100\%$ 的数据，$1\leq n\leq 10^9$，$1\leq m\leq 5$，$1\leq p_i^{c_i}\leq 10^5$，$1\leq w_i \leq P\leq 10^9$。

Hint

by hansang

/*  by；hansang 
(如果学会 exLucas ，着重理解 solve函数就行) 
exLucas 求的是 C nm %P (P不一定是质数)，把 C nm 设为 x

把 P 化为 p1^k1p2^k2... (pi是质数)
列出式子：
x % (p1^k1) = a1
x % (p2^k2) = a2
......
用中国剩余定理合并可得答案
注意；本题和模板不同的是；要枚举每一个人要的礼物，求 C (剩下的礼物) (当前人的礼物个数) 的积
/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10;
LL a[N], c[N], w[6]; int cnt; //a 数组表示 x (C nm ) % (pi^ki) 的值，c 数组表示 pi^ki，cnt 表示 a c 数组长度
// w 存每个人的礼物个数
LL q_pow(LL a, LL b, LL P) //求 a ^b %P
{
LL ans=1%P; a%=P; //防止 P 为 1，a 先%P
for(; b; b>>=1) //枚举 b 的二进制位
{
if(b&1) ans=ansa%P; //b 这个位为 1，ans 就乘这个位的 a
a=aa%P; // a=a^2
}
return ans;
}
void exgcd(LL a, LL b, LL &d, LL &x, LL &y) //扩展欧几里得
{
if(b==0) {d=a; x=1; y=0;}
else
{
exgcd(b, a%b, d, y, x);
y-=(a/b)x;
}
//详细解释可以在exLucas模板标程里看，这里不多赘述
}
// exgcd 和 q_pow 都为很重要的板子，请熟背
LL inv(LL a, LL P) //逆元 (运用 exgcd)
{
LL A=a, B=P, K=1, d, x, y; // ax=1 (%P) = ax+P?=1 = Ax+By=K
exgcd(A, B, d, x, y); //算的是 Ax+By=d (d为 gcd(a, b))
x=x(K/d); LL dx=abs(B/d); x=(x%dx+dx)%dx; //把 x变成最小正整数解
// x*(K/d)变成 Ax+By=K 的解，dx等于当前 x 与下一组解 x 的差 (下一组解x+abs(B/d)，y-abs(A/d))
// x=(x%dx+dx)%dx 是常用的把 x变成最小正整数解的方式，如果还不懂可以手模一下
return x;
}
LL fac(LL n, LL P, LL Pk) // 算 n! 不含 P 的部分 (例如 P=3，则 fac(9)=12(1)45*(2)78*(1))
{
LL ans=1; if(n0) return 1; //ans初始化为 1，n=0 值为 1
for(LL i=1; i<Pk; i++) if(i%P!=0) ans=(ansi)%Pk; //ans等于 1 ~ Pk 里不含 P 的数的积
ans=q_pow(ans, n/Pk, Pk); // ans^(n/Pk) % Pk， ans等于 1 ~ n/PkPk 里不含 P 的数的积
for(LL i=1; i<=n%Pk; i++) if(i%P!=0) ans=(ansi)%Pk; //ans等于 1 ~ n 里不含 P 的数的积
return ansfac(n/P, P, Pk)%Pk; //继续递归，因为有些数 = x* P^i，x 也要算进来
}
LL C(LL n, LL m, LL P, LL Pk) // C n m
{
if(n<m) return 0; // n<m 值为 0
LL f1=fac(n, P, Pk), f2=fac(m, P, Pk), f3=fac(n-m, P, Pk), sum=0;
// f1表示 n!中不含 P的部分， f2表示 m!中不含 P的部分，f3表示 (n-m)!中不含 P的部分，
for(LL i=n; i; i/=P) sum+=i/P; //sum加上 n 里面有多少个 P
for(LL i=m; i; i/=P) sum-=i/P; //sum减去 m 里面有多少个 P
for(LL i=n-m; i; i/=P) sum-=i/P; //sum减去 (n-m) 里面有多少个 P
return f1inv(f2, Pk)%Pkinv(f3, Pk)%Pkq_pow(P, sum, Pk)%Pk;
// f1乘上 f2的逆元 (%Pk) 乘上 f3的逆元 (%Pk) 再乘上 P^sum (%Pk) 就是 C n m
}
LL CRT() //中国剩余定理
{
LL m=1, ans=0; // m 表示所有 (pi^ki) 的最小公倍数 (就是 P)，ans初始化为 0
for(int i=1; i<=cnt; i++) m=c[i];
for(int i=1; i<=cnt; i++)
{
ans=(ans+a[i](m/c[i])%minv(m/c[i], c[i])%m)%m;
// (m/c[i]) 是除 c[i] 其它所有 (pi^ki) 的公倍数，加上对其它 c的取模结果不影响
// inv(m/c[i], c[i]) 是 (m/c[i]) 的逆元 (%c[i])，乘以 (m/c[i]) %c[i] 等于 1
// 再乘以 a[i] 就达成了不改变其它 c的取模结果，让 %c[i] 的结果等于 a[i]
// %m 防止溢出，加减 m 对所有 c的取模结果没影响 (因为是公倍数)
}
return ans;
}
LL exLucas(LL n, LL m, LL P) //拓展卢卡斯
{
cnt=0; //cnt 初始化
for(int i=2; i*i<=P; i++) if(P%i0) //找出组成 P 的质数
{
LL tmp=1;  while(P%i==0) {tmp*=i; P/=i;} //把 P中的 i提取到 tmp里
cnt++;  a[cnt]=C(n, m, i, tmp); c[cnt]=tmp; //存到 a c 数组里
}
if(P>1) {cnt++; a[cnt]=C(n, m, P, P); c[cnt]=P;} //当 P 还剩有质数时
return CRT();
}
LL solve(LL n, LL m, LL P)
{
LL sum=0, ans=1; // sum记录当前礼物总和，ans初始化为 1
for(int i=1; i<=m; i++)
{
ans=(ans*exLucas(n-sum, w[i], P))%P; //从剩下的礼物中选出当前人要的礼物
sum+=w[i]; //sum加上 w[i]，这里注意先后顺序
}
return ans;
}
int main()
{
LL P, n, m, sum=0; scanf("%lld%lld%lld", &P, &n, &m); //注意读入顺序
for(int i=1; i<=m; i++) scanf("%lld", &w[i]), sum+=w[i]; //所有人要的礼物总和
if(n<sum) printf("Impossible\n"); //供不应求，不可能有答案
else printf("%lld\n", solve(n, m, P));
return 0;
}

by scy:</p>

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=110;
LL cnt,a[N],p[N],pk[N];
void exgcd(LL a,LL b,LL &d,LL &x,LL &y)
{
	if(b==0){d=a;x=1;y=0;}
	else
	{
		exgcd(b,a%b,d,y,x);
		y-=(a/b)*x;
	}
}
LL qpow(LL a,LL b,LL P)
{
	LL ans=1%P;a%=P;
	for(;b;b>>=1)
	{
		if(b&1)ans=ans*a%P;
		a=a*a%P;
	}
	return ans;
}
LL inv(LL a,LL P)
{
	LL A=a,B=P,x,y,d;exgcd(A,B,d,x,y);
	LL dx=abs(B/d);
	x=(x%dx+dx)%dx;
	return x;
}
LL fac(LL n,LL p,LL pk)
{
	if(n==0) return 1;
	LL ans=1;for(LL i=1;i<pk;i++)if(i%p!=0) ans=ans*i%pk;
	ans=qpow(ans,n/pk,pk);
	for(int i=1;i<=n%pk;i++)if(i%p!=0) ans=ans*i%pk;
	return ans*fac(n/p,p,pk) %pk;
}
LL C(LL n,LL m,LL p,LL pk)
{
	if(n<m) return 0;
	LL f1=fac(n,p,pk),f2=fac(m,p,pk),f3=fac(n-m,p,pk);
	LL xyz=0;
	for(LL i=n;i;i/=p)xyz+=i/p;
	for(LL i=m;i;i/=p)xyz-=i/p;
	for(LL i=n-m;i;i/=p)xyz-=i/p;
	return f1*inv(f2,pk)%pk*inv(f3,pk)%pk * qpow(p,xyz,pk) %pk;
}
LL exlucas(LL n,LL m,LL P)
{
	cnt=0;LL tp=P;
	for(LL i=2;i*i<=tp;i++) if(tp%i==0)
	{
		cnt++;p[cnt]=i;pk[cnt]=1;while(tp%i==0)tp/=i,pk[cnt]*=i;
	}
	if(tp>1){cnt++;p[cnt]=pk[cnt]=tp;};
	
	for(int i=1;i<=cnt;i++) a[i]=C(n,m,p[i],pk[i]);
	
	LL x=0;
	for(int i=1;i<=cnt;i++)
	{
		x=( x+ a[i] *  (P/pk[i]) % P * inv(P/pk[i], pk[i]) % P )%P;
	}
	return x;
}
LL w[N];
int main()
{
	LL n,m,p;scanf("%lld%lld%lld",&p,&n,&m);
	LL sum=0;
	for(int i=1;i<=m;i++)
	{
		scanf("%lld",&w[i]);
		sum+=w[i];
	}
	if(sum>n){printf("Impossible\n");return 0;}
	LL ans=1;
	for(int i=1;i<=m;i++)
	{
		ans=(ans* exlucas(n,w[i],p))%p;
		n-=w[i];
	}
	printf("%lld\n",ans);
	return 0;
}

Source

省选/NOI−