题目：

10分还要用 Lucas 定理囧...因为模数太小了不能直接算...

#include
      
       #include
       
        #include
        
         using namespace std;typedef long long ll;int rd(){  int ret=0,f=1; char ch=getchar();  while(ch<'0'||ch>'9'){
    if(ch=='-')f=0; ch=getchar();}  while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();  return f?ret:-ret;}int const xn=1e5+5,xm=25,mod=10007;int n,num,m[xm],jc[xn],jcn[xn];ll pw(ll a,int b){ll ret=1; for(;b;b>>=1,a=a*a%mod)if(b&1)ret=ret*a%mod; return ret;}void init(){  jc[0]=1; int mx=mod-1;  for(int i=1;i<=mx;i++)jc[i]=(ll)jc[i-1]*i%mod;  jcn[mx]=pw(jc[mx],mod-2);  for(int i=mx-1;i>=0;i--)jcn[i]=(ll)jcn[i+1]*(i+1)%mod;}int C(int n,int m){
    return (ll)jc[n]*jcn[m]%mod*jcn[n-m]%mod;}int lucas(int n,int m){  if(m==0||n
         
          =mod)x-=mod; while(x<0)x+=mod; return x;}int main(){  int T=rd(); init();  while(T--)    {      n=rd(); num=rd(); bool fl=1;      for(int i=1;i<=n;i++)    {      m[i]=rd();      if(m[i]>30)fl=0;    }      if(n==1)printf("%d\n",lucas(m[1],num));    }  return 0;}
         
        
       
      

参考博客：

开头结尾思路好妙，莫比乌斯反演好套路；

忘记前缀和调了半天hhh。

代码如下：

#include
     
      #include
      
       #include
       
        using namespace std;typedef long long ll;int rd(){  int ret=0,f=1; char ch=getchar();  while(ch<'0'||ch>'9'){
   if(ch=='-')f=0; ch=getchar();}  while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();  return f?ret:-ret;}int Min(int x,int y){
   return x
        
         >=1,a=a*a%mod)if(b&1)ret=ret*a%mod; return ret;}int upt(int x){
   while(x>=mod)x-=mod; while(x<0)x+=mod; return x;}void getpri(){  int mx=1e5; mu[1]=1;  for(int i=2;i<=mx;i++)    {      if(!vis[i])pri[++cnt]=i,mu[i]=-1;      for(int j=1;j<=cnt&&(ll)i*pri[j]<=mx;j++)    {      vis[i*pri[j]]=1;      if(i%pri[j])mu[i*pri[j]]=-mu[i];      else break;    }    }}void init(){  int mx=1e5;  for(int i=0;i<=mx;i++)C[i][0]=1;  for(int i=1;i<=mx;i++)    for(int j=1;j<=20;j++)      C[i][j]=upt(C[i-1][j]+C[i-1][j-1]);  for(int c=2;c<=20;c++)    {      for(int g=1;g<=mx;g++)    for(int T=g;T<=mx;T+=g)      G[c][T]=upt(G[c][T]+C[g-1][c-2]*mu[T/g]);      for(int T=1;T<=mx;T++)      for(int i=0,k=1;i<=11;i++,k=(ll)k*T%mod)        f[c][T][i]=(f[c][T-1][i]+(ll)k*G[c][T])%mod;    }}void get(int t)//(px+q){  int tmp,p,q;  memset(a,0,sizeof a); a[0]=1;//  for(int i=1;i<=n;i++)    {      tmp=m[i]/t;      p=upt(-(ll)tmp*(tmp+1)%mod*inv2%mod);      q=(ll)tmp*m[i]%mod;      for(int j=i;j;j--)    a[j]=upt((ll)a[j-1]*p%mod+(ll)a[j]*q%mod);      a[0]=upt((ll)a[0]*q%mod);    }}int main(){  int T=rd(); getpri(); init(); inv2=pw(2,mod-2);  while(T--)    {      n=rd(); c=rd(); int mn=xm,ans=0;      for(int i=1;i<=n;i++)m[i]=rd(),mn=Min(mn,m[i]);      for(int i=1,nxt;i<=mn;i=nxt+1)    {      nxt=m[1]/(m[1]/i);      for(int j=2;j<=n;j++)nxt=Min(nxt,m[j]/(m[j]/i));      get(i);      for(int j=0;j<=n;j++)ans=upt(ans+(ll)a[j]*(f[c][nxt][j]-f[c][i-1][j])%mod);    }      printf("%d\n",ans);    }  return 0;}