【Codeforces 653G】Move by Prime

  由于每个质数之间的操作是相互独立的，所以把每个质数分开考虑。把每个数都质因子分解一遍，时间复杂度是\(O(n \sqrt{n})\)。

  官方的题解没有讲完，至今不知道它的从k个数到k+1个数是怎么转移的...

  对于质数p，第i个数可表示成\(t_i=p^{a_i} \cdot k\)的形式，其中k与p互质，然后将数组a排序。

  接下来要做的就是从数组a中选出一些数，进行最少的+1,-1的操作使得选出的这些数最终相等。

  显然，我们要让选出的数最终都等于它们的中位数的时候操作次数最少。

  例如，当我们选出的数为\(b_1,b_2,b_3, \cdots ,b_m\)时，最少操作次数等于\[\sum_{i=1}^{mid-1}{b_{mid}-b_i} +\sum_{i=mid+1}^{m}{b_i-b_{mid}}\]

  容易发现，一个数的贡献等于它被加上的次数减去它被减去的次数，乘以这个数本身的值。

  接下来要算的就是一个数最终被加上和减去了多少次。

  考虑\(a_k\)，如果在\(a_k\)左边有l个数，在\(a_k\)右边有r个数，那么

      1.当l<r时，\(a_k\)对答案贡献次数+1

      2.当l>r时，\(a_k\)对答案贡献次数-1

      3.当l=r时，\(a_k\)就是中位数，而且加减次数正好抵消，所以对答案没有贡献。

  思路比较清晰了，计算\(a_k\)的贡献，就是计算选k左边的数大于和小于k右边的数的方案个数，然后再乘上\(a_k\)。

  考虑这样一个多项式：\[(1+x)^{k-1} \cdot (1+x^{-1})^{n-k} = \frac{(1+x)^{n-1}}{x^{n-k}} \]

  利用组合的想法，结果的多项式中x的指数即l-r的值，x指数为正即l>r，系数则表示方案数。

  然后可以得到第k个数对答案的贡献为\[a_k \cdot (C_{n-1}^{n-1}+C_{n-1}^{n-2}+ \cdots +C_{n-1}^{n-k+1} -C_{n-1}^{n-k-1} - C_{n-1}^{n-k-2} - \cdots - C_{n-1}^{0})\]

  最后把一些质数的质数相同的项合并起来瞎JB优化一下就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=300010,p=1e9+7;

int Pow(long long x,int pow)
{
	int res=1;
	while (pow)
	{
		if (pow&1) res=(res*x)%p;
		x=(x*x)%p;
		pow>>=1;
	}
	return res;
}

int inv(int x) {return Pow(x,p-2);}

int Prime[maxn],Not_Prime[maxn],PToNum[maxn],Primes;
int C[maxn],CSum[maxn],CSSum[maxn];
int t[maxn];
int a[maxn][20];
int ans;
int n;

void Get_Prime()
{
	for (int i=2;i<maxn;i++)
	{
		if (!Not_Prime[i]) Prime[++Primes]=i,PToNum[i]=Primes;
		for (int j=1,temp;j<=Primes && (temp=Prime[j]*i)<maxn;j++)
		{
			Not_Prime[temp]=1;
			if (i%Prime[j]==0) break;
		}
	}
}

void Init_Comb()
{
	C[0]=CSum[0]=CSSum[0]=1;
	for (int i=1;i<n;i++)
		C[i]=((long long)C[i-1]*(n-i)%p)*inv(i)%p;
	for (int i=1;i<n;i++)
		CSum[i]=(CSum[i-1]+C[i])%p;
	for (int i=1;i<n;i++)
		CSSum[i]=(CSSum[i-1]+CSum[i])%p;
}

void Init()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&t[i]);
	Get_Prime();
	Init_Comb();
	
	for (int i=1;i<=Primes;i++) a[i][0]=n;
	
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=Primes && Prime[j]*Prime[j]<=t[i];j++) if (t[i]%Prime[j]==0)
		{
			int cnt=0;
			while (t[i]%Prime[j]==0) cnt++,t[i]/=Prime[j];
			a[j][cnt]++;
			a[j][0]--;
		}
		if (t[i]>1) a[PToNum[t[i]]][1]++,a[PToNum[t[i]]][0]--;
	}
}

void Solve()
{
	for (int i=1;i<=Primes;i++) if (a[i][0]<n)
	{
		int cnt=a[i][0];
		for (int j=1;cnt<n;cnt+=a[i][j++])
		{
			int res=0;
			res=(long long)a[i][j]*CSum[n-1]%p;
			res=((res+CSum[n-cnt-1]-2*CSSum[n-cnt-1])%p+p)%p;
			if (cnt+a[i][j]<n) res=((res-CSum[n-cnt-a[i][j]-1]+2*CSSum[n-cnt-a[i][j]-1]%p)%p+p)%p;
			res=(long long)res*j%p;
			ans=(ans+res)%p;
		}
	}
}

int main()
{
	Init();
	Solve();
	printf("%d\n",ans);
}