看到akb在冬令营就切了好多点分治就好慌啊qaq,然后机房里也有一堆人写点分治qaq,然后我就被点分治虐了啊qaq……

树上的点分治是一种针对树上路径统计的问题的算法,通过找到重心使得子问题规模快速下降,再将所有子问题答案合并起来,通常能够将\(O(n ^ 2)\)规模的问题优化为\(O(n \log n)\)或者\(O(n \log ^ 2 n)\)。

先看一道题:
给定一颗\(n \leq 10 ^ 5\)个节点的带权无根树,设\((i, j)\)之间的简单路径边数为\(dis(i, j)\),求所有满足\(dis(i, j) \leq K\)且\(i \lt j\)的数对\((i, j)\)的数量。(CWOJ1201

暴力做法显然,从每个节点开始dfs (bfs是等价的,后文dfs均可以用bfs解决),记录答案即可。时间复杂度为\(O(n ^ 2)\)

但是这样太慢了!我们想要更快的做法。

Continue reading

2017.2.3

提前inf分钟被叫起床,到地铁站都还要等地铁首班车,之后死在飞机场。离线了一场cf,被A题血虐,直到降落收电脑才意识到自己的sb,下飞机一分钟写完。

绍一条件很资磁呀,饭很好吃学校也很有味道,还比较自由,提供的除了洗澡不便利其他都好。

下午颓废。本来准备好好打打cfvp的。结果tm迷之excited然后啥事没干。见了ZYQN,zms等众犇。吃完晚饭前和t123yh, ZYQN出去买了根网线来续wifi。

开幕式表演光污染严重,射灯亮多炸,表演包括主场嗨的不行,t123yh刚说完“他们声音太小了”之后就马上威震全场的乐队,还有不知道有多少版本的“掀起你的女装来”等等。然后就是各级领导开始吹嘘,听着挺尬的。

然后就是我们亲爱的CCF ONI(误)dzd主席辣!出场掌声30+1s!

王小川!搜狗CEO!杰出企业家!
去年我们的NOI P! 参加人数变多……
noi是坠吼的!
ccf很公正!把权力关在笼子里!
贪污20个手办!(雾)
……

(More : 如何评价杜子德在NOI2017WC上的讲话?)

回寝室颓废。下去和ruanx面了面基顺便决定给tyh先生众筹女装!(逃
没买三国杀,强行抱着电脑开黑坑杀路人233

寝室不断电!资磁!然而HK_Journalist因为506光猫炸了而炸了qaq……

决定填任务和坑然后滚到现在,准备睡啦。

2017.2.4

早上迷之最后一个起床,早餐仍然非常资磁。

上午鏼鏼鏼讲字符串,喜欢鏼鏼鏼但字符串我真的菜啊qaq于是划水。

午饭非常资磁。中午将HK_Journalist放到406提高了上网水平。

下午猜数游戏好棒!不是lyp给我们才做过打表题么!挺有意思的,噪音中的通信也蛮有意思的(虽然量化熵之后太菜Zzz了……

然后小火车为我们讲了IOI练习赛以及比赛题,讲得非常有意思然后发现国外OI类型的题比垃圾国内OI题不知道高到哪里去了,希望国内科技发达后与国际接轨不然还是只能数据结构满天飞。不过很遗憾没能看到小火车直播学习(雾晚饭继续资磁,晚上开始下雨地上滑的不行差点摔死在这里。

毛爷爷讲了些听不懂的大新闻还强行D人qaq,敦爷神奇字符串,wlp仙人掌计数!于是可以预料的是我们全部被强制离线了。于是开始做atcoder比赛,然而因为太智障连C sb题都调到半夜,结果是特么

if (n == 2) return puts(a[1] == a[2] ? "YES" : "NO")/*, 0*/;

导致了迷之RE跪了一个半小时?excuse me?

然后bzoj某题卡我莫队毁我青春。睡啦。


2017.2.5

早上起晚了刚好错过早饭,不过还好啦自备有吃的。

上午PhOI?我只会玩不会算啊qaq……我需要提高自己的几何与微积分水平才能全程在线,然而我的这俩都是几乎为0 qaq……然而因为是近似数值计算,讲到近似结果的稳定还是蛮有意思的。另外视频好评,(膜李)模拟水好评!

午饭一如既往,然而我觉得我增重了好多qaq……因为神奇的原因没洗成澡。

下午,dls的可并行/分布式竞赛简直excited,用并行和通信解决问题感觉很有意思,但是真的好难啊qaq,简单题都能因为限制成为需要好好研究性质的难题。后半程Zzz了,并调了一道神构造的div1 C没调出来,后来才发现随机丑了。

晚上先是线性代数解决一般图匹配,虽然隔着厚厚的线代屏障还有巨大的常数但是能感觉到这个东西是极其有用的(然而uoj上被卡随机hack掉了233),然后那两位自称猫的大爷上来讲了仙人掌与圆方树——好吧,虽然看id知道两位都是神犇,但你们讲课的时候完全是在自嗨好嘛!从断线到放弃重连。

回寝颓废,500ping+丢包强行屁股五连胜,随缘得人心。HK_Journalist在换了电源后终于稳定一些了。lxl大爷太强啦,随口ak了我查了题解都差点没看懂的div1B。然后bzoj 400题了。


2017.2.6

上午课是什么辣鸡PKU教授来花了一个上午嘲讽OIers并且讲了去年WC近似算法的不到10%。第一次觉得第一课堂比第二课堂无聊,拿出耳机打vp。对PKU好感降到比较低啊。

下午是毕姥爷的整数和多项式呀。qaqqaqaq真的不是我想掉线啊但是真的因为数学太菜强制离线了呀……求毕姥爷不d QAQ……

晚上上机练习。鸡去把NOI Linux用dirty cow给hack了获取了root权限(然后被毕姥爷狂d 哈哈哈哈哈……然后回寝室三国杀,哼他们明明就是在恶意破坏极个别玩家的游戏体验……

半夜发生了点奇怪的事情导致我到了睡觉又起床又睡着又起床才更新这个。


2017.2.7

上午卡常。虽然挺感兴趣的并且逼格很高,但是其实讲义已经涵盖了所有内容。还是略困。

下午先是挺帅的董先生讲线代。虽然他讲得很好并且很努力地来讲懂我们,然而我太菜了qaq于是离线。然后又是吉司机发车。简直是开车,压缩编码很有趣并且因为他的奖品是wallpaper engine导致忍不住剁了手买了一个非常excited。

晚上复(yu)习(xi)了一点树剖,fft,左偏树,splay还有对拍程序和vimrc。

RP++.


2017.2.8

……

这tm就是说的要考的卡常?

服气。

行吧反正我菜连排序都不会桶排。

T1:诶不是暴力40分嘛,资磁骗分……

T2:wori怎么一个都不会呀……艹那就骗完弃疗吧。然后最后发现自己是连桶排都不会的菜鸡。

T3:第一个点可做啊,然后是不该随机化一发啊……不会随机化那就写最sb的/(n^2/)排序网络啊居然骗了13分,然后手玩出了第二个点第一分……

40 + 21 + 20 = 81。菜啊。等明天划线。

wys被d的好惨(虽然应该d,毕竟第二题放错了位置)。

然后YJQ退役了(UPD:假的)

世事无常。

心情变得悲观了呢。

晚上晚会,膜你抄好评,直播狼人杀好评。

今天比赛又没做,艹。


2016.2.9

上午去逛柯岩,其实就是石头而已,并且强行搭了一个鲁镇。感觉后人搭的没什么意思啊。路上买了只惨叫鸡,简直毒瘤。
中午做了一个可能改变我一生的决定,拒了PKU的省队一本的约。希望是正确的。
下午懒得去鲁迅故居了,在寝室颓废。
卡线WC Au,还是太菜了。

还有YJQ是假装退役!哼。花近高楼伤客心,假装退役杨进清(逃
离开了邵一。
晚上到了杭州后就分开了呢,鸡和吴去逛西湖了。学军新校区好强大啊!太豪华了感到害怕。
明天就THUWC考试了,希望能够有好一点的成绩吧。


2016.2.10

早上好冷啊,有一点点着凉。在开幕式前和凯爷玩了玩通讯题,虽然比较好玩但是好难啊QAQ……听xjb讲座,然后试机。Ubuntu16.04好评!调戏FAQ system也挺好玩的。
我: Is this FAQ system working?
某不知名的管理员: Wo cai yes
…….
垃圾试机题简直奇葩,反复提交猜答案啊。
下午是cls监考。cls好帅啊好帅啊!然后开考。卧槽第一题什么鬼,第二题什么鬼,只有提答可做啊……
然后两个小时写了第一题20分暴力并且和另一个暴力拍上,然后开始玩提答。发现提答数据迷之弱,12暴力3背包4567费用流,感觉都是满的啊。。。890因为姿势不好不会写退火就用费用流瞎调,估计没什么分。。。然后回头看二题发现暴力还能做,把暴力写完,骗了骗完全图,弃疗。
不知道结果怎么样了呢,等名单吧。
晚上打了打羽毛球,发现太久不运动真的不好。


2016.2.11

早上非常意外地进了面试,基本没什么准备,然后面试也是xjb扯,居然扯到我并不熟悉的机器学习又只能xjb扯,做了道sb题,感觉面试过程没什么太大的问题吧。

然后熊老带我和lsw去了西溪,那里还真的挺漂亮的。于是我们拍摄了鸡的游记,真的是鸡!






↑↑↑我们的红太阳神犇lsw

下午讲题。感觉不妙,那么多人A了第一题我估计没机会了。

然后就真没机会了,什么约也没有胸牌滚粗。

毕竟是自己太弱了有什么办法呢。

原来我与thu无条件一本只差一个LCT+泰勒展开。哎。

THUSC,将会不再重蹈覆辙。

晚上回到了成都,回了家,WC2017+THUWC2017完结了。

接下来的两个月可以决定我的生死了,相信我不会辜负上天给予我的一切。

斜率优化是将方程看起来非常可推的dp从\( O(n^2) \)优化至\( O(n) \)的优秀方法,这种优化是基于决策单调性的……………………

一句话:都是套路。

关于斜率优化的文章很多,而且我数学贼差QAQ(主要是懒),就直接指向一篇本校神犇HenryPigLi的斜率优化DP,虽然他推得有点乱但是还算能看。
然而他的文章还有一个好,就是底下给的题比其他blog都多,于是我觉得应该把solution发出来。Continue reading

异或(exlusive OR, XOR, \( \oplus \))是一种非常优美的逻辑/集合运算符。
数学上,对于两个取值为\(S = \{ 0,1 \} \)的量\( p, q \),异或被表示为$$
\begin{alignat}{1}
p \oplus q &=& (\lnot p \land q) &\lor& (p \land \lnot q) \\
&=& (p \lor q) &\land& (\lnot p \lor \lnot q) \\
&=& (p \lor q) &\land& \lnot (p \land q)
\end{alignat}
$$如果用Venn图来表示,就是这样:(From Wikipidia)

其实我们可以用更简洁的语言描述这个运算符$$
p \oplus q = [p \neq q]
$$或者$$
p \oplus q = (p + q) \mod 2
$$异或之所以优美,是因为这是一个满足以下性质的运算符:

Continue reading

本次停课会持续到4.8。
如果有幸考上省选,那么会延长到暑假。
如果有幸能拿到金牌,那么会就此告别高考。
祝我好运。

The game is on.
Let’s enjoy it.

莫比乌斯反演通常是利用莫比乌斯函数来简化一类逆向求函数的问题。
设\(F(n)\)与\(f(n)\)是定义在自然数集合上的两个数论函数,并且满足条件$$
F(n) = \sum_{d|n}f(d)
$$或者$$
F(n) = \sum_{n|d}f(d)
$$已知的\(F(n)\),求\(f(n)\)的表达式。

观察\(F(n)\)式:\(F(n)\)被\(F(xn)(x > 1)\)所包含。所以只需容斥就可以逐个求出\(f(n)\)。

但是这样太慢了!于是我们想加速这个过程。
我们希望,存在一个函数,使得\(F(n)\)可以直接被表示出来。

/*** UPD 2018.3.13

如何容斥呢?

我们以第一个函数举例子。

考虑每个约数对答案的贡献,比如 6:
6: +1, 首先 \(F(6)\) 一定要包含进答案;\((f(6)+f(3)+f(2)+f(1))\)
3: -1, 我们发现去掉 \(f(3)\) 只能删掉 \(F(3)\);(\(f(6)+f(2))\)
2: -1, 我们发现去掉 \(f(2)\) 只能删掉 \(F(2)\);(\(f(6)-f(1))\)
1: +1, 我们发现这个时候好像 \(f(1)\) 被删多了,所以加回来。

我们可以发现,这个过程是一个“奇消偶不消”的,也就是说,删去质数个数为奇数时为 -1,否则为 +1;
我们还可以发现,我们对于一个质数不会删第二次,比如对于 \(F(12)\), \(f(12) = F(12)-F(6)-F(4)+F(2)\),和 \(F(6)\) 几乎一样,而没有 \(F(3), F(1)\) 什么事,因为他们相比起 \(12\) 多删了一次 \(2\)。

这样,我们就得到了莫比乌斯函数。

***/

这里给出结论,有莫比乌斯反演公式$$
f(n) = \sum_{d|n} \mu(d) F(\frac nd)
$$或者$$
f(n) = \sum_{n|d} \mu(\frac dn) F(d)
$$其中,莫比乌斯函数\( \mu(n) \)即是我们所要的容斥函数,\( \mu(n) \)定义为$$ \mu(n)=
\begin{cases}
1 \ \quad \quad d = 1 \\
(-1)^k \ n = p_1 p_2 \ldots p_k ,p_i为互异的质数\\
0 \ \quad \quad else \\
\end{cases}
$$同时,\( \mu(n) \)还有几个性质:
(1)\( \mu(n) \)是积性函数,即对于互质的正整数\(a,b\)有$$ \mu(ab) = \mu(a) \mu(b) $$(2)对于任意正整数\(n\)有$$\sum_{d|n} \mu(d) = [n = 1]$$(3)对于任意正整数\(n\)有$$\sum_{d|n} \frac{\mu(d)}{d} = \frac{\varphi(n)}{n}$$这些性质都是可以证明的,详见最后。
利用莫比乌斯函数的第二个性质,可以证明第一个莫比乌斯反演公式:$$
\begin{align*}
f(n) &= \sum_{d’|n}[d’=1]f(\frac N{d’}) \\
&= \sum_{d’|n}f(\frac n{d’}) \sum_{d|d’} \mu(d) \\
&= \sum_{d|n} \mu(d) \sum_{k | \frac n d} f(\frac n {dk}) \\
&= \sum_{d|n} \mu(d) F(\frac n d)
\end{align*}
$$类似的可以证明第二个公式。
当然,因为我们用到了函数的性质,这给人一种钦定的感觉。所以我找到一篇文章完整讲了莫比乌斯函数的朴素证明和构造性证明: http://blog.csdn.net/danliwoo/article/details/51866867

求莫比乌斯函数的话,可以利用莫比乌斯函数的定义在\(O(\sqrt{n})\)的时间内通过分解质因数的方法得到任意\( \mu(n) \)的值:

int mu(int x) {
	int ret = 1;
	for (int i = 2, sqx = (int)sqrt(x); i <= sqx; i++) {
		if (x % i == 0) {
			ret = -ret;
			if ((x /= i) % i == 0) return 0;
			sqx = (int)sqrt(x);
		}
	}
	return ret;
}

也可以在\(O(n)\)的时间内通过线性筛法在筛素数的同时求得\( \mu(1 \ldots n) \)的值:

const int N = 1000000;
const int CNT = 78498;
int prime[CNT + 5], pcnt = 0, mu[N + 5];
bool vis[N + 5];
void linearSieve() {
	mu[1] = 1;
	for (int i = 2; i <= N; i++) {
		if (!vis[i]) prime[++pcnt] = i, mu[i] = -1;
		for (int j = 1; j <= pcnt && i * prime[j] <= N; j++) {
			vis[i * prime[j]] = 1;
			if (i % prime[j]) mu[i * prime[j]] = -mu[i];
			else {mu[i * prime[j]] = 0; break;}
		}
	}
}

首先先看一个并不需要莫比乌斯反演的问题,求$$
\sum_{a=1}^N \sum_{b=1}^N [\gcd(a,b) = 1], \ N \leq 10^7
$$我们发现这个式子后半部分和欧拉函数\( \varphi(n) \)的定义是类似的。因为数对\( (x,y) \)是有序的,所以当\( x \neq y \)时需要算两遍,注意到\( \gcd(x, x) = 1\)的充要条件是\( x = 1\),所以答案就是$$
\sum_{d = 1}^{N} 2\varphi(\lfloor \frac nd \rfloor) \ – 1
$$
那么再来看一个问题,求$$
\sum_{a=1}^N \sum_{b=1}^M [\gcd(a,b) = 1], \ N \leq \ M \leq 10^7
$$对于这道题就不能只用欧拉函数解决了,需要用莫比乌斯反演来解决。我们考虑定义\(F(n)\)与\(f(n)\),然后利用莫比乌斯反演公式来进行转换。
我们发现这样定义\(F(n)\)与\(f(n)\)比较友好:$$
f(n) = \sum_{i = 1}^N \sum_{j = 1}^M [\gcd(i,j)=n] \\
F(n) = \sum_{n|d} \sum_{i = 1}^N \sum_{j = 1}^M [\gcd(i,j)=d]
$$其中,\(f(1)\)就是我们要求的答案,\(F(d)\)就是统计所有\(a|d\)且\(b|d\)的合法的数对\( (a,b) \)的个数。那么就有$$
F(n) = \lfloor \frac Nn \rfloor \lfloor \frac Mn \rfloor
$$于是我们代入前面提到的第二种莫比乌斯反演公式得到$$
f(n) = \sum_{n|d} \mu(\frac dn) F(d) = \sum_{n|d} \mu(\frac dn) \lfloor \frac Nd \rfloor \lfloor \frac Md \rfloor
$$此时我们令\(n = 1\),有$$
f(1) = \sum_{d = 1}^N \mu(d) \lfloor \frac Nd \rfloor \lfloor \frac Md \rfloor
$$这个式子就是答案。

如果通过质因数的方法求\(\mu(1 \ldots N)\),时间复杂度为\(O(N \sqrt N)\),过不了;
如果线性筛预处理\(\mu(1 \ldots N)\),预处理\(O(N)\),查询\(O(N)\),已经能过了;

其实还有更快的查询方法。事实上\(\lfloor \frac Nd \rfloor \)的取值个数非常小(易证一定不大于\(2 \sqrt N \)),并且在\(d\)递增时,\(\lfloor \frac Nd \rfloor \)均是单调不升并且连续的,这意味着,\( \lfloor \frac Nd \rfloor \lfloor \frac Md \rfloor \)的取值对总数是\( O(\sqrt M) \)的!
所以我们可以在\(O(\sqrt M) \)的时间内完成一次查询,实现如下:

for (int i = 1, j; i <= n; i = j + 1) {
	j = min(n / (n / i), m / (m / i));
	ans += (long long)(sum_mu[j] - sum_mu[i - 1]) * (n / i) * (m / i);
}

差不多就这样辣……

用类似的方法,推出和式,有时再加一点其他的优化(比如杜教筛),就是莫比乌斯反演的套路了。
(然而不是莫比乌斯模板题我还是不会做QAQ)

这里有一个Po姐的PPT,写的非常棒,反正能看懂很多东西吧……
PoPoQQQ的良心PPT