BZOJ 3434 [WC2014]时空穿梭 (莫比乌斯反演)

题面：BZOJ传送门洛谷传送门

好难啊..反演的终极题目

首先，本题的突破口在于直线的性质。不论是几维的空间，两点一定能确定一条直线

选取两个点作为最左下和最右上的点！

假设现在是二维空间，选取了$(x1,y1)$和$(x2,y2)$两个点，那么它们连线上经过的点数就是$gcd(x2-x1,y2-y1)-1$

选取的方案数为$\left ( _{gcd-1}^{c-2} \right )$

发现这个方案数只和坐标的差值有关，我们直接枚举差值就行

接下来就是反演了，为了方便叙述，以$n=2$为例

$\sum\limits_{x=1}^{m_{1}}\sum\limits_{y=1}^{m_{2}} \left ( _{c-2}^{gcd(x,y)-1} \right ) (m_{1}-x)(m_{2}-y)$

$\sum\limits_{k=1}^{m} \left ( _{c-2}^{k-1} \right ) \sum\limits_{x=1}^{m_{1}} \sum\limits_{y=1}^{m_{2}} [gcd(x,y)==k] (m_{1}-x)(m_{2}-y)$

$\sum\limits_{k=1}^{m} \left ( _{c-2}^{k-1} \right ) \sum\limits_{x=1}^{\left \lfloor \frac{m_{1}}{k} \right \rfloor} \sum\limits_{y=1}^{\left \lfloor \frac{m_{2}}{k} \right \rfloor} [gcd(x,y)==1] (m_{1}-xk)(m_{2}-yk)$

$\sum\limits_{k=1}^{m} \left ( _{c-2}^{k-1} \right ) \sum\limits_{d=1}^{\left \lfloor \frac{m_{1}}{k} \right \rfloor} \mu(d) \sum\limits_{x=1}^{\left \lfloor \frac{m_{1}}{kd} \right \rfloor} (m_{1}-xkd) \sum\limits_{y=1}^{ \left \lfloor \frac{m_{2}}{kd} \right \rfloor} (m_{2}-ykd)$

令$Q=kd$

$\sum\limits_{Q=1}^{m} \left ( \sum\limits_{k|Q} \left ( _{c-2}^{k-1} \right ) \mu(\frac{Q}{k}) \right ) \left ( \sum\limits_{x=1}^{\left \lfloor \frac{m_{1}}{Q} \right \rfloor} (m_{1}-xQ) \right ) \left ( \sum\limits_{y=1}^{ \left \lfloor \frac{m_{2}}{Q} \right \rfloor} (m_{2}-yQ) \right ) $

利用等差数列公式 $\left ( \sum\limits_{x=1}^{\left \lfloor \frac{m}{Q} \right \rfloor} (m-xQ) \right ) = \left ( \left \lfloor \frac{m}{Q} \right \rfloor m- \frac{ (1+\left \lfloor \frac{m}{Q} \right \rfloor )\left \lfloor \frac{m}{Q} \right \rfloor Q}{2} \right ) $

$\sum\limits_{Q=1}^{m} \left ( \sum\limits_{k|Q} \left ( _{c-2}^{k-1} \right ) \mu(\frac{Q}{k}) \right ) \left ( \left \lfloor \frac{m_{1}}{Q} \right \rfloor m_{1}- \frac{ (1+\left \lfloor \frac{m_{1}}{Q} \right \rfloor )\left \lfloor \frac{m_{1}}{Q} \right \rfloor Q}{2} \right ) \left ( \left \lfloor \frac{m_{2}}{Q} \right \rfloor m_{2}- \frac{ (1+\left \lfloor \frac{m_{2}}{Q} \right \rfloor )\left \lfloor \frac{m_{2}}{Q} \right \rfloor Q}{2} \right ) $

推广到更高维上

$\sum\limits_{Q=1}^{m} \left ( \sum\limits_{k|Q} \left ( _{c-2}^{k-1} \right ) \mu(\frac{Q}{k}) \right ) \prod_{t=1}^{n} \left ( \left \lfloor \frac{m_{t}}{Q} \right \rfloor m_{t}- \frac{ (1+\left \lfloor \frac{m_{t}}{Q} \right \rfloor )\left \lfloor \frac{m_{t}}{Q} \right \rfloor Q}{2} \right ) $

我们不能把$Q$这一项带入到整除分块里去

所以每次$O(n^{2})$暴力计算出$Q^{k}(k=0,1,2...n)$的系数

预处理出$f(Q,c)=\sum\limits_{k|Q} \left ( _{c-2}^{k-1} \right ) Q^{u}$

用整除分块即可

时间$O(Tn^{3}\sqrt {m})$

人傻常数大，BZOJ过不去，洛谷上开O2过了，懒得优化了

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define ll long long

 #define N1 100100

 using namespace std;

 const int inf=0x3f3f3f3f;

 int gint()

 {

     int ret=,fh=;char c=getchar();

     while(c<''||c>''){if(c=='-')fh=-;c=getchar();}

     while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}

     return ret*fh;

 }

 const int zwz=;

 int qpow(int x,int y)

 {

     int ans=;

     for(;y;x=x*x%zwz,y>>=) if(y&) ans=ans*x%zwz;

     return ans;

 }

 int T,n,c,cnt;

 int mu[N1],pr[N1],use[N1], f[][N1][],m[N1],C[N1][],mul[N1],_mul[N1];

 int maxn=;

 int Lucas(int a,int b)

 {

     if(b>a) return ;

     if(a<zwz&&b<zwz) return mul[a]*_mul[b]%zwz*_mul[a-b]%zwz;

     else return Lucas(a%zwz,b%zwz)*Lucas(a/zwz,b/zwz)%zwz;

 }

 void Pre()

 {

     int i,j,k,l;

     mu[]=;

     for(i=;i<=maxn;i++)

     {

         if(!use[i]) pr[++cnt]=i,mu[i]=-;

         for(j=;(j<=cnt)&&(i*pr[j]<=maxn);j++)

         {

             use[i*pr[j]]=;

             if(i%pr[j]) mu[i*pr[j]]=-mu[i];

             else mu[i*pr[j]]=;

         }

     }

     mul[]=mul[]=_mul[]=_mul[]=;

     for(i=;i<zwz;i++)

     {

         mul[i]=mul[i-]*i%zwz;

         _mul[i]=qpow(mul[i],zwz-);

     }

     for(i=;i<=maxn;i++) for(k=;k<=min(i,);k++)

         C[i][k]=Lucas(i,k);

     for(i=;i<=maxn;i++) for(j=i;j<=maxn;j+=i)

     {

         for(k=;k<=;k++)

             (f[][j][k]+=C[i-][k-]*mu[j/i]%zwz+zwz)%=zwz;

     }

     for(l=;l<=;l++) for(i=;i<=maxn;i++) for(k=;k<=;k++) f[l][i][k]=i*f[l-][i][k]%zwz;

     for(l=;l<=;l++) for(i=;i<=maxn;i++) for(k=;k<=;k++) (f[l][i][k]+=f[l][i-][k])%=zwz;

 }

 int p[][];

 int main()

 {

     scanf("%d",&T);

     int i,la,j,x,y,k,t,mi,ans,tmp,inv2,now,pst;// ll ans=0;

     Pre();

     for(t=;t<=T;t++){

     scanf("%d%d",&n,&c); ans=; inv2=qpow(,zwz-);

     for(i=,mi=inf;i<=n;i++) m[i]=gint(), mi=min(mi,m[i]);

     for(i=;i<=mi;i=la+)

     {

         for(j=,la=inf;j<=n;j++) la=min(la,m[j]/(m[j]/i));

         memset(p,,sizeof(p)); now=; pst=; p[pst][]=;

         for(j=;j<=n;j++)

         {

             memset(p[now],,sizeof(p[now]));

             for(k=;k<n;k++)

                 p[now][k+]=(p[now][k+]-p[pst][k]*(+m[j]/i)%zwz*(m[j]/i)%zwz*inv2%zwz+zwz)%zwz,

                 p[now][k]=(p[now][k]+p[pst][k]*(m[j]/i)%zwz*m[j])%zwz;

             swap(now,pst);

         }

         for(k=;k<=n;k++)

             ans=(ans+p[pst][k]*(f[k][la][c]-f[k][i-][c]+zwz)%zwz)%zwz;

     }

     printf("%d\n",ans);

     }

     return ;

 }

巴特西

BZOJ 3434 [WC2014]时空穿梭 (莫比乌斯反演)

最新文章

热门文章