「Codeforces 653G」Move by Prime – 题解

主要思路

这些 3000+ 题目里做过最小清新的。

首先肯定可以想到，分解质因子之后，对于一个 \(p^c\)，把每个元素该质因子的指数拿出来做中位数即为此质因子的贡献。我大概想到这里就断片了。

然而这个题完全可以拆出每个数的贡献来算。对于第 \(i\) 个数而言，在中位数左侧的贡献是 \(-c_i\)、右侧的贡献是 \(c_i\)。生成函数显然是：

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

那么这个写成组合数就是：

\[ \sum_{j = i}^{n – 1} {n – 1 \choose j} – \sum_{j = 0}^{i – 2} {n – 1 \choose j} \]

维护下即可。

代码

// CF653G.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3e5 + 200, mod = 1e9 + 7;

int n, ai[MAX_N], ptot, pid[MAX_N], fac[MAX_N], fac_inv[MAX_N], inv[MAX_N], pre[MAX_N];
vector<int> pidx[MAX_N];

void initialize()
{
	for (int i = fac[0] = 1; i < MAX_N; i++)
		fac[i] = 1LL * fac[i - 1] * i % mod;
	inv[0] = inv[1] = fac_inv[0] = 1;
	for (int i = 2; i < MAX_N; i++)
		inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
	for (int i = 1; i < MAX_N; i++)
		fac_inv[i] = 1LL * fac_inv[i - 1] * inv[i] % mod;
}

int binomial(int n_, int k_) { return 1LL * fac[n_] * fac_inv[k_] % mod * fac_inv[n_ - k_] % mod; }

void factorize(int x)
{
	int acc = x;
	for (int i = 2; 1LL * i * i <= acc; i++)
		if (acc % i == 0)
		{
			if (pid[i] == 0)
				pid[i] = ++ptot;
			int idxcnt = 0;
			while (acc % i == 0)
				idxcnt++, acc /= i;
			pidx[pid[i]].push_back(idxcnt);
		}
	if (acc > 1)
	{
		if (pid[acc] == 0)
			pid[acc] = ++ptot;
		pidx[pid[acc]].push_back(1);
	}
}

int main()
{
	initialize(), scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &ai[i]), factorize(ai[i]);
	pre[0] = binomial(n - 1, 0);
	for (int i = 1; i <= n - 1; i++)
		pre[i] = (0LL + pre[i - 1] + binomial(n - 1, i)) % mod;
	int ans = 0;
	for (int ptr = 1; ptr <= ptot; ptr++)
	{
		sort(pidx[ptr].begin(), pidx[ptr].end());
		int rest0 = n - pidx[ptr].size();
		for (int i = 0, siz = pidx[ptr].size(); i < siz; i++)
		{
			rest0++, ans = (0LL + ans + 1LL * pidx[ptr][i] * ((0LL + (rest0 == 1 ? 0 : pre[rest0 - 2])	+ pre[rest0 - 1] + mod - pre[n - 1]) % mod) % mod) % mod;
		}
	}
	printf("%d\n", ans);
	return 0;
}