本文作于 2023 年 4 月。 作为一道生成函数的练习题。 不用生成函数推了好久还是错的。 以后遇到这类递推关系绝对首选 GF（能力范围内）。 简单观察不难发现，如果 \(m<n\)，那么无解。如果 \(m=n\)，那么只能是连续的 \(n\) 个01。 考虑 \(m>n\) 的情况，不难发现任何一个合法串都可以在一个初始串——连续的 \(n\) 个01中插入 \(m-n

专门放一些不大可能会考的计数题，长期更新。 大约是输入的只有问题规模，输出的只有相应方案数。 luogu6561 [SBCOI2020] 人 两两不相邻这个条件不是很容易搞。 考虑把 \([1,2m]\) 分成 \(m\) 个数对，形如 \((\text{odd},\text{even})\)，其中 $ +1 = $ 把选择了 \(\text{odd}\) 的数对称为A，选择了 \(

计数杂题。 CF840C On the Bench 先进行一些基本的观察。 \(\texttt{Observation}\) \(\{a_i\}\) 中乘积为完全平方数的数集，一定是相对封闭的。因此我们可以将 \(\{a_i\}\) 划分成若干个集合，满足其中两两乘积为完全平方数。 \(\texttt{proof}\) 考虑和 \(a_i\) 相乘为完全平方数的数集 \(\{

倍增处理的是满足「结合律」的静态信息 CF1175E Minimal Segment Cover 预处理 \(rt_x\) 表示点 \(x\) 经过一条线段能到达的最右边的点。 跳区间显然是满足结合律的，可以倍增之，复杂度 \(O(n \log_2 n)\)。 这类题目有一个重要的小技巧：为了满足最优性，倍增时跳到不能到达 \(y\) 的最远的点 \(p\)，然后判断能一次跳过 \(y\

多项式哈希 把元素看作数字，把哈希对象看作关于 \(P\) 的多项式，得到多项式哈希，亦称为进制哈希。 主要用于有序对象的哈希。 一般使用unsigned long long自然溢出，相当于对 \(2^{64}\) 取模。 关于 \(P\) 的选取，尽量避免常用的大质数。下文统一使用1610612741，其在 \([2^{30},2^{31}]\) 中。 单哈希的话很简单。 vo

Trie luogu2922 [USACO08DEC]Secret Message G 给定两个字符串序列 \(a\) 与 \(b\)，对于 \(b\) 中每个字符串 \(t\)，求 \(a\) 中有多少个字符串 \(s\)，满足以下两个条件之一 \(s\) 是 \(t\) 的前缀。 \(t\) 是 \(s\) 的前缀。 两个字符串序列中所有字符串长度之和不超过 \(500

突破口永远在环上。   找环是常用操作，但是并没有一个合适的模板。 笔者在写这篇文章之前就做过一些基环树的简单题，但是每一次写的找环都不尽相同。仅仅用dfs的回溯模拟一个栈，显然是不够公式化的，且容易出 bug，因此我们需要确定一种可靠的写法。 关于dfn的那套理论再合适不过了。 当然这玩意只能找一个环。 int cnt, num, fa[N], dfn[N], cir[N]; vo

树形 DP 计数。 luogu8867 建造军营 对于图中一条非割边，看守与否都相同，因此可以用 Tarjan 算法求出边双再缩点，把非树边单独拿出来，讨论每一条树边。 然而貌似不是很好做，子树外是否建造会影响子树内。考虑设 \(f_x\) 为军营只在以 \(x\) 为根的子树中出现，且至少存在 \(1\) 个军营的方案数。 转移时对于边 \((x,y)\)，如果 \(y\) 中没有军营

OI 中的博弈论主要研究公平组合游戏（ICG）。 此外还有非公平组合游戏，比如大部分的棋类；反常游戏，ICG中的胜者改为败者。 公平组合游戏 定义 如果一个游戏满足以下条件，就称其为一个公平组合游戏 由两名玩家交替行动。 在游戏的任意时刻，能执行的合法操作与当前是那一名玩家无关。 先无法行动者告负。 同时公平组合游戏一定只有先手必胜和先手必败两种情况。 Bash Game

树链剖分能够将一棵树按照某种法则剖分为若干条链，从而便于维护树上路径的信息。 按照剖出链的法则不同，其性质也不同，大体可将树剖分成重链剖分，长链剖分和用于 Link-Cut Tree 的剖分（实链剖分）。 其中重链剖分用途最广泛，本文也只介绍重链剖分。 重链剖分 定义与部分性质 给出如下定义 重儿子。对于一个非叶子节点，其重儿子为其以它的所有儿子为根的子树中，最大子树所对应的那个