Tellegens Principle

问题 给出一个 $m\times n$ 的矩阵 $A$,以及一个用于计算 $u\mapsto Au$ 的(线性的)算法,求一个几乎同样次数乘、同样次加减法的用于计算 $v\mapsto A^Tv$ 的算法。 本篇 Blog 是个人口嗨。 ...

一种多项式多点求值算法

Problem 给定一个 $m-1$ 次多项式 $f(x)$ 以及 $n$ 个点 $\alpha_0,\dots,\alpha_{n-1}$,求 $f(\alpha_0),f(\alpha_1),\dots,f(\alpha_{n-1})$。 参考:《转置原理的简单介绍》rushcheyo, negiizhao, Created_Equal 参考:EI’s blog 参考:Tellegen’s Principle into Practice ...

生成函数简介

生成函数 生成函数(generating function)又称母函数,是处理组合数学问题的一大利器。 ...

带花树

Problem UOJ79. 某机房里有$n$个OIer,其中有$n$个男生,$0$个女生。现在他们要两两配对。 有$m$个关系,每个关系是一个无序对$(a_i,b_i)$,表示这两个人之间愿意配对。 求:最多能配成多少对,并找出一组方案。 说人话:一般图最大匹配。 ...