如何使用「构造函数法」去做Möbius反演

以前的反演都是瞎推一气直接硬推

昨天才了解到这个玩意可以构造函数搞。

那么怎么搞呢?

比如来个这个吧:

f\left( d \right) =\sum_{i=1}^n{\sum_{j=1}^m{\left[ \left( i,j \right) =d \right]}}

那么我们一般是:

f(n)= \sum_{i=1}^n{\sum_{j=1}^m{\left[ \left( i,j \right) =d \right]}}\ \left( n\geqslant m \right)

= \sum_{id=1}^n{\sum_{jd=1}^m{\left[ \left( i,j \right) =1 \right]}}

= \sum_{1\leqslant id\leqslant n}{\sum_{1\leqslant jd\leqslant m}{\sum_{g|id\ \&\ g|jd}{\mu \left( g \right)}}}

= \sum_{1\leqslant i\leqslant \frac{n}{d}}{\sum_{1\leqslant j\leqslant \frac{m}{d}}{\sum_{g|i,g|j}{\mu \left( g \right)}}}

= \sum_{1\leqslant g\leqslant \frac{m}{d}}{\mu \left( g \right) \lfloor \frac{n}{dg} \rfloor \lfloor \frac{m}{dg} \rfloor}

 

那么我们现在不这样做了,我们使用第二个反演式:

g\left( n \right) =\sum_{n|d}{f\left( d \right)}\,\,\Leftrightarrow \,\,f\left( n \right) =\sum_{n|d}{\mu \left( \frac{d}{n} \right) g\left( d \right)}

首先我们需要构造出一个上面所谓的 g(n) ,这里我们定义:

f\left( n \right) =\sum_{i=1}^A{\sum_{j=1}^B{\left[ \left( i,j \right) =n \right]}}

F\left( n \right) =\sum_{n|d}{f\left( d \right)}=\sum_{i=1}^A{\sum_{j=1}^B{\left[ n|\left( i,j \right) \right]}}=\sum_{i=1}^{\lfloor \frac{A}{n} \rfloor}{\sum_{j=1}^{\lfloor \frac{B}{n} \rfloor}{1}}=\lfloor \frac{A}{n} \rfloor \lfloor \frac{B}{n} \rfloor

然后呢,我们直接代进第二个反演柿子:

f\left( n \right) =\sum_{n|d}{\mu \left( \frac{d}{n} \right) F\left( d \right)}=\sum_{t=1}^{\chi}{\mu \left( t \right) F\left( nt \right)}=\sum_{t=1}^{\chi}{\mu \left( t \right) \lfloor \frac{A}{nt} \rfloor \lfloor \frac{B}{nt} \rfloor}

\left( t\xlongequal{\text{def}}\frac{d}{n},\chi \xlongequal{\text{def}}\min \left( \lfloor \frac{A}{n} \rfloor ,\lfloor \frac{B}{n} \rfloor \right) \right)

叮叮!做完啦!

闲的无聊随便写点| [CQOI2015]任务查询系统

主席树板儿

考虑把添加优先级为 k 的任务转化为在时间 \mathrm{st} 上加 k ,在时间 \mathrm{en}+1 上减 k

那么这样就成功维护了差分咯,然后每棵权值树单独地维护前缀和就行。

注意要离散化和排序。

06/06,应该是一轮集训 (之前) 做的题咯。

POI2008 Building blocks

主席树题。

首先我们考虑,这个问题就是区间上的中点问题。

\mathrm{cost} = \sum | \overline{x} - a_i |

然后事情就变得很简单了。

权值主席树 -> 区间第 \mathrm{k} 大可以求得中点。

注意考虑区间长度是偶数的问题。。这个我们去取平均值就好了。

求出来位置之后我们在主席树上走一遍,对于不包含中点的区间我们直接可以算出贡献,包含的递归进去算就好了。

 

一个小题目

这应该是某道题的弱化版。

题目就是给定一个正整数序列,长度 \leqslant 3 \times 10^5 ,然后值域是到 [1,10^9]

q 个询问 (q \leqslant 3 \times 10^5) ,每次呢给定一个数字 w (值域还是 [1,10^9] ),和区间 [l,r]

然后你可以把 w 异或上序列的 [l,r] 内的任意数字任意次。

要求最后的 w' 最小。

 

那么我们先来思考一个简单点的问题。如果是给定整个序列,那么我们可以预处理出序列的线性基

然后可以做到 O(\log_2 10^9) 内回答一个询问。

具体做法就是从高到低地,如果这一位非零,那就异或这一位的线性基然后继续下一位。

 

那么下面我们说一下线性基合并。线性基合并就是把其中一个线性基暴力地插入另一个线性基。

这样做的复杂度是 O(\log_2^2 10^9) 的。

那么我们可以用线段树/ST表等任意 \log 区间数据结构去维护线性基合并。

建议用ST表,这样预处理尽管带了三个 \log ,但是回答却是两个 \log 的,而且比线段树常数小。

 

可是有什么方法把整个算法也从三个变为两个 \log 呢?

分治!把回答离线,先递归处理掉左右两侧的回答,再处理跨中线的回答就好了。

每次返回的时候都合并一下。

 

那么还有一个相关的问题,和这种无关的。

把刚刚的问题修改一下,我们只能选择区间内的任意数字然后异或一次。

oh!可持久化Trie!

每次递归地往下走就好了。

非常好写。

从特殊的图论模型谈开去

最近停课集训算是让我短时间内也接触了不少图论模型,再加上之前的,够我写一篇文了。

在这篇里面我并不想谈关于 弦图,区间图,PQTree,完美消除序列 以及那篇文留下的几个大坑,我想从几个比较常用的和比较具有启发性的小玩意说起。

 

 

 

 

 

 

 

 

斯坦纳树

我是在做 [JLOI2015]管道连接 的时候学习到 Steiner Tree Problem 的。这个东西是什么呢?

我们看一下背景……


背景

Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a number of settings, they all require an optimal interconnect for a given set of objects and a predefined objective function. One well-known variant, which is often used synonymously with the term Steiner tree problem, is the Steiner tree problem in graphs. Given an undirected graph with non-negative edge weights and a subset of vertices, usually referred to as terminals, the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals (but may include additional vertices). Further well-known variants are the Euclidean Steiner tree problem and the rectilinear minimum Steiner tree problem.


斯坦纳树问题 (STP) , 或者说最小斯坦纳树问题, 是一类 组合优化 问题的统称, 那么尽管这个问题可能被设定到许多环境中, 但它都是一类要求: 对于给定的一个对象集合和一个预先定义好的作用于对象的函数, 求出集合的最佳互联的问题.

我们常用的 Steiner Tree Problem 的一个同义指的是在上的 STP . 也就是给定一个非负权边的无向图 和一个顶点的子集 ( 这些给定的顶点通常被称为 terminals ) , 那么我们要求一个把 terminals 联通的最小权生成树. (虽然这个生成树可以有非 terminal 结点).

还有一些奇怪的变种比如 Euclidean Steiner tree problem 和 rectilinear minimum Steiner tree problem.

(这个翻译我真的尽力了.)(我再翻译一些)

这个问题可以说是(非负权的)最短路问题和 MST 问题的组合. 那么如果只有两个 terminals , 它显然是一个最短路问题. 如果所有的结点都是 terminals , 它则是一个 MST 问题.

虽然最短路问题和 MST 问题都是 P 问题, 他们的好哥们 Steiner Tree Problem 却是一个 NPC 问题! 但是虽然大多数 STP 都是 NP-hard 的, 但在某些限制条件下它可以在多项式时间内解决.


PollakGilber猜想

Pollak-Gilbert 猜想指出,平面上任意 n 点集,斯坦纳最小树长与最小生成树之长的比值的最小值是 \frac{\sqrt{3}}{2}


求解问题

子集DP。把 j 的二进制各位的 0/1 看做集合中各个元素选/不选,那么可以设计状态 dp[i][j] 来表示以 i 作为根, 并且集合选择状态为 j 的情况下的最优解答。

转移分两步:

  • 先通过对 j 进行划分求得对于 i,j 下的最优解。
  • 再通过 i,j 去优化 j 下的其他根的答案。

为什么只优化 j 下的呢?因为其他联通状态会转移到 j 或由 j 转移得到。

第一种转移:

除了枚举子集去更新之外,不要忘记要把有效状态放入队列。

第二种转移:


复杂度分析

我们枚举子集的复杂度应是 n \times \sum (C_k^i \times 2^i) = n \times 3^k

那个 SPFA 的复杂度是 n \times 2^k

那么就是 O(n \times 3^k)


流程回顾


Advanced: 斯坦纳森林问题

并没有多大难度。

考虑这样一件事情:我们给定并非一组 terminals ,我们给定 k 组。

对于这 k 组 terminals ,我们只要求同组中的是互相联通的。求一个生成树的最小花费方案。

那么我们可以这样:

我们枚举一个状态 w , 然后我们把 w 二进制拆分对应的几个集合中的 terminals 看成一组 terminals 。然后去做 STP。

然后我们求全集的答案就是再次子集DP一遍:

就很简单做完了。


图的遍历问题

这个问题比较有来头,他牵涉到了图论的起源(或者说创生?)

背景是著名的所谓 Könisberg seven bridge problem ,相信大家都已经耳熟能详了。

由此我们诞生了 Euler 回路或者说, Euler 环游问题。

那么现在我们来看另一个更难的问题: the Chinese Postman Problem (CPP)

(注:下文顶点和结点混用,但其实是一回事,vertex or vertice)

 

一些记号

环游就是从结点 v_0 出发最终回到 v_0 的一个有序路径。

在一个无向正权图上,经过每条边至少一次的环游的权是经过边的权值与次数的乘积的和。

即: v_0e_1,v_1e_2,\cdots ,e_nv_0 的权为 \sum_{i=1}^{n} w_{e_i}

图的最优环游就是该图的最小权的环游。

 

问题描述

那么这个问题是这样被描述的:

给定一个无向正权联通图,求出最优环游。

 

求解

第一,如果图是一个 Euler 图,那么显然任意一个 Euler 环游都是一个最优环游。

第二:非 Euler 图

把这个图记为 G

我们使用一种方法就是重复边法,说白了很简单,我们先假设答案已经求得,我们先规定每条边只能经过一次,然后把答案中重复的边拆成多条边,在原图上画出。

记这个新图为 G' ,这个 G' 显然是一个 Euler 图。

那么我们的任务就是构造出这样一个 Euler 图 G' 并且让它添加的边(称为重复边)的边权总和 W 最小。

 

Edmonds-Johnson 算法

case 1: G 正好有两个奇次(度)顶点

记这两个顶点为 S,T ,跑最短路即可。

case 2: G2n 个奇次顶点

我们使用 Edmonds 最小对集算法

思想:就是把 case 1 推广到了多组顶点上。

先用随便什么方法求出所有奇次顶点之间的最短路。 (Floyd or Dijkstra)

然后以这些奇次顶点为点集,做一个完全图,边权是两点间最短路。该图记为 G_1

我们跑带花树求出 G_1 的最小权完美匹配。(取负跑最大权完美匹配)

然后就做完了。

case 3:其余情况无解

 

注: 带花树写的只要不丑,差不多110行多点(含头文件IO等)。

注:我不会写。


2-SAT问题

缓更,但今晚肯定会更。

 

 

JLOI2016 毒瘤题解

这玩意就是我在上一篇里面记错的那个树形DP

我复制一下……

就一树形DP裸题。

设计状态 f[i][j] 表示在点 i 上,子树前 j 层未覆盖的最小答案。

然后 g[i][j] 表示子树全部覆盖完毕,又多往上覆盖了 j 层的答案。

然后转移就是了。注意最后更新要扫两遍。

为啥要倒着一遍啊?

不要脸的抄的学长的代码QAQ

把圆的左右端的点离散下来做扫描线。

用set维护。如果当前点的父亲是一个左半拉圆,那么当前层次要 +1

如果父亲是右半拉圆,就是和父亲是一样的。

注意要在正确的时机正确地删除元素。

还有注意比较的时候。

贪心+KMP

先枚举覆盖顺序,然后讨论一下:

当前的这一个子串放哪儿。

下一个和这一个相交不相交。

最大:第一个要尽量向前放。尽量不相交。相交最长。

最小:尽量相交,相交最短。不放这个位置去放下个位置就是个子问题,可以记搜。

组合数美滋滋。

首先DP。设 dp[i][j] 表示 前 i 门科目,有 j 个人被碾压的方案数。

然后 DP 的转移就是乘乘组合数。

\mathrm{dp[i][j]}= \sum_{k=j}^{n} \mathrm{dp[i-1][k]} \cdot C_k^{k-j} \cdot C_{n-k}^{rk-1-(k-j)}

最后每个 dp[i][k] 都要乘一个东西:成绩的合法分配方案。

那么就是乘这个:

d_i=\sum_{k=1}^{U_i}k^{n-rk} \cdot (U_i-k)^{rk-1}

(不超过)n次多项式,取点插值就行了。

容斥。别忘了正方形可以斜着放。

总方案是

\sum_{i=1}^{\min(n,m)}(i \times (n-i+1) \times (m-i+1)) \mod p

然后枚举两个点就可以算出 2, 3, 4 个点不可行的方案。

然后一个点不可行的方案很麻烦,

我们按照点把坐标系分三部分,然后有左面的宽 l ,右面的是 r ,高是 h

然后计算方案。

如果 h \leqslant \min (l,r) 那么比较好算。

如果不呢?减去 h-\min(l,r) 的部分!

公式见下,建议自己推导。

然后就基本上做完啦!

可以用 map 缩短代码。

到此为止就屠龙啦!

[今天颓死了]JLOI2015题解

其实是补昨天的坑。。。

今天颓死了。。。啥都没写 基本没学会多少东西 题也想不出来。。

成天看题解写代码 看题解调试。。。。。。。。

各种事。。还有CCPC。。

烦死了。。。。。

 

艹 我今天怎么也要做完三道题。

看题解对着写代码这毛病能把我送退役。。这毛病怎么也得改。。。

 

……[咕咕咕咕]挣扎两天半后的更新

 

行了,说正事


 

 

左偏树模板。

首先每个结点都来一颗左偏树。

然后你直接DFS,去合并左偏树并更新答案。

每个结点pop()完之后合并到父节点。

注意下放标记的顺序和时机。

就一树形DP裸题。

设计状态 f[i][j] 表示在点 i 上,子树前 j 层未覆盖的最小答案。

然后 g[i][j] 表示子树全部覆盖完毕,又多往上覆盖了 j 层的答案。

然后转移就是了。注意最后更新要扫两遍。

 

woc……记错题目了?尴尬。。。

这好像是另外一题的??

那么,我看一下题面

 

哦,这里我们首先可以发现对于每个叶子,他只对所在的链有影响

然后考虑爆搜,每次搜到底搜一条链,然后非叶结点可以:

枚举左边有多少参战。枚举右边。

记搜一下。

完了。。送分。。。

名字和题面毫无关系之 (1)

求某个式子 \lfloor ( \frac {b+\sqrt{d}} {2} ) ^{n} \rfloor \mod p

那你发现这玩意儿是无理数。。没法算

我们考虑这样

我们求这个:

\lfloor [ ( \frac{b+\sqrt{d}}{2} )^{n} + (\frac{b-\sqrt{d}}{2})^{n} ] - (\frac{b-\sqrt{d}}{2})^{n} \rfloor

然后去观察左边的柿子,发现:

我们可以构造一个方程: x^2-bx+\frac{b^2-d}{4}=0 。

为啥?这玩意儿两解是: x_1=\frac{b+\sqrt{d}}{2} \,,\, x_2=\frac{b-\sqrt{d}}{2}

然后呢?

(\frac{b+\sqrt{d}}{2} )^{n} + (\frac{b-\sqrt{d}}{2})^{n} = x_1^n + x_2^n

变形!

F(n) = x_1^n+x_2^n = (x_1+x_2)(x_1^{n-1}+x_2^{n-1}) - x_1x_2(x_1^{n-2}+x_2^{n-2})

然后用这个:

x_1+x_2 = -\frac{b}{c} \,,\, x_1x_2 = \frac{a}{c}

得出:

F(n)=-\frac{b}{c}F(n-1) - \frac{a}{c}F(n-2)

然后就可以快乐的矩乘啦!

后面的那个怎么搞?

我们有个结论!看:

\because b^2 \leqslant d < (b+1)^2

\therefore b \leqslant \sqrt{d} < b+1

\therefore \frac{b-\sqrt{d}}{2} \in (-1,0]

那么只有 n 为奇数并且 \sqrt{d} \ne b 的时候,这一部分对答案是有 -1 的贡献的。

注意快速乘 , ull 。

斯坦纳树问题:斯坦纳森林(子集DP套子集DP)

首先我们发现,如果去掉频道这个玩意,这就是个裸的最小斯坦纳树问题

(Minimal – Steiner – Tree Problem , MST)

那么我们对每个频道分别做斯坦纳树。这玩意就一个子集DP,不会的可以找找板子看一下。

SPFA更新状态真的绝了。

 

那么做完每个点的MST-Problem,我们做子集的。

先离散化一下频道编号。。这个无所谓的。。细节问题。

 

你就把频道作为集合直接暴力枚举子集。然后把子集内的频道的斯坦纳点都初始化一下(其他全给个 \infty )然后跑斯坦纳树。

 

然后最后合并答案。斯坦纳森林,第一次见,还挺好玩的。

线性基。求一个权值和最小的线性无关组,使得可以线性表出所有给定向量。

那么我们直接排序贪心+线性基就完事了。。

高消版线性基。

这套题让我至少学了三个板子。

看好,这道题能让我达成史上最长题解之一。。。。

首先转化问题:

打死我也想不到这么转化

你可以找一下关系,然后连一下边,然后你会发现,答案等价为:

就这个图,然后从原点走到菱形点,信息都标好了。

答案是不跨越这两条对角中任一条的情况。

那么我们做辅助线 A \,,\, B

然后就是变为全部方案减去触碰 AB 的情况。

那么我们假设不合法的方案记为类似 AAABABABBBAAB 这样的方式。这个表示方法就是记录了一下跨越顺序。

相同的字母可以缩成一个,这样不会算重复。

那么:

我们令初始点为那个方点,然后我们做这样的操作:

将当前点沿直线A翻转,然后把原点到当前点的方案数从答案中扣除;

将当前点(注意此时已经翻转过了)沿直线B翻转,然后把原点到当前点的方案数从答案中加回来;

反复如此直到某一坐标 <0

因为此时无论如何进行下去方案数都是 0 了 。

这样做相当于把以 AAB 为后缀的方案删除,然后把以 BABAB 为后缀的方案加回去,然后把以 ABAABAB 为后缀的方案删除……

好妙啊!

然后我们先沿 B 翻转再做一次,就删掉了以 B 为前缀的所有方案 。

好妙啊好妙啊!!!!!

呼,写完啦!去补2016的。

[莫名其妙的]二项式反演

\text{第一反演公式}

\text{设}n\in \mathbb{N}_+\,\,,\text{多项式序列}\left\{ p_n \right\} ,\left\{ q_n \right\} \text{有如下关系:}

p_n\left( x \right) =\sum_{k=0}^n{\alpha _{nk}q_k\left( x \right) \,\,},\,\,q_n\left( x \right) =\sum_{k=0}^n{\beta _{nk}p_k\left( x \right)}

\text{且}A=\left( \alpha _{ij} \right) ,B=\left( \beta _{ij} \right) \text{为非奇异矩阵},\,\text{则有}

v_n=\sum_{k=0}^n{\alpha _{nk}u_k}\Leftrightarrow u_n=\sum_{k=0}^n{\beta _{nk}v_k}

 

 

Proof.

\text{令}p=\left( p_0,p_1,\cdots ,p_n \right) ^T,q=\left( q_0,q_1,\cdots ,q_n \right) ^T

u=\left( u_0,u_1,\cdots ,u_n \right) ^T,v=\left( v_0,v_1,\cdots ,v_n \right) ^T

\text{则可将原式表示为}

p=Aq\,\,,\,\,q=Bp

\therefore p=Aq=ABp.

\because p\text{是线性空间}R\left[ x \right] \text{的一组基}

\therefore AB=I,\,\,A^{-1}=B

\therefore v=Au\Leftrightarrow u=A^{-1}v=Bv\,\,\,\,\blacksquare

 

 

\text{二项式反演}

\text{设}\left\{ a_n \right\} \text{和}\left\{ b_n \right\} \text{是两个数列}

a_n=\sum_{k=0}^n{\left( \begin{array}{c}n\\k\end{array} \right) b_k}\Leftrightarrow b_n=\sum_{k=0}^n{\left( -1 \right) ^{n-k}\left( \begin{array}{c}n\\k\end{array} \right) a_k}

 

 

Proof.

x^n=\left( 1+x-1 \right) ^n=\sum_{k=0}^n{\left( \begin{array}{c}n\\k\end{array} \right) \left( x-1 \right) ^k}

\left( x-1 \right) ^n=\sum_{k=0}^n{\left( -1 \right) ^{n-k}\left( \begin{array}{c}n\\k\end{array} \right) x^k}

\text{由第一反演公式可得证}

[Zzz]趁着不太清醒赶紧把题解补完 | JLOI2014

[JLOI2014]天天酷跑

某优雅的DP题。

dp[i][j][k]表示在位置 (i,j) 并且用了 k 次连跳的答案。

转移分三种:一是如果 j=0 也就是在地面那可以跑一格

或者 k<q 可以跳一下

或者如果可以的话,下落。

可以枚举跳跃高度和次数然后记搜。

[JLOI2014]松鼠的新家

年代久远了。如果我没记错应该是一个树上差分问题。

好像是什么树上差分的板子……随便写写。

这是我元旦那天做的第一题,或者也可以说18年第一道题。

[JLOI2014]路径规划

这题劲啊!这题可劲了

考虑对 k 也就是过红绿灯的次数分层。

然后还是不好搞,没有办法之后我们可以分第二层。

k 分层之后,对于每一层,枚举所有加油站,计算出这个加油站 i 分别到 所有层 的 所有加油站 的最短路。

然后这样建新图,直接在加油站-加油站之间连边。然后跑对于 k 的分层图最短路。

SPFA 不会被卡。

期望等待长度是 \frac{R^2}{2 \cdot (R+G)}