題目鏈接：http://www.lydsy.com/JudgeOnline/problem.php?id=3434

題意：

思路：

const int mod=10007; const int N=100005;int g[22][N]; int C[N][22],mou[N]; int h[22][N][13];int prime[N],cnt; int tag[N];void init() {int i,j;mou[1]=1;for(i=2;i<N;i++){if(!tag[i]){prime[cnt++]=i;mou[i]=-1;}for(j=0;j<cnt;j++){if(i*prime[j]>=N) break;tag[i*prime[j]]=1;if(i%prime[j]==0){mou[i*prime[j]]=0;break;}else mou[i*prime[j]]=-mou[i];}}C[0][0]=1;for(i=1;i<N;i++){C[i][0]=1;for(j=1;j<=i&&j<=20;j++){C[i][j]=C[i-1][j-1]+C[i-1][j];if(C[i][j]>=mod) C[i][j]-=mod;}}int c;for(c=2;c<=20;c++){for(i=1;i<N;i++) for(j=i;j<N;j+=i){g[c][j]+=C[i-1][c-2]*mou[j/i];if(g[c][j]>=mod) g[c][j]-=mod;if(g[c][j]<0) g[c][j]+=mod;}}for(c=2;c<=20;c++){for(i=1;i<N;i++){int pre=1;int x=i;if(x>=mod) x%=mod;for(j=0;j<=11;j++){h[c][i][j]=pre*g[c][i]%mod;h[c][i][j]+=h[c][i-1][j];if(h[c][i][j]>=mod) h[c][i][j]-=mod;pre=pre*x%mod;}}} }int n,cc,M[13];struct node {int a[15];int Max;void clear(){clr(a,0);Max=0;}void mul(int x1,int x0){int i;int b[15];for(i=0;i<=Max;i++) b[i]=a[i]*x0%mod;b[Max+1]=0;for(i=0;i<=Max;i++){b[i+1]=b[i+1]+a[i]*x1%mod;if(b[i+1]>=mod) b[i+1]-=mod;}for(i=0;i<=n;i++) a[i]=b[i];Max++;}}A;int cal(int d1,int d2) {A.clear();A.a[0]=1;int i;for(i=1;i<=n;i++){i64 tmp=M[i]/d1;int aa=-(i64)(tmp+1)*tmp/2%mod;int bb=M[i]%mod*tmp%mod;A.mul(aa,bb);}int ans=0;for(i=n;i>=0;i--){ans+=A.a[i]*(h[cc][d2][i]-h[cc][d1-1][i])%mod;if(ans<0) ans+=mod;if(ans>=mod) ans-=mod;}return ans; }int main() {init();int T=getInt();while(T--){n=getInt();cc=getInt();int i;for(i=1;i<=n;i++) M[i]=getInt();sort(M+1,M+n+1);int ans=0;for(i=1;i<=M[1];){int L=i;int R=M[1];int j;for(j=1;j<=n;j++){R=min(R,M[j]/(M[j]/i));}ans+=cal(L,R);if(ans>=mod) ans-=mod;if(ans<0) ans+=mod;i=R+1;}printf("%d\n",ans);} }

?

總結

以上是生活随笔為你收集整理的BZOJ 3434 时空穿梭的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。