洛谷 P2183 [国家集训队]礼物）（扩展卢卡斯定理）

[国家集训队]礼物

题目背景

一年一度的圣诞节快要来到了。每年的圣诞节小 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

样例输入 #1

100
4 2
1
2
1
2
3
4

样例输出 #1

12
1

样例 #2

样例输入 #2

100
2 2
1
2
1
2
3
4

样例输出 #2

Impossible
1

提示

样例 1 解释

以 / 分割，/ 前后分别表示送给第一个人和第二个人的礼物编号。$12$ 种方案详情如下：

1/23 1/24 1/34
2/13 2/14 2/34
3/12 3/14 3/24
4/12 4/13 4/23
1
2
3
4

数据规模与约定

设 $P={\prod }_{i=1}^t{p}_i^{c_i}$，$p_i$ 为质数。

对于 $15\%$ 的数据，$n\le 15$，$m\le 5$，$p_i^{c_i}\le 10^5$。

在剩下的 $85\%$ 数据中，约有 $60\%$ 的数据满足 $t\le 2$，$c_i=1$，$p_i\le 10^5$，约有 $30\%$ 的数据满足 $p_i\le 200$。

对于 $100\%$ 的数据，$1\le n\le 10^9$，$1\le m\le 5$，$1\le p_i^{c_i}\le 10^5$，$1\le w_i\le P\le 10^9$。

1、题目求若干个组合数对 p（不一定是素数）求模
2、有几个组合数，就调用几次 扩展卢卡斯定理 模板
1
2

#include 
using namespace std;
typedef long long ll;
const int MaxN = 1000010;
ll nn, mm, pp;

ll exgcd(ll a, ll b, ll& x, ll& y)
{
	if(0 == b)
	{
		x = 1, y = 0;
		return 0;
	}
	ll d, x1, y1;
	d = exgcd(b, a % b, x1, y1);
	x = y1, y = x1 - a / b * y1;
	return d;
}

//计算 a^b mod p
ll quick_pow(ll a, ll b, ll p)
{
	ll c = 1;
	while(b)
	{
		if(b & 1)
			c = (c * a) % p;
		a = (a * a) % p;
		b >>= 1;
	}
	return c;
}

// 计算逆元 ax = 1(mod p), 算出最小非负整数 x 
ll inverse(ll a, ll p)	// gcd(a, p) = 1, 可以用好 exgcd 计算逆元x
{
	ll x, y;
	exgcd(a, p, x, y);
	return (x % p + p) % p;
}

// 递归 计算 n! mod p^k 的值
ll fac(ll n, ll  p, ll pk)
{
	if(!n)
		return 1;
	ll ans = 1;
	for(ll i = 1; i < pk; ++i)
	{
		if(i % p)
			ans = (ans * i) % pk;
	}
	ans = quick_pow(ans, n / pk, pk); 
	for(ll i = 1; i <= n % pk; ++i)		// 余下一部分，全部算上
	{
		if(i % p)
			ans = (ans * i) % pk;
	}
	return ans * fac(n / p, p, pk) % pk;
}

// 计算 c[m][n]  mod p^k 
ll combi(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 t1 = n, t2 = m, t3 = n - m, cnt = 0;
	for(; t1; t1 /= p)	
		cnt += t1 / p;
	for(; t2; t2 /= p)	
		cnt -= t2 / p;
	for(; t3; t3 /= p)	
		cnt -= t3 / p;
	return ((f1 * inverse(f2, pk) % pk) * inverse(f3, pk) % pk * quick_pow(p, cnt, pk)) % pk;
}


ll r[300], m[300];

ll crt(ll n)
{
	ll M = 1, ans = 0;
	for(ll i = 1; i <= n; ++i)
		M *= m[i];
	for(ll i = 1; i <= n; ++i)
	{
		ll c = M / m[i], x, y;
		exgcd(c, m[i], x, y);
		ans = (ans + r[i] * c * x % M) % M;
	}
	return (ans % M + M) % M;
}

ll exlucas(ll A, ll B, ll pp)
{
	memset(m, 0, sizeof m);
	memset(r, 0, sizeof r);
	ll tmp = pp;
	int cnt = 0;
	m[cnt] = 1;
	for(ll i = 2; i * i <= pp; ++i)
	{
		if(tmp % i == 0)
		{
			m[++cnt] = 1;
			while(tmp % i == 0)
				tmp /= i, m[cnt] *= i;
			r[cnt] = combi(A, B, i, m[cnt]);
		}
	}
	if(tmp > 1)
		m[++cnt] = tmp, r[cnt] = combi(A, B, tmp, m[cnt]);
	return crt(cnt);
}

int main()
{
	ll person[10], sum = 0;
	scanf("%lld%lld%lld", &pp, &nn, &mm);
	for(ll i = 1; i <= mm; ++i)
	{
		scanf("%lld", &person[i]);
		sum += person[i];
	}
	if(nn < sum)	// 不够分
	{
		printf("Impossible\n");
		return 0;
	}

	ll mod = pp;
	ll result = 1;
	for(ll i = 1; i <= mm; ++i)
	{
		result = result * exlucas(nn, person[i], mod) % mod;
		nn -= person[i];
	}
	printf("%lld\n", result);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141