洛谷3773 [CTSC2017]吉夫特
Luogu LOJ 分析 由 Lucas 定理可以推出，${n\choose m}\bmod 1\equiv{2}$ 当且仅当 $n \& m = m$。这样子很容易有一个 $\mathcal{O}(n^2)$ 的 DP。 为了方便，我们倒过来 DP，则要求上一个数是这一个数的子集，直接枚举子集转移即可。 复杂度是 $\mathcal{O}(3^{\log A})$ 的。 代码 //...
博主已经退役，评论可能会审核很久才能通过。
博主已经退役，评论可能会审核很久才能通过。
Luogu LOJ 分析 由 Lucas 定理可以推出，${n\choose m}\bmod 1\equiv{2}$ 当且仅当 $n \& m = m$。这样子很容易有一个 $\mathcal{O}(n^2)$ 的 DP。 为了方便，我们倒过来 DP，则要求上一个数是这一个数的子集，直接枚举子集转移即可。 复杂度是 $\mathcal{O}(3^{\log A})$ 的。 代码 //...
Codeforces Luogu 分析 $\mathcal{O}(k ^ 2)$ 预处理第二类斯特林数即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #...
Codeforces Luogu 分析 先对 $T_{1..m}$ 建立广义 SAM，然后把 $S$ 丢上去匹配，记录每个前缀匹配到的节点 $pos_i$。 考虑对每个节点维护一棵以 $T$ 的下标为下标的线段树，线段树上的每个节点维护当前串在这些 $T$ 串中的出现次数的最大值及其下标。这可以通过线段树合并预处理出来。 询问时，我们首先找到 $s_{l..r}$ 所在的节点，直接从 $po...
Luogu LOJ 分析 题目中的条件相当于 $(p+1)(q+1)\geq n$。 第一问可以每次选一个度数最小的点删去，然后更新答案。用堆维护可以做到 $\mathcal{O}(n\log n)$。 第二问是求独立集，也可以每次选一个度数最小的点，然后把它和与它相连的点都删去。 可以证明这样子一定是满足条件的。设第 $i$ 次删掉的点的度数为 $d_i$，那么有 $\sum_{i=1}^...
Luogu LOJ 分析 容易想到一个费用流，即将每个哨站拆成两个点 $i$ 和 $i'$，然后源点向 $i$ 连容量为 $1$ 费用为 $0$ 的边，$i$ 向汇点连容量为 $1$ 费用为 $W$ 的边，$i'$ 向汇点连容量为 $1$ 费用为 $0$ 的边，$i$ 向 $j'$（$i<j$）连容量为 $1$ 费用为 $|a_i-a_j|$ 的边，然后求最小费用最大流即可。 然而这样...
Luogu LOJ 分析 考虑枚举一个 $A_i$，则我们需要计算 发现 $(Px+A_i)\bmod Q$ 有长度为 $\frac{Q}{\gcd(P,Q)}$ 的循环节，因此我们可以暴力求出循环节，然后计算。这样子是 $\mathcal{O}\left(\frac{nQ}{\gcd(P,Q)}\right)$ 的。 注意到模 $\gcd(P,Q)$ 意义下相等的 $A_i$ 循环节内的...
Luogu LOJ 分析 考虑容斥，问题变为计算至少有 $i$ 组人讨论 cxk 的方案数。 首先我们需要选出 $i$ 个位置 $p_{1..i}$ 满足 $[p_j,p_j+3]$ 不交，容易算出方案数为 ${n-3i\choose i}$。 对于剩下的位置，枚举每种学生的个数，方案数是一个多重集排列数，式子是 可以看成四个生成函数卷起来，用 NTT 可以 $\mathcal{O}(n\...
Luogu LOJ 分析 二进制下每一位模 $3$ 的余数是 $1,2,1,2,\cdots$，也可以看成 $1,-1,1,-1,\cdots$。 假设有 $k$ 个 $1$，我们要将其分配到 $\lceil\frac{n}{2}\rceil$ 个 $1$ 和 $\lfloor\frac{n}{2}\rfloor$ 个 $-1$ 上，使得分配到的 $1$ 和 $-1$ 的和是 $3$ 的倍数...
Luogu UOJ 分析 考虑把每个筐子拆成三个点，三个点间互相连边，然后每个球向能放的筐子拆成的三个点连边。 考虑这张图的一个最大匹配：如果某个筐子匹配了 $0$ 个球，那么会贡献 $1$ 个匹配；如果匹配了 $1$ 个球，那么会贡献 $2$ 个匹配；如果匹配了 $2$ 或 $3$ 个球，那么会贡献 $2$ 或 $3$ 个匹配。 也就是说，半空的筐子贡献的匹配数恰为匹配的球数加 $1$。 ...
Luogu LOJ 分析 显然二合一，先考虑 $m=2$ 的情况。 可以知道 $2\times n$ 网格的方案数就是 $f_{n+1}$。为了方便，我们把 $l,r$ 都加上 $1$，那么相当于要求 用同样的方法扩域计算即可。 代码 // ==================================== // author: M_sea // website: https...