相关链接
题目传送门：http://codeforces.com/problemset/problem/653/G
官方题解：http://codeforces.com/blog/entry/43886
数学推导参考：http://codeforces.com/blog/entry/43886?#comment-285657
中文题面：http://www.cnblogs.com/AOQNRMGYXLMV/p/5441441.html
生成函数的做法：http://www.cnblogs.com/AOQNRMGYXLMV/p/5441441.html
解题报告
不难发现质因数之间相互独立
于是我们就可以将每一个质因数单独考虑
这样问题转化为：
给定一个序列 {$ { {a_i}}$} ，每一次操作可以选一个数加一或者减一
问：将序列中所有数变为相同至少需要多少次操作
这个经典的问题，我们都知道全部变到中位数是较优的策略
但如何考虑每一个子序列？似乎没有比较优雅的方法…
于是我们换一个角度考虑：
设序列排序后为 {\({ {b_i}}\)}, 中位数为 $ {b_{mid}}$
那么这个序列的花费为 $ \sum\limits_{i = 1}^{mid – 1} {({b_{mid}} – {b_i})} + \sum\limits_{i = mid + 1}^n {({b_i} – {b_{mid}})}$
打开∑之后发现 $ {b_{mid}}$ 全部抵消掉了！
于是我们统计一个数有有多少次是加上或是减去就好啦！
考虑当前处理 $ {b_k}$ 这样的话，枚举有i个数比他小
那么有 $ i+1 \sim n-k$ 个数比他大的情况全部是减去
有 $ 0 \sim i-1$ 个数比他大的情况全部是加上
写出来就是 $ \sum\limits_{i = 0}^{{\rm{k – 1}}} {(\sum\limits_{j = {\rm{0}}}^{i – 1} {C_{n – k}^j} – \sum\limits_{j = i + 1}^{n – k} {C_{n – k}^j} )} \cdot {b_k}$
但这样计算的话，复杂度不对，于是再化简一下：
考虑选法1：左边选 $ l$ 个，右边选 $ r$ 个，$ r-l=x$
这样的话，我们总共选了 $ r+l$ 个数
考虑将右边选的数反选（方案间仍然一一对应），此时我们选择了 $ n-k-x$ 个数再考虑选法二：我们任选 $ n-k-x$ 个数
因为 $ r-l=x$， 所以一定可以构造出唯一一组 $ (l,r)$ 使得 $ l+r=n-k-x$于是我们就证明了上述两种选法存在一种一一对应的映射
换一句话来说，我们可以直接统计第二种选法的方案数 $ C_{n – 1}^{n – k – x}$ 即可
这样的话，答案就成了 $ (\sum\limits_{i = – 1}^{ – (k – 1)} {C_{n – 1}^{n – k – i} – \sum\limits_{i = 1}^{n – k} {C_{n – 1}^{n – k – i}} ) \cdot {b_k} = } (\sum\limits_{i = n – k + 1}^{n – 1} {C_{n – 1}^i – \sum\limits_{i = 0}^{n – k – 1} {C_{n – 1}^i} ) \cdot {b_k}}$
这样的话，我们处理一下组合数的前缀和就可以 $ O(n)$ 处理完每一个质因数了
又因为 $ {b_k}$ 的值域很小，于是再预处理一下组合数的前缀和的前缀和
就可以得到 $ O(nlog(n))$ 的复杂度辣！
当然上面数学推导那一块还可以用生成函数来推导
然而我不会 QwQ
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 300000+9;
const int L = 22;
const int MOD = 1000000007;
int n,tot,vout,pri[N],vis[N],sur[N],cnt[N][L];
int POW[N],REV[N],sum[N],pre1[N],pre2[N];
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
inline int C(int a, int b) {
if (a > b || a < 0 || b < 0) return 0;
else return ((LL)POW[b] * REV[a] % MOD) * REV[b-a] % MOD;
}
inline int pre_sum(int l, int r) {
if (l > r) return 0;
return (sum[r] - (l?sum[l-1]:0)) % MOD;
}
inline int Pow(int w, int t) {
int ret = 1;
while (t) {
if (t & 1) ret = (LL)ret * w % MOD;
w = (LL)w * w % MOD; t >>= 1;
}
return ret;
}
inline void prework() {
n = read(); sur[1] = 1;
for (int i=2;i<N;i++) {
if (!vis[i]) pri[++tot] = i, sur[i] = tot;
for (int j=1;j<=tot&&pri[j]*i<N;j++) {
vis[i*pri[j]] = 1;
sur[i*pri[j]] = j;
if (i % pri[j] == 0) break;
}
}
for (int i=1;i<=tot;i++)
cnt[i][0] = n;
POW[0] = REV[0] = 1;
for (int i=1;i<N;i++)
POW[i] = (LL)POW[i-1] * i % MOD;
REV[N-1] = Pow(POW[N-1], MOD-2);
for (int i=N-2;i;i--)
REV[i] = (LL)REV[i+1] * (i+1) % MOD;
sum[0] = 1;
for (int i=1;i<N;i++)
sum[i] = (sum[i-1] + C(i, n-1)) % MOD;
for (int i=1;i<=n;i++)
pre1[i] = (pre_sum(n-i+1, n-1) - pre_sum(0, n-i-1)) % MOD;
for (int i=1;i<=n;i++)
pre2[i] = (pre2[i-1] + pre1[i]) % MOD;
}
int main() {
prework();
for (int i=1,w;i<=n;i++) {
w = read();
for (int j=sur[w],tmp;w>1;j=sur[w]) {
for (tmp=0;w%pri[j]==0;tmp++,w/=pri[j]);
cnt[j][tmp]++;
cnt[j][0]--;
}
}
for (int i=1;i<=tot;i++) {
if (cnt[i][0] < n) {
for (int j=0,l=0,r=0;j<L;j++) {
if (cnt[i][j]) {
r += cnt[i][j];
(vout += (LL)(pre2[r] - pre2[l]) * j % MOD) %= MOD;
l = r;
}
}
}
}
printf("%d\n",(vout+MOD)%MOD);
return 0;
}
Hey! I know this is kinda off topic but I was wondering
which blog platform are you using for this website? I’m getting tired of WordPress because I’ve had issues
with hackers and I’m looking at options for
another platform. I would be awesome if you could point me in the direction of a good platform.
Undeniably imagine that that you stated. Your favourite reason appeared to be at the net the easiest factor to take
note of. I say to you, I certainly get annoyed while other people consider concerns that they plainly don’t understand about.
You managed to hit the nail upon the highest as neatly as defined out the whole
thing without having side effect , folks can take a signal.
Will probably be again to get more. Thanks
I love reading a post that will make people think. Also, many thanks for permitting me to comment!
I think everything said made a lot of sense. But, what
about this? what if you added a little content? I am not suggesting your content isn’t solid, but what if you added a post
title that grabbed a person’s attention? I mean 【Codeforces 653G】Move by Prime – Qizy's Database is a little plain. You
could glance at Yahoo’s front page and see how they write article headlines to grab people to click.
You might try adding a video or a picture or two to grab readers excited about everything’ve written. In my opinion, it would
bring your posts a little livelier.
It’s an amazing piece of writing for all the web
visitors; they will get advantage from it I am sure.
I enjoy what you guys are usually up too. This type of clever
work and exposure! Keep up the very good works
guys I’ve added you guys to blogroll.
Nice blog! Is your theme custom made or did you
download it from somewhere? A design like yours with a few simple adjustements would really
make my blog shine. Please let me know where you got your design. Appreciate it
Hey there, You have done a great job. I’ll definitely digg it and personally
suggest to my friends. I am confident they will
be benefited from this website.
Hello to every one, as I am genuinely keen of reading this website’s post to be updated regularly.
It carries fastidious information.
Nice weblog right here! Additionally your website a
lot up fast! What host are you using? Can I get your
associate link on your host? I want my website loaded up as fast as yours lol
Incredible quest there. What happened after?
Good luck!
Hi there, just became alert to your weblog through Google, and found that it is really informative. I’m going to be careful for brussels. I’ll be grateful for those who proceed this in future. Many other people shall be benefited from your writing. Cheers!
Hello, its fastidious article about media print, we all be aware of media is a impressive source of
information.
Hello! This post couldn’t be written any better!
Reading through this post reminds me of my previous room mate!
He always kept chatting about this. I will forward this article to him.
Pretty sure he will have a good read. Thank you for sharing!
Hey! Quick question that’s entirely off topic.
Do you know how to make your site mobile friendly?
My site looks weird when browsing from my apple iphone.
I’m trying to find a template or plugin that might
be able to fix this issue. If you have any recommendations, please share.
With thanks!
Hi! I’m at work surfing around your blog from my new apple
iphone! Just wanted to say I love reading through your blog and look forward to
all your posts! Carry on the great work!
Hi there, I think your site might be having web browser compatibility problems.
When I look at your web site in Safari, it looks fine
however when opening in Internet Explorer, it has some overlapping issues.
I just wanted to provide you with a quick heads
up! Apart from that, fantastic site!
Wow! This blog looks exactly like my old one! It’s on a entirely different subject but it has pretty much the same
page layout and design. Excellent choice of colors!
It’s amazing in favor of me to have a site, which is beneficial in support of my knowledge.
thanks admin
Aw, this was a very nice post. In thought I would like to put in writing like this additionally – taking time and actual effort to make a very good article… but what can I say… I procrastinate alot and on no account appear to get one thing done.