当前位置：首页 > news >正文

BZOJ2142 礼物

news 2025/9/6 22:52:59

题目描述

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

输入格式

输入的第一行包含一个正整数P，表示模；第二行包含两个整整数n和m，分别表示小E从商店购买的礼物数和接受礼物的人数；以下m行每行仅包含一个正整数wi，表示小E要送给第i个人的礼物数量。

输出格式

若不存在可行方案，则输出“Impossible”，否则输出一个整数，表示模P后的方案数。

输入样例

输出样例

样例解释

下面是对样例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

数据范围

设 $P=p1c1×p2c2⋯×ptctP=p_1^{c_1}\times p_2^{c_2}\dots\times p_t^{c_t}$ ， $p_i$ 为质数。

对于 $100%100\%$ 的数据， $1≤n≤109，1≤m≤5,1≤pici≤1051\leq n\leq 10^9，1\leq m\leq 5,1\leq p_i^{c_i}\leq 10^5$ 。

题解

前置知识：扩展lucas定理

题意即求 $Cna1×Cn−a1a2×⋯×Cn−a1−a2−⋯−am−1amC_n^{a_1}\times C_{n-a_1}^{a_2}\times \cdots \times C_{n-a_1-a_2-\dots -a_{m-1}}^{a_m}$ 。

根据 $Cnm=n!m!(n−m)!C_n^m=\dfrac{n!}{m!(n-m)!}$ ，我们整理可以发现，上述式子等于

$n!a1!×a2!×⋯×am!×(n−a1−a2−⋯−am)!\dfrac{n!}{a_1!\times a_2!\times \cdots\times a_m!\times (n-a_1-a_2-\dots-a_m)!}$

我们呢可以用扩展lucas定理。因为 $1≤m≤51\leq m\leq 5$ ，所以并不需要求太多次阶乘的逆元，与普通的扩展lucas定理的时间复杂度差不了多少。

code

#include<bits/stdc++.h>
using namespace std;
int tot=0;
long long n,m,x,y,sum,ans,w[10],r[105],a[105];
long long mod;
long long mi(long long t,long long v){if(v==0) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
void exgcd(long long c,long long d){if(d==0){x=1;y=0;return;}exgcd(d,c%d);long long t=x;x=y;y=t-c/d*y;
}
long long gt(long long v,long long p,long long q){if(!v) return 1;long long re=1;for(int i=1;i<=q;i++){if(i%p) re=re*i%q;}re=mi(re,v/q)%q;for(int i=1;i<=v%q;i++){if(i%p) re=re*i%q;}return re*gt(v/p,p,q)%q;
}
long long C(long long p,long long q){if(n<m) return 0;long long f[10],f1=gt(n,p,q),f2=gt(sum,p,q),vt=0,re;for(int i=1;i<=m;i++) f[i]=gt(w[i],p,q);for(long long i=p;i<=n;i*=p) vt+=n/i;for(long long i=p;i<=sum;i*=p) vt-=sum/i;for(int j=1;j<=m;j++){for(long long i=p;i<=w[j];i*=p) vt-=w[j]/i;}re=mi(p,vt)%q*f1%q*(mi(f2,q-q/p-1)%q)%q;for(int i=1;i<=m;i++){re=re*(mi(f[i],q-q/p-1)%q)%q;}return re;
}
int main()
{long long v;scanf("%lld%lld%lld",&mod,&n,&m);sum=n;for(int i=1;i<=m;i++){scanf("%d",&w[i]);sum-=w[i];}if(sum<0){printf("Impossible");return 0;}v=mod;for(long long i=2;i*i<=v;i++){if(v%i==0){r[++tot]=1;while(v%i==0){r[tot]*=i;v/=i;}a[tot]=C(i,r[tot]);}}if(v>1){r[++tot]=v;a[tot]=C(v,v);}v=mod;for(int i=1;i<=tot;i++){exgcd(v/r[i],r[i]);x=(x%r[i]+r[i])%r[i];ans=(ans+v/r[i]*a[i]*x%v)%v;}printf("%lld",ans);return 0;
}