CF653G Move by Prime 题解
Link.
Codeforces
Luogu
Description.
定义 \(F(S)\) 为把 \(S\) 中每次可以把每个元素 \(\times p,\div p(p\in\text{prime})\) 把所有元素变相同的最少步数。
求 \(\sum_{T\subseteq S}F(T)\)。
Solution.
质因数可以拆开，分别求解
对于每个质因数，有一个序列表示指数
现在相当于对所有子序列求到中位数差之和
可以考虑枚举中位数为 \(m\)（定义中位数偏左
然后相当于要求 \(\sum|X-m|\) 其中 \(m\) 是中位数。
绝对值拆开后，\(m\) 的贡献肯定是 \(0\)。
相当于在左边选 \(a\) 个，右边选 \(b\) 个的贡献是下式：
可以枚举 \(b-a+i-1\)，意义是左边不选个数和右边选个数之和。
因为 \(i\) 当前确定，左边不选、右边选总方案数就相当于从 \(n-1\) 里选出这些数，方案数是 \(\dbinom{n-1}{b-a+i-1}\)。
则有贡献为
然后预处理组合数前缀和就做完了。
Coding.
点击查看代码
//Coded by Kamiyama_Shiki on 2021.11.14 {{{
//是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了
#include
using namespace std;typedef long long ll;
templateinline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
f?x=-x:x;
}
templateinline void read(T &x,L&...l) {read(x),read(l...);}//}}}
const int N=300005,P=1000000007;
namespace Binom//{{{
{
int fc[N],fi[N],iv[N];//dbinit
inline int ksm(int x,int q=P-2) {int r=1;for(;q;q>>=1,x=1ll*x*x%P) if(q&1) r=1ll*r*x%P;return r;}
inline void dbinit(int n=N-1)
{
fc[0]=1;for(int i=1;i<=n;i++) fc[i]=1ll*fc[i-1]*i%P;
iv[1]=1;for(int i=2;i<=n;i++) iv[i]=1ll*iv[P%i]*(P-P/i)%P;
fi[0]=1;for(int i=1;i<=n;i++) fi[i]=1ll*fi[i-1]*iv[i]%P;
}
inline int C(int n,int m) {return n<0||m<0||nfc[N];
int main()
{
read(n),prinit(),dbinit();for(int i=1;i<=n;i++) read(a[i]);
int pw=ksm(2,n-1);for(int i=n-1;~i;i--) qz[i]=(qz[i+1]+(c[i]=C(n-1,i)))%P;
for(int i=1,x=a[i];i<=n;x=a[++i]) while(ls[x]) {int v=ls[x],c=0;while(x%v==0) x/=v,c++;fc[v].push_back(c);}
for(int i=1;i