【CF653G】Move by Prime

题意：给你一个长度为n的数列$a_i$，你可以进行任意次操作：将其中一个数乘上或者除以一个质数。使得最终所有数相同，并使得操作数尽可能小。现在我们想要知道$a_i$的所有子序列的操作数之和是多少。答案对$10^9+7$取模。

$n,a_i\le 3\times 10^5$

题解：显然要对每个质数分别处理。而对于每个质数，最终一定是让所有数都变成该序列的中位数最优。因此如果所有数的次数分别是$k_1,k_2...k_n$，则如果i在中位数左边，则贡献为$-k_i$，否则贡献为$k_i$。那么我们只需要知道有多少子序列满足i在中位数左边/有边就行了。

考虑如下生成函数：

$(1+{1\over x})^{i-1}(1+x)^{n-i}={(1+x)^{n-1}\over x^{i-1}}$

它的意义显然是：$x^j$的系数等于i右面的数比左面的数多j的方案数。显然我们要的就是所有j为正的系数-所有j为负的系数。显然就是：

$\sum\limits_{j=i}^nC_{n-1}^j-\sum\limits_{j=0}^{i-2}C_{n-1}^j$

维护个组合数的前缀和就好了。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

const int maxn=300010;

typedef long long ll;

const ll P=1000000007;

int n,num;

ll ans;

int pri[maxn],vis[maxn];

ll s[maxn],ine[maxn],jc[maxn],jcc[maxn];

vector<int> v[maxn];

vector<int>::iterator it;

inline ll c(int a,int b)

{

	if(a<b)	return 0;

	return jc[a]*jcc[b]%P*jcc[a-b]%P;

}

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+(gc^'0'),gc=getchar();

	return ret*f;

}

int main()

{

	n=rd();

	int i,j,t;

	for(i=1;i<=n;i++)

	{

		t=rd();

		for(j=2;j*j<=t;j++)	if(t%j==0)

		{

			if(!vis[j])	pri[++num]=j,vis[j]=num;

			int tmp=0;

			while(t%j==0)	t/=j,tmp++;

			v[vis[j]].push_back(tmp);

		}

		if(t!=1)

		{

			if(!vis[t])	pri[++num]=t,vis[t]=num;

			v[vis[t]].push_back(1);

		}

	}

	ine[0]=ine[1]=jc[0]=jc[1]=jcc[0]=jcc[1]=1;

	for(i=2;i<=n;i++)	ine[i]=P-(P/i)*ine[P%i]%P,jc[i]=jc[i-1]*i%P,jcc[i]=jcc[i-1]*ine[i]%P;

	s[0]=1;

	for(i=1;i<n;i++)	s[i]=(s[i-1]+c(n-1,i))%P;

	for(i=1;i<=num;i++)

	{

		int k=n-v[i].size();

		sort(v[i].begin(),v[i].end());

		for(it=v[i].begin();it!=v[i].end();it++)

		{

			k++;

			ans=(ans+(*it)*(((k==1)?0:s[k-2])-s[n-1]+s[k-1]))%P;

		}

	}

	printf("%lld",ans);

	return 0;

巴特西

【CF653G】Move by Prime 组合数

【CF653G】Move by Prime

最新文章

热门文章