题目大意：给定一个方程$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的部分依然使用容斥的方法处理，类似于CF451E，状压+容斥
接下来就是拓展Lucas了，讲解传送门
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 10
#define ll long long
using namespace std; ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b) {x=,y=;return a;}
ll g=exgcd(b,a%b,x,y);
ll t=x;x=y,y=t-a/b*y;
return g;
}
ll qmul(ll x,ll y,const ll &mo){
ll ans=;
while(y){
if(y&) ans=(ans+x)%mo;
x=(x+x)%mo,y>>=;
}return ans;
}
ll qpow(ll x,ll y,const ll &mo){
ll ans=;
while(y){
if(y&) ans=ans*x%mo;
x=x*x%mo,y>>=;
}return ans;
}
ll son1[]={};
ll son2[]={,,,,};
ll son3[]={,,}; namespace exlucas{
ll ans=,M=;
ll son[],pw[];
int num;
void Pre(ll p)
{
if(p==){
num=,son[]=son1[],pw[]=son1[];
}else if(p==){
num=;
for(int i=;i<num;i++)
son[i]=son2[i],pw[i]=son[i];
}else{
num=;
for(int i=;i<num;i++)
son[i]=son3[i];
pw[]=,pw[]=,pw[]=;
}
}
int excrt_ins(ll A,ll B)
{
ll a=A,b=B,c=(a-ans%b+b)%b,x,y;
ll g=exgcd(M,b,x,y);ll bg=b/g;
if(c%g!=) return -;
//x=x*(c/g)%bg;
x=qmul(x,c/g,bg);
ans+=x*M,M*=bg,ans=(ans%M+M)%M;
return ;
}
ll get_mul(ll n,ll p,ll &sum,const ll &mo,int type)
{
if(n==) return ;
ll ans=;
for(int i=;i<=min(n,mo);i++)
if(i%p) ans=ans*i%mo;
ans=qpow(ans,n/mo,mo);
for(int i=;i<=n%mo;i++)
if(i%p) ans=ans*i%mo;
sum+=1ll*(n/p)*type;
return ans*get_mul(n/p,p,sum,mo,type)%mo;
}
ll get_C(ll n,ll m,ll p,const ll &mo)
{
if(m>n) return ;
ll sum=;ll y;
ll nn=get_mul(n,p,sum,mo,);
ll mm=get_mul(m,p,sum,mo,-);
ll nm=get_mul(n-m,p,sum,mo,-);
exgcd(mm,mo,mm,y);
mm=(mm%mo+mo)%mo;
exgcd(nm,mo,nm,y);
nm=(nm%mo+mo)%mo;
return nn*mm%mo*nm%mo*qpow(p,sum,mo)%mo;
}
ll C(ll n,ll m,const ll &mo)
{
if(m>n) return ;
ll ret=;
for(int i=;i<num;i++){
ll val=get_C(n,m,son[i],pw[i]);
excrt_ins(val,pw[i]);
}
ret=ans,M=,ans=;
return ret;
}
}; int T;ll p;
ll n,m,n1,n2;
ll a[N],b[N]; int main()
{
// freopen("t1.in","r",stdin);
scanf("%d%lld",&T,&p);
exlucas::Pre(p);
while(T--)
{
scanf("%lld%lld%lld%lld",&n,&n1,&n2,&m);
memset(a,,sizeof(a));memset(b,,sizeof(b));
for(int i=;i<n1;i++) scanf("%lld",&a[i]);
for(int i=;i<=n2;i++) scanf("%lld",&b[i]),m-=(b[i]-);
if(m<) printf("0\n");
int tot=(<<n1);ll ans=;
for(int s=;s<tot;s++)
{
ll res=m;int cnt=;
for(int i=;i<n1;i++) if(s&(<<i)) res-=a[i],cnt++;
if(res<=) {continue;}
ll w=(cnt&?-1ll:1ll)*exlucas::C(res-,n-,p);
(ans+=w)%=p;
}
printf("%lld\n",(ans%p+p)%p);
}
return ;
}