【WC2014】时空穿梭（莫比乌斯反演）

【WC2014】时空穿梭（莫比乌斯反演）

题目

枚举每一维上第一个点和最后一个点的坐标差 ( x 1 , . . x n ) (x_1,..x_n) (x1​,..xn​)
a n s = ∑ x 1 , x 2 . . . x n ( ( gcd ⁡ i = 1 n x i ) − 1 c − 2 ) ∏ i = 1 n ( m i − x i ) = ∑ d = 1 min ⁡ 1 n m i ( d − 1 c − 2 ) ∑ x 1 , x 2 . . . x n ≤ m i d [ gcd ⁡ i = 1 n x i = 1 ] ∏ i = 1 n ( m i − d x i ) = ∑ d = 1 min ⁡ 1 n m i ( d − 1 c − 2 ) ∑ x 1 , x 2 . . . x n ≤ m i d ∑ p ∣ x 1 , p ∣ x 2 . . . μ ( p ) ∏ i = 1 n ( m i − d x i ) = ∑ d = 1 min ⁡ 1 n m i ( d − 1 c − 2 ) ∑ p = 1 min ⁡ 1 n m i d μ ( p ) ∑ x 1 , x 2 . . . x n ≤ m i d p ∏ i = 1 n ( m i − d p x i ) = ∑ d = 1 min ⁡ 1 n m i ( d − 1 c − 2 ) ∑ p = 1 min ⁡ 1 n m i d μ ( p ) ∏ i = 1 n ∑ 1 ≤ x i ≤ m i d p ( m i − d p x i ) = ∑ d = 1 min ⁡ 1 n m i ( d − 1 c − 2 ) ∑ p = 1 min ⁡ 1 n m i d μ ( p ) ∏ i = 1 n ( 2 m i − d p − d p ⌊ m i d p ⌋ ) ⌊ m i d p ⌋ 2 = ∑ D = 1 m ∏ i = 1 n ( 2 m i − D − D ⌊ m i D ⌋ ) ⌊ m i D ⌋ 2 ∑ d ∣ D ( d − 1 c − 2 ) μ ( D d ) begin{aligned}ans &= sum_{x_1,_n} binom{ (gcd_{i=1}^n x_i) -1}{c-2} prod_{i=1}^n (m_i-x_i)\&=sum_{d=1}^{min_1^n m_i} binom{d-1}{c-2} sum_{x_1,_n leq frac{m_i}d}[gcd_{i=1}^nx_i = 1] prod_{i=1}^n(m_i-dx_i)\&=sum_{d=1}^{min_1^n m_i} binom{d-1}{c-2} sum_{x_1,_nleq frac{m_i}d}sum_{p|x_1,p|} mu(p) prod_{i=1}^n(m_i-dx_i)\&=sum_{d=1}^{min_1^n m_i} binom{d-1}{c-2} sum_{p=1}^{frac {min_{1}^n m_i}d} mu(p)sum_{x_1,_nleq frac{m_i}{dp}} prod_{i=1}^n(m_i-dpx_i)\&=sum_{d=1}^{min_1^n m_i} binom{d-1}{c-2} sum_{p=1}^{frac {min_{1}^n m_i}d} mu(p)prod_{i=1}^nsum_{1leq x_i leqfrac {m_i}{dp}} (m_i-dpx_i)\&=sum_{d=1}^{min_1^n m_i} binom{d-1}{c-2} sum_{p=1}^{frac {min_{1}^n m_i}d} mu(p)prod_{i=1}^nfrac {(2m_i-dp-dplfloor frac{m_i}{dp} rfloor)lfloor frac{m_i}{dp} rfloor}2\&=sum_{D=1}^mprod_{i=1}^n frac {(2m_i-D-Dlfloor frac{m_i}{D} rfloor)lfloor frac{m_i}{D} rfloor}2 sum_{d|D} binom{d-1}{c-2}mu(frac Dd)end{aligned} ans​=x1​,x2​...xn​∑​(c−2(gcdi=1n​xi​)−1​)i=1∏n​(mi​−xi​)=d=1∑min1n​mi​​(c−2d−1​)x1​,x2​...xn​≤dmi​​∑​[i=1gcdn​xi​=1]i=1∏n​(mi​−dxi​)=d=1∑min1n​mi​​(c−2d−1​)x1​,x2​...xn​≤dmi​​∑​p∣x1​,p∣x2​...∑​μ(p)i=1∏n​(mi​−dxi​)=d=1∑min1n​mi​​(c−2d−1​)p=1∑dmin1n​mi​​​μ(p)x1​,x2​...xn​≤dpmi​​∑​i=1∏n​(mi​−dpxi​)=d=1∑min1n​mi​​(c−2d−1​)p=1∑dmin1n​mi​​​μ(p)i=1∏n​1≤xi​≤dpmi​​∑​(mi​−dpxi​)=d=1∑min1n​mi​​(c−2d−1​)p=1∑dmin1n​mi​​​μ(p)i=1∏n​2(2mi​−dp−dp⌊dpmi​​⌋)⌊dpmi​​⌋​=D=1∑m​i=1∏n​2(2mi​−D−D⌊Dmi​​⌋)⌊Dmi​​⌋​d∣D∑​(c−2d−1​)μ(dD​)​

右边可以调和级数预处理，设 G ( x ) = ∑ d ∣ x ( d − 1 c − 2 ) μ ( x d ) G(x) = sum_{d|x} binom{d-1}{c-2} mu(frac xd) G(x)=∑d∣x​(c−2d−1​)μ(dx​)。
左边的这个 ∏ prod ∏我们看作一个 n n n次的关于 D D D的多项式，
那么因为对于 i ∈ [ 1 , n ] iin[1,n] i∈[1,n] m i D frac {m_i}D Dmi​​有 O ( n m ) O(nsqrt m) O(nm ​)种取值，
所以一共有 O ( n m ) O(nsqrt m) O(nm ​)种不同的多项式。
假设在某一段这个多项式是
P ( x ) = ∑ i = 0 n a i x i P(x) = sum_{i=0}^n a_i x^i P(x)=∑i=0n​ai​xi
那么在这一段我们需要求的就是
∑ i = l r G ( i ) P ( i ) = ∑ i = l r G ( i ) ∑ j = 0 n a j i j sum_{i=l}^r G(i)P(i) = sum_{i=l}^r G(i) sum_{j=0}^n a_ji^j ∑i=lr​G(i)P(i)=∑i=lr​G(i)∑j=0n​aj​ij
= ∑ j = 0 n a j ∑ i = l r G ( i ) i j =sum_{j=0}^n a_jsum_{i=l}^r G(i)i^j =∑j=0n​aj​∑i=lr​G(i)ij
因为 n n n很小，所以后面那个 ∑ i = 1 r G ( i ) i j sum_{i=1}^r G(i)i^j ∑i=1r​G(i)ij是可以直接预处理的。
至于 a i a_i ai​，暴力多项式乘法就行了，复杂度是 O ( n 2 ) O(n^2) O(n2)的。你也可以写分治NTT

A C C o d e mathcal AC Code AC Code

#include<bits/stdc++.h>
#define maxn 100005
#define mod 10007
#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
#define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--)
using namespace std;int n,c,m[12],cc[maxn][22];
int fac[maxn],inv[maxn],invf[maxn],mu[maxn],G[12][22][maxn],a[maxn],vis[maxn],pr[maxn],cnt_pr;
int C(int a,int b){if(a < 0 || b < 0 || a-b < 0) return 0;return cc[a][b];
}
int ar[12];
void add(int x0,int x1){per(i,n,0) ar[i] = (ar[i] * x0 + (i ? ar[i-1] : 0) * x1) % mod;
}int main(){fac[0] = fac[1] = inv[0] = inv[1] = invf[0] = invf[1] = 1;mu[1] = 1;rep(i,cc[0][0]=1,maxn-1)rep(j,cc[i][0]=1,min(i,20))cc[i][j] = (cc[i-1][j-1] + cc[i-1][j]) % mod;rep(i,2,maxn-1){fac[i] = 1ll * fac[i-1] * i % mod;inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod,invf[i] = 1ll * inv[i] * invf[i-1] % mod;if(!vis[i]) pr[cnt_pr++] = i , mu[i] = -1;for(int j=0;pr[j] * i < maxn;j++){vis[i * pr[j]] = 1;if(i % pr[j] == 0){mu[i * pr[j]] = 0;break;}mu[i * pr[j]] = - mu[i];}}rep(c,2,20) rep(i,1,maxn-1)for(int j=i;j<maxn;j+=i)G[0][c][j] = (G[0][c][j] + mu[i] * C(j/i-1,c-2)) % mod;rep(p,1,11) rep(c,2,20) rep(i,1,maxn-1)G[p][c][i] = G[p-1][c][i] * i % mod;rep(p,0,11) rep(c,2,20) rep(i,1,maxn-1)G[p][c][i] = (G[p][c][i] + G[p][c][i-1]) % mod;int T;for(scanf("%d",&T);T--;){scanf("%d%d",&n,&c);int ans = 0;rep(i,1,n) scanf("%d",&m[i]);sort(m+1,m+n+1);for(int i=1,nxt;i<=m[1]-1;i=nxt+1){nxt = 0x3f3f3f3f;memset(ar,0,sizeof ar);ar[0] = 1;rep(j,1,n){nxt = min(nxt , (m[j]-1) / ((m[j]-1) / i));int v = (m[j]-1) / i;//	printf("@%d %dn",(m[j]*v-v)%mod,(-v-v*v)%mod*inv[2]%mod);add((m[j]*v)%mod,(-v-v*v)%mod*inv[2]%mod);}rep(j,0,n){ ans = (ans + 1ll * ar[j] * (G[j][c][nxt] - G[j][c][i-1])) % mod;//printf("@%d %d %d %dn",j,ar[j],G[j][c][nxt]-G[j][c][i-1],ans);}}printf("%dn",(ans+mod)%mod);}
}