洛谷5339 [TJOI2019]唱、跳、rap 和篮球
LuoguLOJ分析考虑容斥，问题变为计算至少有 $i$ 组人讨论 cxk 的方案数。首先我们需要选出 $i$ 个位置 $p_{1..i}$ 满足 $[p_j,p_j+3]$ 不交，容易算出方案数为 ${n-3i\choose i}$。对于剩下的位置，枚举每种学生的个数，方案数是一个多重集排列数，式子是可以看成四个生成函数卷起来，用 NTT 可以 $\mathcal{O}(n\log n)$...
标签 排列组合 下的文章
- 首页
- 排列组合
洛谷5320 [BJOI2019]勘破神机
LuoguLOJ分析显然二合一，先考虑 $m=2$ 的情况。可以知道 $2\times n$ 网格的方案数就是 $f_{n+1}$。为了方便，我们把 $l,r$ 都加上 $1$，那么相当于要求用同样的方法扩域计算即可。代码// ==================================== // author: M_sea // website: https://m-sea...
洛谷5363 [SDOI2019]移动金币
LuoguLOJ分析一次移动后会让左边的空位减少若干，右边的空位增加若干，从而可以转化为一个阶梯博弈。不妨把左右反过来，那么就是要算有多少种方案满足编号为偶数的空位的异或和不为 $0$。再转化问题，相当于求 $n-m$ 个物品放进 $m+1$ 个盒子中，使得编号为偶数的盒子中的物品数的异或和不为 $0$ 的方案数。这个不为 $0$ 不好处理，可以容斥一下，变成算为 $0$ 的。那么就是每一位...
洛谷4384 [八省联考2018]制胡窜
LuoguLOJ分析首先容斥一下，求出三段都不包含 $s_{l..r}$ 的方案数，然后用 ${n-1\choose 2}$ 减掉即为答案。我们先把所有和 $s_{l..r}$ 相等的子串位置都找到，然后分类讨论一下：如果有三个互不相交的串，方案数是 $0$。如果最左边的串和最右边的串相交：考虑 $i$ 的位置：如果 $i\in[1,l_1)$，那么 $j\in(l_m,r_1]$，方案数为...
CF1264D2 Beautiful Bracket Sequence (hard version)
CodeforcesLuogu分析考虑枚举一个分界点，如果左边的 ( 和右边的 ) 相等，那么深度就是左边的 ( 数。设 $l$ 为左边的 ( 数、$f$ 为左边的 ? 数、$r$ 为右边的 ) 数、$g$ 为右边的 ? 数，枚举深度，方案数为时间复杂度 $\mathcal{O}(n)$。代码// ==================================== // autho...
洛谷4351 [CERC2015]Frightful Formula
LuoguGym分析先考虑 $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+j>n...
AGC038E Gachapon
AtCoderLuogu分析我不喜欢容斥，我不喜欢组合意义，我不喜欢生成函数，我也没有精神首先 Min-Max 容斥一手转移直接枚举 $d$ 即可。为了方便我们把容斥系数压到 DP 里去，转移要乘上一个 $-1$。算答案就把上面这个东西代回去就好了。代码// ==================================== // author: M_sea // websit...
JOISC2018 部分题解
高速道路の建設 / Construction of Highway这个操作长得很像 LCT 中的 access。于是我们每次只要 access 一下并把所有颜色段拿出来，然后树状数组求逆序对数，再把对应的边连上并把整条重链的颜色赋值为 $c_v$。因为 access 是均摊 $\mathcal{O}(\log n)$ 的，所以每次颜色段数也是均摊 $\mathcal{O}(\log n)$ ...
Codeforces Round #419 简要题解
Div1Div2Karen and Morning暴力枚举即可。代码Karen and Coffee差分求出每个点被覆盖的次数，再求一个被覆盖次数是否 $\geq k$ 的前缀和即可。代码Karen and Game先把行尽量删完，再把列尽量删完，如果最后剩下了则无解。但这不一定是最优的，还有可能先把列尽量删完，再把行尽量删完。两种情况比一下即可。代码Karen and Test$n$ 为偶...
AtCoder Regular Contest 077 简要题解
比赛地址pushpush双端队列模拟即可。代码11显然有恰好一个数出现了 $2$ 次，设其出现的两个位置为 $l,r(l<r)$。考虑容斥。长度为 $k$ 的子序列数显然为 ${n+1\choose k}$，但其中有重复的。冷静分析一下可以发现，重复的一定是在 $l-1+(n+1-r)$ 个元素中选了 $k-1$ 个，和某个重复的数组成了子序列。所以答案为 ${n+1\choose k...