注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

WC 2014 space 题解  

2014-02-16 16:06:37|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://pan.baidu.com/s/1gdonfRd

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define mod 10007
#define maxn 100010
#define maxt 1010
#define maxm 15
#define maxc 25
using namespace std;
int anti2;
int n,m,lim[maxn],anti[maxn];
int a[maxc][maxc],Sum[maxm][maxc][maxn];
void Prepare(int n,int m,int c)
{
static bool isPrime[maxn];
static int prime[maxn],top,mu[maxn],pw[maxc+maxm][maxn],p[maxn];
mu[1]=1;
fill(isPrime+2,isPrime+n+1,true);
for(int i=2;i<=n;++i)
{
if(isPrime[i]==true)
{
prime[++top]=i;
mu[i]=-1;
p[i]=1;
}
for(int j=1;j<=top&&prime[j]*i<=n;++j)
{
isPrime[i*prime[j]]=false;
if(i%prime[j]==0)
{
p[i*prime[j]]=p[i];
break;
}
else
mu[i*prime[j]]=-mu[i],p[i*prime[j]]=i;
}
}
for(int i=1;i<=n;++i)
pw[0][i]=1;
for(int i=1;i<=c+m;++i)
for(int j=1;j<=n;++j)
pw[i][j]=pw[i-1][j]*j%mod;
for(int i=0;i<=m;++i)
for(int j=0;j<=c;++j)
{
int *sum=Sum[i][j];
sum[1]=1,top=0;
for(int k=2;k<=n;++k)
{
if(isPrime[k])
++top,sum[k]=(pw[j+i][k]-pw[i][k]+mod)%mod;
for(int S=1;S<=top&&prime[S]*k<=n;++S)
{
int v=k*prime[S];
if(k%prime[S]==0)
{
if(p[v]!=1&&sum[p[v]]&&sum[v/p[v]])
sum[v]=sum[p[v]]*sum[v/p[v]]%mod;
else
sum[v]=(pw[j][v]-pw[j][k]+mod)*pw[i][v]%mod;
}
else if(sum[k])
sum[v]=sum[k]*sum[prime[S]]%mod;
}
}
for(int k=2;k<=n;++k)
sum[k]=(sum[k]+sum[k-1])%mod;
}
anti[1]=1;
for(int i=2;i<=n;++i)
{
int k=mod/i,r=mod%i;
anti[i]=i*k*k%mod*anti[r]%mod*anti[r]%mod;
}
a[0][0]=1;
for(int i=1;i<=c;++i)
{
int v=mod-i;
for(int j=i;j>=1;--j)
a[i][j]=(a[i-1][j]*v+a[i-1][j-1])%mod*anti[i]%mod;
a[i][0]=a[i-1][0]*v%mod*anti[i]%mod;
}
anti2=anti[2];
}
int work()
{
static int A[maxn],B[maxn],C[maxn];
int ans=0,c=m-2;
for(int i=1,nexti;i<=lim[1];i=nexti+1)
{
nexti=1<<30;
for(int j=1;j<=n;++j)
{
nexti=min(nexti,lim[j]/(lim[j]/i));
int d=lim[j]/i%mod;
B[j]=d*lim[j]%mod,A[j]=mod-(d+1)*d%mod*anti2%mod;
}
for(int j=1;j<=n;++j)
C[j]=0;
C[0]=1;
for(int j=1;j<=n;++j)
{
for(int k=j;k>=1;--k)
C[k]=(C[k]*B[j]+C[k-1]*A[j])%mod;
C[0]=C[0]*B[j]%mod;
}
for(int j=0;j<=c;++j)
for(int k=0;k<=n;++k)
ans=(ans+a[c][j]*C[k]%mod*(Sum[k][j][nexti]-Sum[k][j][i-1]+mod))%mod;
}
return ans;
}
void read()
{
static int LIM[maxt][maxm],N[maxt],M[maxt];
int T,max_n=0,max_m=0,max_c=0;
scanf("%d",&T);
for(int j=1;j<=T;++j)
{
scanf("%d %d",N+j,M+j);
max_m=max(max_m,N[j]),max_c=max(max_c,M[j]);
for(int i=1;i<=N[j];++i)
{
scanf("%d",LIM[j]+i);
max_n=max(max_n,LIM[j][i]);
}
sort(LIM[j]+1,LIM[j]+N[j]+1);
}
Prepare(max_n,max_m,max_c);
for(int j=1;j<=T;++j)
{
n=N[j],m=M[j];
for(int i=1;i<=n;++i)
lim[i]=LIM[j][i];
printf("%d\n",work());
}
}
int main()
{
freopen("space.in","r",stdin);
freopen("space.out","w",stdout);
read();
fclose(stdin);
fclose(stdout);
return 0;
}

  评论这张
 
阅读(507)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017