题目大意：给出n和a[1]到a[m]，求∑C(a[i],n-∑a[j](j<i))对非质数P取余的结果。
其实本题难点在于组合数对非质数取余。
先了解一下普通lucas：
（本人认为仅次于gcd的第二好写的数论板子）
lucas定理常用于组合数对质数取余，定理为：
C(n,m) ≡ C(n/p,m/p) * C(n%p,m%p) ( mod p )
理性理解一下就好。
（所以我第一次用lucas+CRT拿了75）
接下来进入正题，什么是拓展lucas?
拓展lucas的精髓在于递归地求解 n! % p^k (p是质数) 和中国剩余定理 。（说实话和普通lucas没有一点关系）
1.求解阶乘对质数整数次幂去模：
先举个例子：
n=22 , p = 3 , k = 2 , pk = p^k = 9
则:
n! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19 * 20 * 21 * 22
其中黑的是p的倍数。
把黑的拉出来，是：3^7 * ( 1 * 2 * 3 * 4 * 5 * 6 * 7 );
其中括号里的是阶乘形式，递归向下做;
然后发现：
1 * 2 * 4 * 5 * 7 * 8 和 10 * 11 * 13 * 14 * 16 * 17 是同余的（mod pk）。
所以可以只算一组（从2到pk），然后快速幂n/pk次。
最后还剩 19 * 20 , 其实只要做 1 * 2就行了，反正同余。
2.CRT的应用：
因为1操作需要pk是p^k形式，所以要把原来的mod分解，然后分组做，可以得到一个线性同余方程组，
然后CRT合并。
代码：
#include#include using namespace std;#define ll long longint P,n,m,a[10];ll ans = 1;ll fast(ll x,int y,ll mod){ ll ret = 1ll; while(y) { if(y&1)ret=ret*x%mod; x=x*x%mod; y>>=1; } return ret;}void exgcd(ll aa,ll b,ll &x,ll &y){ if(!b) { x=1,y=0; return ; } exgcd(b,aa%b,y,x); y-=aa/b*x;}ll inv(ll aa,ll b){ ll x,y; exgcd(aa,b,x,y); x = (x%b+b)%b; return x;}ll stp(ll x,ll p,ll pk)//x! % p^k{ if(!x)return 1; ll ret = 1; for(int i=2;(ll)i<=pk;i++) if(i%p)ret=ret*i%pk; ret = fast(ret,x/pk,pk); for(int i=2;(ll)i<=x%pk;i++) if(i%p)ret=ret*i%pk; return ret*stp(x/p,p,pk)%pk;}ll C(ll x,ll y,ll M,ll p,ll pk){ ll a = stp(y,p,pk),b = stp(x,p,pk),c = stp(y-x,p,pk),k = 0; for(ll i=y;i;i/=p)k+=i/p; for(ll i=x;i;i/=p)k-=i/p; for(ll i=y-x;i;i/=p)k-=i/p; ll ret = a*inv(b,pk)%pk*inv(c,pk)%pk*fast(p,k,pk)%pk; return ret*(M/pk)%M*inv(M/pk,pk)%M;}ll p0[55],md[55],cnt;int main(){ scanf("%d%d%d",&P,&n,&m); int sum = 0; for(int i=1;i<=m;i++) { scanf("%d",&a[i]); sum+=a[i]; } if(sum>n) { printf("Impossible\n"); return 0; } ll M = P; for(int i=2;i*i<=P;i++) { if(P%i==0) { p0[++cnt] = i; md[cnt]=1; while(P%i==0)P/=i,md[cnt]*=i; } } if(P!=1) { p0[++cnt] = P; md[cnt] = P; } ll las = n,ans = 1; for(int i=1;i<=m;i++) { ll now = 0; for(int j=1;j<=cnt;j++) { now = (now+C(a[i],las,M,p0[j],md[j]))%M; } ans = ans*now%M; las-=a[i]; } printf("%lld\n",ans); return 0;}