【BZOJ】3434: [Wc2014]時空穿梭-莫比烏斯反演

傳送門：bzoj3434

題解

枚舉每一維的極差 Δ x i \Delta x_i Δxi​，設 d = g c d ( Δ x 1 , Δ x 2 , . . . , Δ x n ) d=gcd(\Delta x_1,\Delta x_2,...,\Delta x_n) d=gcd(Δx1​,Δx2​,...,Δxn​)，則這條直線上最多可以選出 d d d個整點(不包含起點)。

則

a n s = ∑ Δ x 1 = 1 m 1 ⋯ ∑ Δ x n = 1 m n ( d − 1 c − 2 ) ∏ i = 1 n ( m i − Δ x i ) ans=\sum\limits_{\Delta x_1=1}^{m_1}\dots\sum\limits_{\Delta x_n=1}^{m_n}\dbinom{d-1}{c-2}\prod\limits_{i=1}^n(m_i-\Delta x_i) ans=Δx1​=1∑m1​​⋯Δxn​=1∑mn​​(c−2d−1​)i=1∏n​(mi​−Δxi​)

轉成枚舉 d d d

∑ d = 1 m ( d − 1 c − 2 ) ∑ Δ x 1 = 1 ⌊ m 1 d ⌋ ⋯ ∑ Δ x n = 1 ⌊ m n d ⌋ [ ( Δ x 1 , Δ x 2 , . . . , Δ x n ) = 1 ] ∏ i = 1 n ( m i − d Δ x i ) \sum\limits_{d=1}^m\dbinom{d-1}{c-2}\sum\limits_{\Delta x_1=1}^{\lfloor \frac{m_1}{d}\rfloor}\dots\sum\limits_{\Delta x_n=1}^{\lfloor \frac{m_n}{d}\rfloor}[(\Delta x_1,\Delta x_2,...,\Delta x_n)=1]\prod\limits_{i=1}^n(m_i-d\Delta x_i) d=1∑m​(c−2d−1​)Δx1​=1∑⌊dm1​​⌋​⋯Δxn​=1∑⌊dmn​​⌋​[(Δx1​,Δx2​,...,Δxn​)=1]i=1∏n​(mi​−dΔxi​)

莫比烏斯反演一下

∑ d = 1 m ( d − 1 c − 2 ) ∑ k = 1 ⌊ m d ⌋ μ ( k ) ∑ Δ x 1 = 1 ⌊ m 1 d k ⌋ ⋯ ∑ Δ x n = 1 ⌊ m n d k ⌋ ∏ i = 1 n ( m i − d k Δ x i ) \sum\limits_{d=1}^m\dbinom{d-1}{c-2}\sum\limits_{k=1}^{\lfloor\frac md \rfloor}\mu (k)\sum\limits_{\Delta x_1=1}^{\lfloor \frac{m_1}{dk}\rfloor}\dots\sum\limits_{\Delta x_n=1}^{\lfloor \frac{m_n}{dk}\rfloor}\prod\limits_{i=1}^n(m_i-dk\Delta x_i) d=1∑m​(c−2d−1​)k=1∑⌊dm​⌋​μ(k)Δx1​=1∑⌊dkm1​​⌋​⋯Δxn​=1∑⌊dkmn​​⌋​i=1∏n​(mi​−dkΔxi​)

設 T = d k T=dk T=dk，得到

∑ T = 1 m ( ∏ i = 1 n ∑ Δ x i = 1 ⌊ m i T ⌋ ( m i − T Δ x i ) ) ∑ d ∣ T ( d − 1 c − 2 ) μ ( T d ) \sum\limits_{T=1}^m(\prod\limits_{i=1}^n\sum\limits_{\Delta x_i=1}^{\lfloor \frac {m_i}{T}\rfloor}(m_i-T\Delta x_i))\sum\limits_{d|T}\binom{d-1}{c-2}\mu(\frac Td) T=1∑m​(i=1∏n​Δxi​=1∑⌊Tmi​​⌋​(mi​−TΔxi​))d∣T∑​(c−2d−1​)μ(dT​)

G ( T ) = ∑ d ∣ T ( d − 1 c − 2 ) μ ( T d ) G(T)=\sum\limits_{d|T}\binom{d-1}{c-2}\mu(\frac Td) G(T)=d∣T∑​(c−2d−1​)μ(dT​)可以 O ( m l n m ) O(mlnm) O(mlnm)預處理。

F ( T ) = ∏ i = 1 n ∑ Δ x i = 1 ⌊ m i T ⌋ ( m i − T Δ x i ) F(T)=\prod\limits_{i=1}^n\sum\limits_{\Delta x_i=1}^{\lfloor \frac {m_i}{T}\rfloor}(m_i-T\Delta x_i) F(T)=i=1∏n​Δxi​=1∑⌊Tmi​​⌋​(mi​−TΔxi​)

  = ∏ i = 1 n ( m i ⌊ m i T ⌋ + T ( ⌊ m i T ⌋ + 1 ) ⌊ m i T ⌋ 2 ) \qquad\ =\prod\limits_{i=1}^n(m_i\lfloor\frac {m_i}{T}\rfloor+\dfrac{T(\lfloor\frac {m_i}{T}\rfloor+1)\lfloor\frac {m_i}{T}\rfloor}{2})  =i=1∏n​(mi​⌊Tmi​​⌋+2T(⌊Tmi​​⌋+1)⌊Tmi​​⌋​)

在 ⌊ m i T ⌋ \lfloor\frac {m_i}{T}\rfloor ⌊Tmi​​⌋一定時， F ( T ) F(T) F(T)是一個關于 T T T的 n n n次多項式，是以 n m n\sqrt m nm

​分塊，每次 n 2 n^2 n2暴力處理 T i T^i Ti的系數 a i a_i ai​：

a n s = ∑ T = 1 m ∑ i = 0 n a i G ( T ) T i ans=\sum\limits_{T=1}^m\sum\limits_{i=0}^na_iG(T)T^i ans=T=1∑m​i=0∑n​ai​G(T)Ti

預處理出 G ( T ) T i G(T)T^i G(T)Ti的字首和即可。

複雜度： O ( m   l n   l n m + c m ln ⁡ m + c m n + T n 3 m ) O(m\ ln\ ln m+cm\ln m+cmn+Tn^3\sqrt m) O(m ln lnm+cmlnm+cmn+Tn3m

​)

代碼

#include<bits/stdc++.h>
#define mem(f,x) memset(f,x,sizeof(f))
typedef long long ll;
using namespace std;
const int N=1e5+10,mod=10007;

int tk,mxc,mxm,mn,ans,C[N][21],tmp[12];
int mu[N],g[21][N],f[21][12][N],p[N],num;bool pri[N];

char cp;
inline void rd(int &x)
{
    cp=getchar();x=0;
    for(;!isdigit(cp);cp=getchar());
    for(;isdigit(cp);cp=getchar()) x=x*10+(cp^48);
}

inline void upp(int &x,int y){if(y>x) x=y;}
inline void dnn(int &x,int y){if(y<x) x=y;}
inline void ad(int &x,int y){x+=y;if(x>=mod) x-=mod;}
inline void dc(int &x,int y){x-=y;if(x<0) x+=mod;}
inline int adi(int x,int y){x+=y;return x>=mod?x-mod:x;}
inline int dci(int x,int y){x-=y;return x<0?x+mod:x;}

inline void pre()
{
    int c,i,j,k,res;mu[1]=1;
    for(i=2;i<=mxm;++i){
        if(!pri[i]) p[++num]=i,mu[i]=-1;
        for(j=1;j<=num && (res=i*p[j])<=mxm;++j){
            pri[res]=true;if(i%p[j]==0) break;
            mu[res]=-mu[i];
        }
    }
    C[0][0]=1;
    for(i=1;i<=mxm;++i){
    	C[i][0]=1;
    	for(j=1;j<=mxc;++j) C[i][j]=adi(C[i-1][j-1],C[i-1][j]);
	}
	for(c=2;c<=mxc;++c){
        for(i=1;i<=mxm;++i){
            res=C[i-1][c-2];
            for(j=1,k=i;k<=mxm;++j,k+=i) if(mu[j])
                mu[j]<0?dc(g[c][k],res):ad(g[c][k],res);
        }
    }
    for(c=2;c<=mxc;++c){
       for(i=1;i<=mxm;++i){
          res=g[c][i];
          for(j=0;j<=11;++j){
            f[c][j][i]=adi(res,f[c][j][i-1]);
            res=(res*i)%mod;
          }
       }
    }
}

struct P{
    int n,c,m[12];

    inline void init()
    {
        rd(n);rd(c);upp(mxc,c);
        for(int i=1;i<=n;++i){rd(m[i]);upp(mxm,m[i]);}
    }

    inline void mk(int x)
    {
        int i,j,a,b;mem(tmp,0);tmp[0]=1;
        for(i=1;i<=n;++i){
            j=m[i]/x;
            a=mod-((ll)j*(j+1)/2)%mod;
            if(a==mod) a=0;
            b=(ll)j*m[i]%mod;
            for(j=n;j;--j) tmp[j]=adi(tmp[j]*b%mod,tmp[j-1]*a%mod);
            tmp[0]=tmp[0]*b%mod;
        }
    }

    inline void sol()
    {
        int i,j,k;ans=0;mn=2e9;
        for(i=1;i<=n;++i) dnn(mn,m[i]);
        for(i=1;i<=mn;i=j+1){
            for(j=mn,k=1;k<=n;++k) dnn(j,m[k]/(m[k]/i));
            for(mk(i),k=0;k<=n;++k) ad(ans,tmp[k]*dci(f[c][k][j],f[c][k][i-1])%mod);
        }
        printf("%d\n",ans);
    }
}q[1005];

int main(){
    int i,j;rd(tk);
    for(i=1;i<=tk;++i) q[i].init();
    pre();
    for(i=1;i<=tk;++i) q[i].sol();
    return 0;
}