【BZOJ 3028】食物

相关链接

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

【BZOJ 4785】[ZJOI 2017] 树状数组

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4785
出题人传送门:http://jiruyi910387714.is-programmer.com/posts/209073.html
官方题解:https://pan.baidu.com/s/1dFGHFfr

解题报告

我们发现正常的代码是统计的前缀和
但劼的写法实际是统计后缀和
然后画一画发现,只有$l-1,r$这两个点被改到的时候才会影响答案

我们考虑询问区间是$[l,r]$,一个修改区间是$[a,b]$
那么如果$l,r \in [a,b]$则这个修改区间有$\frac{2}{b-a+1}$的可能影响到答案
如果$l,r$只有一个$\in [a,b]$那么这个修改区间有$\frac{1}{b-a+1}$的可能影响到答案
如果两个都不属于,其显然不会影响到答案

于是我们把修改操作看成二维平面上的点的话
每一个询问操作可以拆成三个矩阵的询问
这个是经典问题,可以用树套树/分治/K-d Tree来解决

至于怎么维护标记,直接做的话,我们可以看成矩阵乘法
因为这个转移矩阵非常特殊,搞一搞发现其不但满足结合律,还满足交换律,所以可以标记永久化
但还有更妙的做法:

我们可以搞一个类似生成函数的东西
设第$i$个操作有$p_i$的可能影响到当前询问,设两个端点被改变偶数次的概率为$a$,奇数次为$b$
那么最后$a-b=\prod\limits_{i}{(1-p_i)-p_i}$
为什么是对的呢?因为只有改变奇数次才会为奇数,而$-1$的奇数次方等于$-1$偶数次方等于$1$,所以刚好对上
又因为我们还知道$a+b=1$,所以$a = \frac{1+\prod\limits_{i}{(1-p_i)-p_i}}{2}$

另外的话,这题有一个坑点:如果$l-1=0$的话,我们需要特判
因为之前我们的推导基于$l-1$那个点记录的是一个后缀
而实际算法中我们我们默认$l-1$那个点的值为$0$,所以需要判断一下总操作次数奇偶
考试的时候就这一点没想到,血wa三小时,最后这题挂零

Code

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

const int N = 100009;
const int M = 30000000;
const int MOD = 998244353;
const int REV = 499122177;

inline int read() {
	char c=getchar(); int ret=0,f=1;
	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;
}

int n,m,tot;
class Segment_Tree{
	int cnt,root,AnsTmp,ch[M][2],prod[M][2];
	public:
		inline void modify(int x, int y, int v, bool t) {
			modify(root, 1, n, x, y, v, t);
		}
		inline int query(int x1, int x2, int y1, int y2, bool t) {
			if (x1 > x2 || y1 > y2) return 1;
			AnsTmp = 1;
			query(root, 1, n, x1, x2, y1, y2, t);
			return (AnsTmp+MOD)%MOD;
		}
	private:
		void modify(int &w, int l, int r, int x, int y, int v, bool t) { //X
			if (!w) w = ++cnt; modify(prod[w][0], 1, n, y, v, t);
			if (l < r) {
				int mid = l + r + 1 >> 1;
				if (x < mid) modify(ch[w][0], l, mid-1, x, y, v, t);
				else modify(ch[w][1], mid, r, x, y, v, t); 
			}
		}
		void modify(int &w, int l, int r, int p, int v, bool t) { //Y
			if (!w) w = ++cnt, prod[w][0] = prod[w][1] = 1; 
			prod[w][t] = (LL)prod[w][t] * v % MOD;
			if (l < r) {
				int mid = l + r + 1 >> 1;
				if (p < mid) modify(ch[w][0], l, mid-1, p, v, t);
				else modify(ch[w][1], mid, r, p, v, t);
			}
		}
		void query(int w, int l, int r, int L, int R, int y1, int y2, bool t) { //X
			if (!w) return;
			if (L <= l && r <= R) query(prod[w][0], 1, n, y1, y2, t);
			else {
				int mid = l + r + 1 >> 1;
				if (L < mid) query(ch[w][0], l, mid-1, L, R, y1, y2, t);
				if (mid <= R) query(ch[w][1], mid, r, L, R, y1, y2, t);
			}
		}
		void query(int w, int l, int r, int L, int R, bool t) { //Y
			if (!w) return;
			if (L <= l && r <= R) AnsTmp = (LL)AnsTmp * prod[w][t] % MOD;
			else {
				int mid = l + r + 1 >> 1;
				if (L < mid) query(ch[w][0], l, mid-1, L, R, t);
				if (mid <= R) query(ch[w][1], mid, r, L, R, t);
			}
		}
}SGT;

inline int Pow(int w, int t) {
	int ret = 1;
	for (;t;t>>=1,w=(LL)w*w%MOD)
		if (t&1) ret=(LL)ret*w%MOD;
	return ret;
}

int main() {
	n = read(); m = read();
	for (int i=1,l,r,len,ret;i<=m;i++) {
		if (read() == 1) {
			l = read(); r = read(); 
			len = Pow(r-l+1, MOD-2); ++tot;
			SGT.modify(l, r, (1 - (len * 2ll)) % MOD, 0);
			SGT.modify(l, r, (1 - (len * 4ll)) % MOD, 1);
		} else {
			l = read() - 1; r = read(); ret = 1;
			ret = (LL)ret * SGT.query(1, l, l, r - 1, 0) % MOD;
			ret = (LL)ret * SGT.query(l+1, r, r, n, 0) % MOD;
			ret = (LL)ret * SGT.query(1, l, r, n, 1) % MOD;
			ret = (ret + 1ll) * REV % MOD;
			if (!l&&(tot&1)) ret = (1 - ret) % MOD; 
			printf("%d\n",(ret+MOD)%MOD);
		}
	}
	return 0;
}

【Codeforces 653G】Move by Prime

相关链接

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

【BZOJ 4115】[WF2015] Tile Cutting

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4115
神犇题解:http://www.cnblogs.com/clrs97/p/4779789.html
英文题面:https://online.acmicpc.org/problems/tiles
英文题解:http://blog.brucemerry.org.za/2015/05/analysis-of-icpc-2015-world-finals.html

解题报告

卧槽,这样乱找题做吃枣药丸啊!
一言不合就FFT+生成函数,FFT还好,生成函数完全不会啊 QwQ
只能先弃坑了,以后慢慢来填 _ (:з」∠) _

—– UPD 2017.1.22 —–
最近听集训队神犇讲了生成函数
然而并没有学会 QwQ
不过做这个题还是足够啦!

考虑最终的切法长这样:

那么平行四边形的面积就是 $ad+bc$
设面积为$i$的答案为 $ans(i)$,$x$ 的约数个数为 $d(x)$
那么就可以得到: $ans(i) = \sum {[ad + bc = i]} = \sum {[x + y = i]} \cdot d(x) \cdot d(y)$
然后看一眼就能发现这货是个卷积的形式,于是搞一波FFT就可以啦!