洛谷5339 [TJOI2019]唱、跳、rap 和篮球
Luogu LOJ 分析 考虑容斥，问题变为计算至少有 $i$ 组人讨论 cxk 的方案数。 首先我们需要选出 $i$ 个位置 $p_{1..i}$ 满足 $[p_j,p_j+3]$ 不交，容易算出方案数为 ${n-3i\choose i}$。 对于剩下的位置，枚举每种学生的个数，方案数是一个多重集排列数，式子是 可以看成四个生成函数卷起来，用 NTT 可以 $\mathcal{O}(n\...
标签 排列组合 下的文章
- 首页
- 排列组合
洛谷5320 [BJOI2019]勘破神机
Luogu LOJ 分析 显然二合一，先考虑 $m=2$ 的情况。 可以知道 $2\times n$ 网格的方案数就是 $f_{n+1}$。为了方便，我们把 $l,r$ 都加上 $1$，那么相当于要求 用同样的方法扩域计算即可。 代码 // ==================================== // author: M_sea // website: https...
洛谷5363 [SDOI2019]移动金币
Luogu LOJ 分析 一次移动后会让左边的空位减少若干，右边的空位增加若干，从而可以转化为一个阶梯博弈。 不妨把左右反过来，那么就是要算有多少种方案满足编号为偶数的空位的异或和不为 $0$。 再转化问题，相当于求 $n-m$ 个物品放进 $m+1$ 个盒子中，使得编号为偶数的盒子中的物品数的异或和不为 $0$ 的方案数。 这个不为 $0$ 不好处理，可以容斥一下，变成算为 $0$ 的。那...
洛谷4384 [八省联考2018]制胡窜
Luogu LOJ 分析 首先容斥一下，求出三段都不包含 $s_{l..r}$ 的方案数，然后用 ${n-1\choose 2}$ 减掉即为答案。 我们先把所有和 $s_{l..r}$ 相等的子串位置都找到，然后分类讨论一下： 如果有三个互不相交的串，方案数是 $0$。 如果最左边的串和最右边的串相交： 考虑 $i$ 的位置： 如果 $i\in[1,l_1)$，那么 $j\in(l_m,...
CF1264D2 Beautiful Bracket Sequence (hard version)
Codeforces Luogu 分析 考虑枚举一个分界点，如果左边的 ( 和右边的 ) 相等，那么深度就是左边的 ( 数。 设 $l$ 为左边的 ( 数、$f$ 为左边的 ? 数、$r$ 为右边的 ) 数、$g$ 为右边的 ? 数，枚举深度，方案数为 时间复杂度 $\mathcal{O}(n)$。 代码 // ==================================== //...
洛谷4351 [CERC2015]Frightful Formula
Luogu Gym 分析 先考虑 $c=0$ 的情况。我们计算每个 $l_i$ 和 $t_i$ 对 $(n,n)$ 的贡献。 只考虑 $l_i$，那么相当于从 $(i,1)$ 走到 $(n,n)$，第一步必须往右，往右走一步乘 $a$，往下走一步乘 $b$，求所有路径的权值和。这个东西显然等于 可以发现，当 $i+j\leq n-2$ 时，贡献就是 $c(a+b)^{i+j}$；当 $i+...
AGC038E Gachapon
AtCoder Luogu 分析 我不喜欢容斥，我不喜欢组合意义，我不喜欢生成函数，我也没有精神 首先 Min-Max 容斥一手 转移直接枚举 $d$ 即可。为了方便我们把容斥系数压到 DP 里去，转移要乘上一个 $-1$。 算答案就把上面这个东西代回去就好了。 代码 // ==================================== // author: M_sea //...
JOISC2018 部分题解
高速道路の建設 / Construction of Highway 这个操作长得很像 LCT 中的 access。 于是我们每次只要 access 一下并把所有颜色段拿出来，然后树状数组求逆序对数，再把对应的边连上并把整条重链的颜色赋值为 $c_v$。 因为 access 是均摊 $\mathcal{O}(\log n)$ 的，所以每次颜色段数也是均摊 $\mathcal{O}(\log n...
ARC077F SS
AtCoder 分析 设 $T$ 为 $S$ 减去 $S$ 的最长 border 后缀后得到的串。 如果 $|T|$ 是 $|S|$ 的约数，那么操作得到的串依次是 可以发现，$s_i=s_{i-1}+s_{i-2}$。 那么串长增长的速度是指数级别的，所以我们可以直接暴力地算出前若干个这样的串中每个字符的个数，询问时把 $[1,r]$ 拆成若干个这样的串相接再加上不是一个完整的 $S$ ...
CF520E Pluses everywhere
Codeforces Luogu 分析 考虑每个数 $a_i$ 的贡献。枚举长度可以得到 预处理 $a_i$ 的前缀和即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==============================...