「BZOJ2142」礼物

Description

一年一度的圣诞节快要来到了。每年的圣诞节小E都会收到许多礼物,当然他也会送出许多礼物。不同的人物在小EE
心目中的重要性不同,在小EE心中分量越重的人,收到的礼物会越多。小E从商店中购买了nn件礼物,打算送给mm个人
,其中送给第ii个人礼物数量为wiw_i。请你帮忙计算出送礼物的方案数(两个方案被认为是不同的,当且仅当存在某
个人在这两种方案中收到的礼物不同)。由于方案数可能会很大,你只需要输出模PP后的结果。

Input

输入的第一行包含一个正整数PP,表示模;
第二行包含两个整整数nnmm,分别表示小E从商店购买的礼物数和接受礼物的人数;
以下mm行每行仅包含一个正整数wiw_i,表示小E要送给第ii个人的礼物数量。

Output

若不存在可行方案,则输出Impossible,否则输出一个整数,表示模PP后的方案数。

Sample Input

1
2
3
4
100
4 2
1
2

Sample Output

1
12

HINT

P=p1c1×p2c2×p3c3××ptctP=p_1^{c_1} \times p_2^{c_2} \times p_3^{c_3} \times \cdots \times p_t ^ {c_t}pip_i为质数。
对于100%100\%的数据,1n1091\leq n\leq 10^91m51\leq m\leq 51pici1051\leq p_i^{c_i}\leq 10^5

Solution

Exlucas模板题。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 66;
ll b[N], a[N], d[N];
int tot;
ll ksm(ll x, ll y, ll p) {
ll res = 1;
for(; y; y >>= 1, x = x * x % p)
if(y & 1) res = res * x % p;
return res;
}
//ll C(ll n, ll m) {
// for(int i = 1; i <= tot; ++i)
// a[i] = ksm(b[i], n / b[i] - m / b[i] - (n - m) / b[i], d[i]);
//}
ll fac(ll n, ll p, int pk) {
if(!n) return 1;
ll res = 1;
for(int i = 1; i < pk; ++i)
if(i % p) res = res * i % pk;
res = ksm(res, n / pk, pk);
int t = n %pk;
for(int i = 1; i <= t; ++i) if(i % p)
res = res * i % pk;
//return res * fac(n / pk, p, pk) % pk;
return res * fac(n / p, p, pk) % pk;
}
ll exgcd(ll a, ll &x, ll b, ll &y) {
if(b) {
ll d = exgcd(b, y, a % b, x);
y -= a / b * x;
return d;
} else {
x = 1;
y = 0;
return a;
}
}
ll inv(ll v, ll p) {
ll x, y;
exgcd(v, x, p, y);
x %= p;
if(x < 0) x += p;
return x;
}
ll C(ll n, ll m, ll p, ll pk) {
if(m > n) return 0;
ll f1 = fac(n, p, pk);
ll f2 = fac(m, p, pk);
ll f3 = fac(n - m, p, pk);
ll cnt = 0;
for(ll i = p;; i = i * p) {
cnt += n / i;
if(n / i < p) break;
}
for(ll i = p;; i = i * p) {
cnt -= m / i;
if(m / i < p) break;
}
for(ll i = p;; i = i * p) {
cnt -= (n - m) / i;
if((n - m) / i < p) break;
}
//return f1 * ksm(f2, pk - 2, pk) % pk * ksm(f3, pk - 2, pk) % pk * ksm(p, cnt, pk) % pk;
return f1 * inv(f2, pk) % pk * inv(f3, pk) % pk * ksm(p, cnt, pk) % pk;
}
ll crt() {
ll M = 1, x, y, ans = 0;
for(int i = 1; i <= tot; ++i) M = M * b[i];
for(int i = 1; i <= tot; ++i) {
exgcd(M / b[i],x, b[i], y);
x %= b[i];
if(x < 0) x += b[i];
ans = (ans + M / b[i] * x % M * a[i] % M) % M;
}
return ans;
}
int main() {
ll p = read();
ll tmp = p;
for(ll i = 2; i <= p / i; ++i) if(p % i == 0) {
d[++tot] = i;
b[tot] = 1;
while(p % i == 0) p/=i, b[tot] *= i;
}
if(p > 1) b[++tot] = p, d[tot] = p;
p = tmp;
ll n = read(), m = read();
ll s = 0, ans = 1;
for(int i = 1; i <= m; ++i) {
ll w = read();
if(s + w > n) {
puts("Impossible");
return 0;
}
for(int j = 1; j <= tot; ++j)
a[j] = C(n - s, w, d[j], b[j]);
s += w;
ans = ans * crt() % p;
}
writeln(ans);
return 0;
}