UOJ551 【UNR #4】校园闲逛
UOJ 分析 设 $f_{i ,j, w}$ 为从 $i$ 走到 $j$、权值和为 $w$ 的方案数，$g_{i, j, w}$ 表示连接 $i,j$ 的权值为 $k$ 的边数。 那么有 可以证明 $I-G$ 一定是可逆的。于是我们只需要求一个每个元素都是一个多项式的矩阵的逆，和普通矩阵求逆类似地做即可。 然而这题还卡常，需要精细地实现来减少 NTT 的次数，最好把预处理原根、取模优化、寻...
分类 题解 下的文章
- 首页
- 题解
洛谷4827 [国家集训队] Crash的文明世界
Luogu 分析 预处理斯特林数和阶乘，换根 DP 求出后面的东西即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/s...
洛谷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})$ 的。 代码 //...
CF932E Team Work
Codeforces Luogu 分析 $\mathcal{O}(k ^ 2)$ 预处理第二类斯特林数即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #...
CF666E Forensic Examination
Codeforces Luogu 分析 先对 $T_{1..m}$ 建立广义 SAM，然后把 $S$ 丢上去匹配，记录每个前缀匹配到的节点 $pos_i$。 考虑对每个节点维护一棵以 $T$ 的下标为下标的线段树，线段树上的每个节点维护当前串在这些 $T$ 串中的出现次数的最大值及其下标。这可以通过线段树合并预处理出来。 询问时，我们首先找到 $s_{l..r}$ 所在的节点，直接从 $po...
洛谷5361 [SDOI2019]热闹的聚会与尴尬的聚会
Luogu LOJ 分析 题目中的条件相当于 $(p+1)(q+1)\geq n$。 第一问可以每次选一个度数最小的点删去，然后更新答案。用堆维护可以做到 $\mathcal{O}(n\log n)$。 第二问是求独立集，也可以每次选一个度数最小的点，然后把它和与它相连的点都删去。 可以证明这样子一定是满足条件的。设第 $i$ 次删掉的点的度数为 $d_i$，那么有 $\sum_{i=1}^...
洛谷5331 [SNOI2019]通信
Luogu LOJ 分析 容易想到一个费用流，即将每个哨站拆成两个点 $i$ 和 $i'$，然后源点向 $i$ 连容量为 $1$ 费用为 $0$ 的边，$i$ 向汇点连容量为 $1$ 费用为 $W$ 的边，$i'$ 向汇点连容量为 $1$ 费用为 $0$ 的边，$i$ 向 $j'$（$i<j$）连容量为 $1$ 费用为 $|a_i-a_j|$ 的边，然后求最小费用最大流即可。 然而这样...
洛谷5330 [SNOI2019]数论
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$ 循环节内的...
洛谷5339 [TJOI2019]唱、跳、rap 和篮球
Luogu LOJ 分析 考虑容斥，问题变为计算至少有 $i$ 组人讨论 cxk 的方案数。 首先我们需要选出 $i$ 个位置 $p_{1..i}$ 满足 $[p_j,p_j+3]$ 不交，容易算出方案数为 ${n-3i\choose i}$。 对于剩下的位置，枚举每种学生的个数，方案数是一个多重集排列数，式子是 可以看成四个生成函数卷起来，用 NTT 可以 $\mathcal{O}(n\...
洛谷4428 [BJOI2018]二进制
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$ 的倍数...