Miskcoo's Space

反演魔术:反演原理及二项式反演

首先我来说说什么是反演(inversion),对于一个数列$\{f_n\}$来说,如果我们知道另外一个数列$\{g_n\}$,满足如下条件 \[ g_n = \sum_{i=0}^n a_{ni}f_i \] 反演过程就是利用 $g_0, g_1, \cdots, g_n$ 来表示出 $f_n$ \[ f_n = \sum_{i = 0}^n b_{ni}g_i \] 本质上来说,反演其实是...

Catalan 数列及其应用

卡特兰数(Catalan number)是组合数学中一个重要的计数数列,在很多看似毫不相关地方都能见到它的身影 这篇文章介绍卡特兰数的几个应用以及它的推导过程,从组合推理和生成函数两个方面来推导出 Catalan 数的公式 带限制条件的路径总数 首先我们来看一个问题: 在一个平面直角坐标系中,只能往右或往上走一个单位长度,问有多少种不同的路径可以从左下角 $(1, 1)$ 走到右上角 $...

Codeforces 上的一些组合计数问题

Codeforces 15E. Triangles Problem:给出一个有规律的金字塔(如图),黑色的边是可以走路径,要求求出包含 $H$ 点的简单回路(不经过一个顶点两次)的条数,并且这个回路围住的部分不可以包含灰色的三角形,答案对 $10^9+9$ 取模,其中 $n \leq 10^6$,并且一定是一个偶数 Example:当 $n = 2$ 时,一共有 $10$ 种方案,其中...

牛顿迭代法在多项式运算的应用

总算是快把 FFT 和生成函数的各种东西补了好多,膜拜策爷的论文和 Picks 的博客 QAQ 这篇文章大概就是说如何用牛顿迭代法来解满足 $G(F(z)) \equiv 0 \pmod {z^n}$ 的 $F(z)$ 然后这东西可以比较方便地计算 $\sqrt{A(z)}$、$e^{A(z)}$,也就是多项式开根、求指数对数之类鬼畜的东西,在生成函数计数中十分有用 顺便一提,这里说的...

平面图转对偶图及点定位

平面图(planar graph)就是一个可以在平面上画出来的图,并且所有的边只在顶点处相交。平面图的对偶图(dual graph)是将这个平面的每个区域看成点,原图每一条边所属的两个相邻的区域对应在对偶图中的点有连边 比如下面这张图(来源于 Wikipedia) 蓝色的部分就是一个平面图,红色的就是它的对偶图 平面图的点定位(point location)就是找出一个点属于这个图...

BZOJ-3456. 城市规划

题目要求求出有 $n (n \leq 130000)$ 个点的有标号简单连通无向图的个数,答案 $\bmod 1004535809$ $(479 \times 2^{21} + 1)$,是个质数 比如三个点的情况 题目链接:BZOJ-3456 首先可以设 $f(n)$ 表示有 $n$ 个点的有标号简单连通无向图的个数,$g(n)$ 表示有 $n$ 个点的有标号简单无向图的个数(...

多项式的多点求值与快速插值

多项式的多点求值(multi-point evaluation)是给出一个多项式 $A(x)$,和 $n$ 个点 $x_0, x_1, \cdots, x_{n-1}$,要求求出 $A(x_0), A(x_1), \cdots, A(x_{n-1})$ 相反的,多项式的插值(interpolation)是给出 $n+1$ 个点 $(x_0, y_0), (x_1, y_1), \cdots...

BZOJ-3435. [Wc2014]紫荆花之恋

强强和萌萌是一对好朋友。有一天他们在外面闲逛,突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了,无数的花瓣以肉眼可见的速度从紫荆树上长了出来。 仔细看看的话,这个大树实际上是一个带权树。每个时刻它会长出一个新的叶子节点,每个节点上有一个可爱的小精灵,新长出的节点上也会同时出现一个新的小精灵。小精灵是很萌但是也很脆弱的生物,每个小精灵 $i$ 都有一个感受能力值 $r_i$,小精灵 $i...

多项式求除法及求模

问题是这样的:给定一个 $n$ 次多项式 $A(x)$ 和一个 $m(m \leq n)$ 次多项式 $B(x)$,要求求出两个多项式 $D(x), R(x)$,满足 \[\begin{equation} \label{div0} A(x) = D(x)B(x) + R(x) \end{equation}\] 并且 $deg D \leq degA - degB = n - m$,$de...

BZOJ-3557. [Ctsc2014]随机数

露露、花花和萱萱最近对计算机中的随机数产生了兴趣。为大家所熟知的是,由计算机生成的随机数序列并非真正的随机数,而是由一定法则生成的伪随机数。 某一天,露露了解了一种生成随机数的方法,称为 Mersenne twister。给定初始参数 $m \in \mathbb Z^+$,$x \in \mathbb Z \cap [0, 2^m)$ 和初值 $M_0 \in \mathbb Z \ca...