题目大意：给定一个方程$X_{1}+X_{2}+X_{3}+X_{4}+...+X_{n}=M$，$\forall X_{i}<=A_{i} (i<=n1)$ $\forall X_{i}>=A_{i} (n1<i<=n2)$在保证的合法正整数解个数n1<=8,n2<=8

一波三折的数学题，调了半天才发现我的Lucas是错的，但它竟然通过了洛谷那一道模板题的全部数据....

后面n1~n2的部分很好处理，直接用M减掉这个部分就行了

因为是求正整数解，所以这个组合数的形式可以用隔板法处理，即每两个物品之间设为一个空位，现在要分成n个部分，则把n-1个隔板放进空位

即$C_{m-1}^{k-1}$

前面1~n1的部分依然使用容斥的方法处理，类似于，状压+容斥

接下来就是拓展Lucas了，

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #define N 10  7 #define ll long long  8 using namespace std;  9  10 ll exgcd(ll a,ll b,ll &x,ll &y){ 11     if(!b) {x=1,y=0;return a;} 12     ll g=exgcd(b,a%b,x,y); 13     ll t=x;x=y,y=t-a/b*y; 14     return g; 15 } 16 ll qmul(ll x,ll y,const ll &mo){ 17     ll ans=0; 18     while(y){ 19         if(y&1) ans=(ans+x)%mo; 20         x=(x+x)%mo,y>>=1; 21     }return ans; 22 } 23 ll qpow(ll x,ll y,const ll &mo){ 24     ll ans=1; 25     while(y){ 26         if(y&1) ans=ans*x%mo; 27         x=x*x%mo,y>>=1; 28     }return ans; 29 } 30 ll son1[]={
   10007}; 31 ll son2[]={
   2,3,11,397,10007}; 32 ll son3[]={
   5,7,101}; 33  34 namespace exlucas{ 35 ll ans=0,M=1; 36 ll son[10],pw[10]; 37 int num; 38 void Pre(ll p) 39 { 40     if(p==10007){ 41         num=1,son[0]=son1[0],pw[0]=son1[0]; 42     }else if(p==262203414){ 43         num=5; 44         for(int i=0;i
          
           n) return 0; 78 ll sum=0;ll y; 79 ll nn=get_mul(n,p,sum,mo,1); 80 ll mm=get_mul(m,p,sum,mo,-1); 81 ll nm=get_mul(n-m,p,sum,mo,-1); 82 exgcd(mm,mo,mm,y); 83 mm=(mm%mo+mo)%mo; 84 exgcd(nm,mo,nm,y); 85 nm=(nm%mo+mo)%mo; 86 return nn*mm%mo*nm%mo*qpow(p,sum,mo)%mo; 87 } 88 ll C(ll n,ll m,const ll &mo) 89 { 90 if(m>n) return 0; 91 ll ret=0; 92 for(int i=0;i