如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY-NC-SA 4.0 （除特别声明或转载文章外）
考虑一个问题，给定一个长为 $n$ 的 $01$ 序列，定义一次操作可以把一个位置取反，一个序列的权值为使得序列内数全部相同的最少操作次数，$f_x$ 为有 $x$ 个 $1$ 的序列的所有子序列的权值和。
我们枚举值域内的所有素数幂，设原序列内存在 $c$ 个数为该素数幂的倍数，则答案为 $\sum f_c$，正确性显然。
考虑 $f_x$ 的计算。 \(\begin{aligned} f_x=&\sum\limits_{i=0}^x\sum\limits_{j=0}^{n-x}\binom{x}{i}\binom{n-x}{j}\min(i,j)\\ =&\sum\limits_{t=1}^{\infin}\sum\limits_{i=t}^{\infin}\sum\limits_{j=t}^{\infin}[u^xv^{n-x}]\sum\limits_{a=i}^{\infin}\binom{a}{i}u^a\sum\limits_{b=j}^{\infin}\binom{b}{j}v^b\\ =&[u^xv^{n-x}]\sum\limits_{t=1}^{\infin}\sum\limits_{i=t}^{\infin}\sum\limits_{j=t}^{\infin}\frac{u^i}{(1-u)^{i+1}}\frac{v^j}{(1-v)^{j+1}}\\ =&[u^xv^{n-x}]\sum\limits_{t=1}^{\infin}\frac{u^t}{(1-u)^{t+1}}\frac{v^t}{(1-v)^{t+1}}\sum\limits_{i=0}^{\infin}\frac{u^i}{(1-u)^i}\sum\limits_{j=0}^{\infin}\frac{v^j}{(1-v)^j}\\ =&[u^xv^{n-x}]\sum\limits_{t=1}^{\infin}\frac{u^t}{(1-u)^{t+1}}\frac{v^t}{(1-v)^{t+1}}\frac{1}{1-\frac{u}{1-u}}\frac{1}{1-\frac{v}{1-v}}\\ =&[u^xv^{n-x}]\frac{uv}{(1-2u)(1-2v)(1-u)(1-v)}\sum\limits_{t=0}^{\infin}\frac{u^tv^t}{(1-u)^t(1-v)^t}\\ =&[u^xv^{n-x}]\frac{uv}{(1-2u)(1-2v)(1-u)(1-v)}\frac{1}{1-\frac{uv}{(1-u)(1-v)}}\\ =&[u^xv^{n-x}]\frac{uv}{(1-2u)(1-2v)(1-u-v)}\\ =&[u^xv^n]\frac{uv^2}{(1-2uv)(1-2v)(1-uv-v)}\\ =&[u^xv^n]\frac{uv^2}{(1-u)^2}\left(\frac{2u^2}{1-2uv}+\frac{2}{1-2v}-\frac{(1+u)^2}{1-uv-v}\right) \end{aligned}\)
温馨提示，最后一步的分式分解可能不是人能手算出来的。
我们依次考虑三部分的取值。
\[\begin{aligned} &2[u^{x-3}v^{n-2}]\frac{1}{(1-u)^2(1-2uv)}\\ =&2[u^{x-3}v^{n-2}]\frac{1}{(1-u)^2}\sum\limits_{i=0}^{\infin}(2uv)^i\\ =&2[u^{x-3}]\frac{1}{(1-u)^2}(2u)^{n-2} \end{aligned}\]因为 $x\le n$，$x-3<n-2$，所以这一项是 $0$。
\[\begin{aligned} &2[u^{x-1}v^{n-2}]\frac{1}{(1-u)^2}\frac{1}{1-2v}\\ =&2[u^{x-1}v^{n-2}]\frac{1}{(1-u)^2}\sum\limits_{i=0}^{\infin}(2v)^i\\ =&2^{n-1}[u^{x-1}]\frac{1}{(1-u)^2}\\ =&2^{n-1}x \end{aligned}\] \[\begin{aligned} &[u^{x-1}v^{n-2}]\frac{(1+u)^2}{(1-u)^2(1-v(1+u))}\\ =&[u^{x-1}v^{n-2}]\frac{(1+u)^2}{(1-u)^2}\sum\limits_{i=0}^{\infin}(v(1+u))^i\\ =&[u^{x-1}]\frac{(1+u)^n}{(1-u)^2}\\ =&\sum\limits_{i=0}^{x-1}\binom{n}{i}(x-1-i+1)\\ =&x\sum\limits_{i=0}^{x-1}\binom{n}{i}-\sum\limits_{i=0}^{x-1}i\binom{n}{i} \end{aligned}\]所以 $f_x=2^{n-1}x-x\sum\limits_{i=0}^{x-1}\binom{n}{i}+\sum\limits_{i=0}^{x-1}i\binom{n}{i}$，我们可以在 $O(n)$ 的复杂度内求解出所有 $f_x$。
总复杂度为 $O(n\log\log n)$，复杂度瓶颈在于求出素数幂倍数的数量。
感谢 EI 和 GuidingStar 帮忙推式子。
#include<cstdio>
#include<algorithm>
int const mod=1e9+7;
int pow(int x,int y){
int res=1;
while(y){
if(y&1) res=1ll*res*x%mod;
y>>=1,x=1ll*x*x%mod;
}
return res;
}
int n,a[300010],m,p[300010],np[300010],cnt,ans,f[300010],fac[300010],ifac[300010];
int main(){
scanf("%d",&n);
for(int i=1,x;i<=n;i++)scanf("%d",&x),m=std::max(x,m),a[x]++;
for(int i=2;i<=m;i++){
if(!np[i]) p[++cnt]=i;
for(int j=1;i*p[j]<=m;j++){
np[i*p[j]]=1;
if(i%p[j]==0) break;
}
}
f[0]=1;
for(int i=1;i<n;i++) f[0]=f[0]*2%mod;
for(int i=1;i<=n;i++) f[i]=1ll*f[0]*i%mod;f[0]=0;
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
ifac[n]=pow(fac[n],mod-2);
for(int i=n;i;i--) ifac[i-1]=1ll*ifac[i]*i%mod;
for(int i=0,k=0,q=0;i<n;i++){
k=(k+1ll*fac[n]*ifac[i]%mod*ifac[n-i])%mod;
q=(q+1ll*i*fac[n]%mod*ifac[i]%mod*ifac[n-i])%mod;
f[i+1]=(f[i+1]-(i+1ll)*k%mod+q+mod)%mod;
}
for(int i=1;i<=cnt;i++){
long long q=p[i];
while(q<=m){
int cnt=0;
for(int j=q;j<=m;j+=q) cnt+=a[j];
ans=(ans+f[cnt])%mod;
q*=p[i];
}
}
printf("%d\n",ans);
return 0;
}