「bzoj2142」礼物 - 扩展Lucas定理 | Bill Yang's Blog

「bzoj2142」礼物 - 扩展Lucas定理

题目大意

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


题目分析

好好的一道水题,$P$竟然变成了任意变量。

答案为$C_n^{a_1}C_{n-a_1}^{a_2}\cdots C_{n-\sum_{j=1}^{i-1}a_j}^{a_i}$。
然后直接上扩展Lucas定理即可。


代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
void Exgcd(LL a,LL b,LL &gcd,LL &x,LL &y) {
if(!b)gcd=a,x=1,y=0;
else Exgcd(b,a%b,gcd,y,x),y-=x*(a/b);
}
LL inv(LL a,LL mod) {
LL gcd,x,y;
Exgcd(a,mod,gcd,x,y);
return (x+mod)%mod;
}
LL Quick_Pow(LL a,LL b,LL mod) {
LL ans=1;
for(; b; b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;
return ans;
}
LL Fac(LL n,LL p,LL num) {
if(n==0)return 1;
LL sum=1;
for(LL i=2; i<=num; i++)if(i%p)sum=sum*i%num;
sum=Quick_Pow(sum,n/num,num);
for(int i=2; i<=n%num; i++)if(i%p)sum=sum*i%num;
return sum*Fac(n/p,p,num)%num;
}
LL Cal(LL n,LL p) {
LL sum=0;
for(LL i=n; i; i/=p)sum+=i/p;
return sum;
}
LL C(LL n,LL m,LL p,LL num) {
if(n<m)return 0;
LL x=Fac(n,p,num),y=Fac(m,p,num),z=Fac(n-m,p,num);
LL sum=Cal(n,p)-Cal(m,p)-Cal(n-m,p);
return x*inv(y,num)%num*inv(z,num)%num*Quick_Pow(p,sum,num)%num;
}
LL ExLucas(LL n,LL m,LL mod) {
LL x=mod,ans=0;
for(LL i=2; i<=sqrt(mod); i++)
if(x%i==0) {
LL num=1;
while(x%i==0)x/=i,num*=i;
LL Mi=mod/num;
ans=(ans+Mi*inv(Mi,num)%mod*C(n,m,i,num)%mod)%mod;
}
if(x>1)ans=(ans+mod/x*inv(mod/x,x)%mod*C(n,m,x,x)%mod)%mod;
return ans;
}
LL n,m,mod,ans=1;
int main() {
mod=Get_Int();
n=Get_Int();
m=Get_Int();
for(int i=1; i<=m; i++) {
LL x=Get_Int();
ans=ans*ExLucas(n,x,mod)%mod;
n-=x;
}
if(n<0)puts("Impossible");
else printf("%lld\n",ans);
return 0;
}
本篇文章有用吗?有用还不快点击!
0%