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