【Codeforces 653G】Move by Prime

Zarxdy34 posted @ 2016年4月05日 13:40 in Codeforces with tags 组合数学 , 309 阅读

  由于每个质数之间的操作是相互独立的,所以把每个质数分开考虑。把每个数都质因子分解一遍,时间复杂度是\(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);
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Copyright © 2007

Webdesign, tvorba www stránek

Valid XHTML 1.1