2142: 禮物

Description

一年一度的圣誕節快要來到了。每年的圣誕節小E都會收到許多禮物，當然他也會送出許多禮物。不同的人物在小E 心目中的重要性不同，在小E心中分量越重的人，收到的禮物會越多。小E從商店中購買了n件禮物，打算送給m個人 ，其中送給第i個人禮物數量為wi。請你幫忙計算出送禮物的方案數（兩個方案被認為是不同的，當且僅當存在某 個人在這兩種方案中收到的禮物不同）。由于方案數可能會很大，你只需要輸出模P后的結果。

Input

輸入的第一行包含一個正整數P，表示模； 第二行包含兩個整整數n和m，分別表示小E從商店購買的禮物數和接受禮物的人數； 以下m行每行僅包含一個正整數wi，表示小E要送給第i個人的禮物數量。

Output

若不存在可行方案，則輸出“Impossible”，否則輸出一個整數，表示模P后的方案數。

Sample Input

100
4 2
1
2

Sample Output

12
【樣例說明】
下面是對樣例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=p1^c1 * p2^c2 * p3^c3 * … *pt ^ ct，pi為質數。
對于100%的數據，1≤n≤109，1≤m≤5，1≤pi^ci≤10^5。
sol：這道題不就是一個ExLucas板子嗎，然后碼+調了一年 Ps：我太菜了 #include <bits/stdc++.h> using namespace std; typedef long long ll; inline ll read() {ll s=0;bool f=0;char ch=' ';while(!isdigit(ch)){f|=(ch=='-'); ch=getchar();}while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48); ch=getchar();}return (f)?(-s):(s); } #define R(x) x=read() inline void write(ll x) {if(x<0){putchar('-'); x=-x;}if(x<10){putchar(x+'0'); return;}write(x/10);putchar((x%10)+'0');return; } #define W(x) write(x),putchar(' ') #define Wl(x) write(x),putchar('\n') ll n,m,Sum; ll Num[10]; ll cnt=0,Mo[65],Yu[65]; ll prim[65],T[65];inline ll Ksm(ll x,ll y,ll Pk); inline ll C(ll n,ll m,ll P,ll Pk); inline ll Solve(); inline void Exgcd(ll a,ll b,ll &X,ll &Y); inline ll Jiecheng(ll n,ll P,ll Pk); inline ll Exlucas(ll n,ll m,ll Mod); inline ll Inv(ll Num,ll Mod);inline ll Ksm(ll x,ll y,ll Pk) {ll Ans=1;while(y){if(y&1) Ans=Ans*x%Pk;x=x*x%Pk;y>>=1;}return Ans; } inline void Exgcd(ll a,ll b,ll &X,ll &Y) {if(b==0){X=1;Y=0;return;}Exgcd(b,a%b,X,Y);ll XX=X,YY=Y;X=YY;Y=XX-a/b*YY;return; } inline ll Inv(ll Num,ll Mod) //Num*Inv = 1 (%Mod) {ll a=Num,b=Mod,c=1,X,Y;Exgcd(a,b,X=0,Y=0);return (X%b+b)%b; } inline ll Jiecheng(ll n,ll P,ll Pk) {if(!n) return 1;ll i,Ans=1;for(i=2;i<=Pk;i++) if(i%P) Ans=Ans*i%Pk;Ans=Ksm(Ans,n/Pk,Pk);for(i=2;i<=n%Pk;i++) if(i%P) Ans=Ans*i%Pk;return Ans*Jiecheng(n/P,P,Pk)%Pk; } inline ll C(ll n,ll m,ll P,ll Pk) {ll Jn=Jiecheng(n,P,Pk);ll Jm=Jiecheng(m,P,Pk);ll Jnm=Jiecheng(n-m,P,Pk);ll i,oo=0;for(i=n;i;i/=P) oo+=i/P;for(i=m;i;i/=P) oo-=i/P;for(i=n-m;i;i/=P) oo-=i/P;return Jn*Inv(Jm,Pk)%Pk*Inv(Jnm,Pk)%Pk*Ksm(P,oo,Pk)%Pk; } inline ll Exlucas(ll n,ll m,ll Mod) {ll i,tmp=Mod;cnt=0;for(i=2;i<=sqrt(tmp);i++) if(tmp%i==0){ll Num=1;while(tmp%i==0){Num*=i;tmp/=i;}Mo[++cnt]=Num;Yu[cnt]=C(n,m,i,Num)%Num;}if(tmp>1){Mo[++cnt]=tmp;Yu[cnt]=C(n,m,tmp,tmp)%tmp;}return Solve(); } inline ll Solve() {memmove(prim,Mo,sizeof Mo);memmove(T,Yu,sizeof T);int i;ll Lcm=prim[1];for(i=2;i<=cnt;i++){ll a=prim[i-1],b=prim[i],c=T[i]-T[i-1],r=1,X,Y;Exgcd(a,b,X=0,Y=0);ll tmp=b/r;X=(X*c%tmp+tmp)%tmp;prim[i]=Lcm=Lcm*prim[i];T[i]=(X*prim[i-1]+T[i-1])%Lcm;}return T[cnt]; } int main() {ll Mod,i,Sum=0,ans=1;R(Mod);R(n); R(m);for(i=1;i<=m;i++) Sum+=(Num[i]=read());if(Sum>n) return 0*puts("Impossible");for(i=1;i<=m;i++){ans=ans*Exlucas(n,Num[i],Mod)%Mod;n-=Num[i];}Wl(ans);return 0; } /* input 286572286 843547440 1 262584859 output 44088044input 100 4 2 1 2 output 12 */ View Code

?

轉載于:https://www.cnblogs.com/gaojunonly1/p/10560804.html

總結

以上是生活随笔為你收集整理的一本通1659礼物的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。