文章

关于同种音乐的限制，最后直接让答案除上 $m!$ 即可。 现在我们需要算出选出 $m$ 的片段的方案数，考虑 $\rm{DP}$ ，设 $dp_i$ 表示前 $i$ 个片段已经确定，且满足下列要求： 这 $i$ 个片段中没有空集 这 $i$ 个片段互不相同 这 $i$ 个片段中所有的音符的出现次数全 阅读更多…

我们考虑这样一个问题。 $$ans=\sum_{i=1}^nf(i)$$ 其中 $1\leq n\leq 10^{10}$ 其中 $f(i)$是一个非常奇怪的函数，并不像 $\mu(i),\varphi(i),i\varphi(i)$那样具有那么好的性质。但是满足以下条件： 1. 若 $p$为质数， 阅读更多…

题目分析 $\mu(m)=\sum_{m|d} F(d)$ $F(m)=\sum_{m|d} \mu(d) \mu(\frac{m}{d})$ $=\mu(m) \sum_{i=1}^{\lfloor \frac{n}{m} \rfloor}\mu(i)^2 [gcd(i,m)==1]$ $=\mu 阅读更多…

题目分析 建立出小根堆性质的笛卡尔树，于是每个节点可以代表一个矩形，其宽度为子树大小，高度为该节点记录的那一列高度-父节点那一列高度。 设 $f(x,i)$表示以 $x$为跟的子树中放了 $i$个棋子的方案数。 初始值：$f(0,0)=1$ 首先求出不在 $x$的矩形中放棋子的方案数：$f(x,i) 阅读更多…

我们先不考虑边的权值(< 与>)，这样子 $n-1$ 条边组成的就是树了，很显然是需要我们求出这棵树的合法拓扑序的个数，考虑使用 $\rm{DP}$ ，对于边的方向(即<,>) ，我们分类讨论即可。

首先的一个想法就是设 $f_u$ 表示点 $u$ 的子树的合法拓扑序的总数，但是这个时候如何计算呢 （更多…）

有趣的题目，可爱的传送门：戳这呢=￣ω￣= 刚开始往概率 $\rm{DP}$ 想了，发现对于一个点的概率是好算，但是如果求贡献的话就会很难办。最后万般无赖的点开了题解，发现居然是…… 组合数学？其实和 $\rm{DP}$ 没有半毛钱关系。 我们考虑一个节点 $i$ ，我们枚举 阅读更多…

本文所包含的思路来自于 NCC79601 * 算法剖析 简单来讲，背包退火就是用模拟退火的思路解决某些类型的背包问题，继承了模拟退火的玄学复杂度，也继承了它的不稳定性，所以能够有效地解决大背包问题的 TLE 问题。这个算法能够把数十行的代码优化部分转移为 洗把脸 调参的问题。 例题 ：LuoGuP1 阅读更多…

题目分析 不难发现需要枚举 D 和 A，然后鱼头鱼尾分别处理。 对于鱼尾，其实就是对着 A 的半平面内两条到 D 距离相等的线段组成的，枚举 D 后，将其他点极角排序，然后扫描线即可解决。 对于鱼头，也就是 BC 这条线段要垂直于 AD，且 BC 的中点在 AD 上。则预处理枚举每个 BC，将这个点 阅读更多…

在我的不断探索发现下，我意识到 DFS 似乎可以用来做数独…… 于是乎就上手操作了一下，然后就做出来了？ 其实思路很简单，就是简单的 DFS (废话，本蒟蒻都想出来了能不简单吗) 就是模仿人填数独的过程，只是更加无脑。 一个个试起走，放不了就回溯，直到解出答案，输出 真的就只有那么简单了，秒杀人脑啊 阅读更多…