不是那么简单的矩阵树。 题目描述 T 国有 $N$ 个城市,用若干双向道路连接。一对城市之间至多存在一条道路。 在一次洪水之后,一些道路受损无法通行。虽然已经有人开始调查道路的损毁情况,但直到...
数学
GuOJ 1200「HB 省队互测 2019 Round1 Day2」游戏 题解【FWT】【DP】
子集卷积这个东西终于学到了啊,被喷 9012 年还有人不会 FST 的就是我了。 题目背景 北斗是一个爱玩游戏的女孩子。 题目描述 北斗有 $n$ 部游戏要玩,这些游戏以 $0\sim n-1$ 标号。她准备花...
洛谷 P5339 [TJOI2019]唱、跳、rap和篮球 题解【容斥】【meet-in-middle】【递推】【排列组合】
计数问题首推容斥,然后再解决一些棘手的组合问题? 题目描述 大中锋的学院要组织学生参观博物馆,要求学生们在博物馆中排成一队进行参观。 他的同学可以分为四类:一部分最喜欢唱、一部分最喜欢跳...
洛谷 P3306 [SDOI2013]随机数生成器 题解【BSGS】【数列】
数据比较强的 BSGS 题,很多细节都卡到了√ 题目描述 小 W 喜欢读书,尤其喜欢读《约翰克里斯朵夫》。最近小 W 准备读一本新书,这本书一共有 $P$ 页,页码范围为 $0 \cdots P-1$。 小 W 很忙,所以...
BSGS/exBSGS 学习笔记【同余】
〇、前言 BSGS 是用来求形如 $a^x\equiv b\pmod p$ 的最小非负整数解的算法。 当 $\gcd(a,p)=1$ 时可以直接使用 BSGS,当 $\gcd(a,p)\ne 1$ 时需要用到 exBSGS 进行转化。 参考资料: PoPoQQQ 《原根与指标》...
CF1163E Magical Permutation 题解【线性基】【递归】【构造】
首先恭喜 xht37 喜提本场 rk1。 考场上想到线性基了不会构造…貌似还有一些别的细节 Description Kuro has just learned about permutations and he is really excited to create a new permutation typ...
洛谷 P4336 [SHOI2016]黑暗前的幻想乡 题解【矩阵树定理】【容斥】
矩阵树定理明明只是个记结论的东西对吧..(大雾 题目描述 四年一度的幻想乡大选开始了,最近幻想乡最大的问题是很多来历不明的妖怪涌入了幻想乡,扰乱了幻想乡昔日的秩序。但是幻想乡的建制派妖怪(人类...
bzoj4589 Hard Nim 题解【FWT】【博弈】【快速幂】
我们需要理解变换的本质从而不会像个煞笔一样给自己增添不必要的复杂度。 Description Claris 和 NanoApe 在玩石子游戏,他们有 $n$ 堆石子,规则如下: Claris 和 NanoApe 两个人轮流拿石子,C...
快速沃尔什变换 FWT 学习笔记【多项式】
〇、前言 之前看到异或就担心是 FWT,然后才开始想别的。 这次学了 FWT 以后,以后判断应该就很快了吧? 参考资料 FWT 详解 知识点 by neither_nor 集训队论文 2015 集合幂级数的性质与应用及其快速算法 by ...
bzoj 4176 Lucas的数论 题解【莫比乌斯反演】【杜教筛】
怎么又有我不知道的东西啊..自闭了 Description 去年的 Lucas 非常喜欢数论题,但是一年以后的 Lucas 却不那么喜欢了。 在整理以前的试题时,发现了这样一道题目“求 $\sum f(i)$,其中 $1\le i\le ...