【WC2014】时空穿梭（莫比乌斯反演）（组合数学）

本文主要是介绍【WC2014】时空穿梭（莫比乌斯反演）（组合数学），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

考虑枚举各维最大最小坐标的差量 $\Delta_i$ ，可以写出式子： $Ans=\sum_{\Delta}\binom{gcd(\Delta_{1...n})-1}{c-2}\prod_{i=1}^n (m_i-\Delta_i)\\ =\sum_d\binom{d-1}{c-2}\sum_{\Delta}\prod_{i=1}^n (m_i-d\Delta_i)[gcd(\Delta_{1...n})=1]\\=\sum_d\binom{d-1}{c-2}\sum_{l}\mu(l)\sum_{\Delta}(\prod_{i=1}^nm_i-dl\Delta_i)\\ =\sum_{T}\prod_{i=1}^n(\sum_{j}^{m_i/T}m_i-Tj)\sum_{l|T}\mu(l)\binom{d-1}{c-2}$
对前面整除分块（ $O(n\sqrt M)$ ）段，每一段是关于 $T$ 的 $n$ 次多项式 $f (T)$ ，可以 $O(n^2)$ 求得第 $k$ 项的系数，所以现在就是要求
$\sum_{T=l}^rcoef_k (T^k\sum_{l|T}\mu(l)\binom{d-1}{c-2})$
后面可以 $O(ncM+cM\log M)$ 预处理得到，询问的复杂度是 $O(Tn^3\sqrt M)$

#include<bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
typedef long long ll;
cs int Mod = 10007;
int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; }
int dec(int a, int b){ return a - b < 0 ? a - b + Mod : a - b; }
int mul(int a, int b){ return 1ll * a * b % Mod; }
void Add(int &a, int b){ a = add(a,b); }
void Dec(int &a, int b){ a = dec(a,b); }
void Mul(int &a, int b){ a = mul(a,b); }
int ksm(int a, int b){ int as=1; for(;b;b>>=1,Mul(a,a)) if(b&1) Mul(as,a); return as; }
cs int N = 1e5 + 50;
int T, n, c, a[20];
int f[20][N], prm[N], pc, mu[N]; bool isp[N];
int fc[N], ifc[N], pw[20][12][N];
void fc_init(int n){fc[0]=fc[1]=ifc[0]=ifc[1]=1;for(int i=2; i<=n; i++) fc[i]=mul(fc[i-1],i);ifc[n]=ksm(fc[n],Mod-2);for(int i=n-1;i>=2;i--) ifc[i]=mul(ifc[i+1],i+1);
}
int C(int n, int m){ if(n<0||m<0||n<m) return 0; return mul(fc[n],mul(ifc[n-m],ifc[m])); }
int binom(int n, int m){if(n<Mod&&m<Mod) return C(n,m);return mul(C(n%Mod,m),binom(n/Mod,m/Mod));
}
void pre_work(int n){mu[1]=1; for(int i=2; i<=n; i++){if(!isp[i]) prm[++pc]=i, mu[i]=-1;for(int j=1; j<=pc&&prm[j]*i<=n; ++j){isp[prm[j]*i]=1;if(i%prm[j]==0) break; mu[i*prm[j]]=-mu[i];}} for(int c=0; c<=18; c++){for(int i=1; i<=n; i++) f[c][i]=binom(i-1,c);for(int i=n; i>=1; i--)for(int j=i+i; j<=n; j+=i)if(mu[j/i]){if(mu[j/i]>0) Add(f[c][j],f[c][i]);else Dec(f[c][j],f[c][i]);}} for(int i=1; i<=n; i++)for(int j=0; j<=18; j++)for(int c=0,mt=1; c<=11; c++,Mul(mt,i))pw[j][c][i]=add(pw[j][c][i-1],mul(f[j][i],mt));
}
int sub(int l, int r){ return ((ll)(l+r)*(r-l+1)>>1)%Mod; }
int calc(int l, int r){ static int dp[20];for(int i=0; i<=n; i++) dp[i]=0; dp[0]=1;for(int i=1; i<=n; i++)for(int j=i; j>=0; j--){Mul(dp[j],mul(a[i],a[i]/l));Dec(dp[j],mul(dp[j-1],sub(1,a[i]/l)));} int ans=0;for(int i=0; i<=n; i++)Add(ans,mul(dp[i],dec(pw[c-2][i][r],pw[c-2][i][l-1])));//,cout<<dec(pw[c-2][i][r],pw[c-2][i][l-1])<<" ";cout<<endl;
//	cout<<"calc "<<l<<" "<<r<<endl;
//	for(int i=0; i<=n; i++) cout<<dp[i]<<" ";cout<<endl;
//	cout<<endl<<ans<<endl;return ans;
}
void Main(){scanf("%d%d",&n,&c); int m=1e5;for(int i=1; i<=n; i++) scanf("%d",&a[i]),m=min(m,a[i]);int Ans=0;for(int l=1,r;l<=m;l=r+1){r=m; for(int i=1; i<=n; i++) r=min(r,a[i]/(a[i]/l));Add(Ans,calc(l,r));} cout<<Ans<<'\n';
}
int main(){#ifdef FSYolandafreopen("1.in","r",stdin);#endifscanf("%d",&T);fc_init(Mod-1); pre_work(1e5);while(T--) Main();return 0;
}