10分还要用 Lucas 定理囧...因为模数太小了不能直接算...
#include<cstdio> #include<cstring> #include<algorithm> 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<m)return 1; return (ll)lucas(n/mod,m/mod)*C(n%mod,m%mod)%mod; } int upt(int x){while(x>=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 ",lucas(m[1],num)); } return 0; }
参考博客：https://www.cnblogs.com/ljh2000-jump/p/6242237.html
开头结尾思路好妙，莫比乌斯反演好套路；
忘记前缀和调了半天hhh。
代码如下：
#include<cstdio> #include<cstring> #include<algorithm> 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<y?x:y;} int const xn=15,xm=1e5+5,xc=25,mod=10007; int n,c,m[xn],a[xn],C[xm][xc],G[xc][xm],f[xc][xm][xn],mu[xm],cnt,pri[xm],inv2; bool vis[xm]; 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;} 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 ",ans); } return 0; }