Category: 生成函数

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3028
神犇题解：http://blog.csdn.net/regina8023/article/details/44995939

解题报告

这题看上去一眼不可做啊！第一反应：还要写高精？
但想一想似乎物品非常妙妙：

我们强行将其分为四组：{汉堡，可乐} {蜜桃多，土豆片炒肉} {包子，鸡块} {鸡腿，面包}
我们发现每一组都能凑出每一个自然数，且方案唯一
于是问题变为将$n$个球分为$4$组，每组可以为空的方案数

这是插板法的经典问题，于是搞一个组合数就可以了
什么组合数太大？
我们注意到答案实际是$\frac{n^{\bar 3}}{6}$，所以我们取个模就可以了

当然你也可以强行搞生成函数然后泰勒展开得到一样的结论
但我不会泰勒展开 QwQ

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 10007;
const int REV = 1668;

int main() {
	int n=0; char pat[600]; cin>>pat+1;
	for (int i=1;i<=strlen(pat+1);i++)
		n = (n * 10 + pat[i] - '0') % MOD;
	cout<<n*(n+1ll)*(n+2)*REV%MOD;
	return 0;
}

相关链接

题目传送门：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;
}