題目描述

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

輸入格式

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

輸出格式

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

輸入樣例

100
4 2
1
2

輸出樣例

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

數(shù)據(jù)范圍

設(shè)$P=p_1^{c_1}\times p_2^{c_2}?\times p_t^{c_t}$，$p_i$為質(zhì)數(shù)。

對于$100\%$的數(shù)據(jù)，$1\le n\le 10^9，1\le m\le 5,1\le p_i^{c_i}\le 10^5$。

題解

前置知識：擴(kuò)展lucas定理

題意即求$C_n^{a_1}\times C_{n?a_1}^{a_2}\times ?\times C_{n?a_1?a_2???a_{m?1}}^{a_m}$。

根據(jù)$C_n^m=\frac{n!}{m!(n?m)!}$，我們整理可以發(fā)現(xiàn)，上述式子等于

$$\frac{n!}{a_1!\times a_2!\times ?\times a_m!\times (n?a_1?a_2???a_m)!}$$

我們呢可以用擴(kuò)展lucas定理。因為$1\le m\le 5$，所以并不需要求太多次階乘的逆元，與普通的擴(kuò)展lucas定理的時間復(fù)雜度差不了多少。

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;
}