Sequence

题目描述

小 F 是一位 Hack 国的居民,他生活在一条长度为 $n$ 的街道上,这个街道上总共有 $n$ 个商店。每个商店里售卖着不同的 Hack 技能包,每个商店本身也会有个便利值。初始时,每个商店的便利值均为 0。每一天,街道上都会有一些商店优化改造。
具体来说,对于每一天,优化改造的商店都是一个连续的区间 $l ∼ r$,每次优化改造也会有一个优化参数 $k$。对于所有 $l ≤ i ≤ r$ ,第 $i$ 个商店的便利值会增加 $\binom {i+k-l}{k}$。

小 F 想知道,$m$ 天之后,每个商店的便利值分别是多少。由于小 F 并不喜欢高精度,因此你只需要输出便利值对 $10^9 + 7$ 取模的结果。

思路

可以发现组合数有一个简单的性质,即 $\binom {n}{k} = \binom {n-1}{k} + \binom {n-1}{k-1}$,我们可以从这个式子中获得启发。考虑一个下标从 $0$ 开始的数列,这个数列的每个数均为 $1$。容易发现这个数列 $k$ 阶前缀和的第 $i$ 项即为 $\binom {k+i}{k}$。(经典的矩形最短路径数量问题的方案数列)

对于这个数列,维护这个数列的 $k$ 阶差分。对于一次修改操作,我们只需要在各阶差分数组上修改,最后做一遍 $k$ 阶的前缀和即可。注意差分数组上修改时,区间边界要相应地减掉一些值。时间复杂度 $O(nk)$,期望得分 $100pts$。

代码

Bomb

题目描述

常数国与 Hack 国近年来战火纷飞。

常数国共有 n 个城市,每两个城市之间均有一条交通线联通。如今常数国遭到 Hack 国的重创,岌岌可危。Hack 国国王小 K 决定轰炸常数国的交通线,对常数国发起最后的攻击。

面对危难之时,常数国国王决定更换首都。在 Hack 国的轰炸结束之后,常数国的领土将会分成若干个联通块。常数国的首都,将会从联通块大小最大的联通块中,随机选择一个城市,作为首都。

小 K 得知了常数国的应对方案之后,他想知道,Hack 国有多少种不同的轰炸方案,使得常数首都所在的联通块大小恰好为 k。两种轰炸方案是不同的,当且仅当一条交通线在一种方案中存在,在另一种方案中被轰炸。由于方案数可能很大,你需要输出方案数对 998244353 取模的结果。

思路

我们先考虑 $k=n$ 的情况,也就是 $n$ 个点的带标号连通图个数。设 $g_i$ 为共有 $i$ 个点的情况,我们容斥一下,求出不连通的情况,可以得到

$$g_i=2^{\binom{i}{2}} – \sum_{j=1}^{i-1}2^{\binom{i-j}{2}}\binom{i-1}{j-1}g_j$$

上式中,$2^{\binom{i}{2}}$ 枚举所有可能的边的状态。现在我们只关心 1 号节点,假设它所在的联通块大小为 $j$,那么我们要从剩下的 $i-1$ 个点中选出 $j-1$ 个点与之相连,剩下 $i-j$ 个点不与选出的这 $j$ 个点连边,那么方案数为 $2^{\binom{i-j}{2}}\binom{i-1}{j-1}g_j$。时间复杂度 $O(n^2)$。

现在我们考虑不受限制的 $k$。如果我们令 $f_{i,j}$ 为共有 $i$ 个点,其中最大联通块大小为 $j$,我们需要 $O(n^2)$ 来转移,时间复杂度为 $O(n^3)$。但是,如果我们令 $f_i$ 为 $i$ 个点的图中最大联通块大小不大于 $k$ 的方案,那么我们可以枚举与 1 号点相连的点的个数 $j$,得到转移方程

$$f_{i,k}=\sum_{j=1}^{\min (i,k)}f_{i-j,k}\binom{i-1}{j-1}g_j$$

分别求出 $f_k, f_{k-1}$,答案为两者之差。在上个式子中不需要枚举 $k$,时间复杂度 $O(n^2)$。

代码

Queue

题目描述

Hack 国的居民人人都是 OI 大师,Hometown 得知便赶紧来到 Hack 国学习。可想要进入 Hack 国并不是件容易的事情,首先就必须通过 Hack 国海关小 B 的
考验。小 B 觉得 Hometown 比较菜,于是就扔了一道小水题给 Hometown。

给定一个长度为 $n$ 的数列 $a_i$,接下来会对这个序列进行 $m$ 次操作。操作类型分为以下两种:

  • $1 \ l \ r$,表示将区间 $[l, r]$ 轮转一次,具体来说,$a_l, a_{l+1}, a_{l+2}, · · · , a_{r−1}, a_r$ 经过一次轮转之后,会变为 $a_r, a_l, a_{l+1}, · · · , a_{r−1}$;
  • $2 \ l \ r \ k$,询问区间 $[l, r]$ 内 $a_i = k$ 的个数。

可惜 Hometown 还是不会做,他只能期待你能解决这个问题了。

思路

一开始我把题目看成了区间翻转,就花了很久写了一个 $Splay$,发现真相以后我就决定这场比赛不交题了。

发现每次修改其实是将 $a_r$ 插入到 $a_l$ 的前面,其他点的相对位置不动,就可以用链表维护这个序列的状态;又发现每次查询只询问一种数值出现的个数,那么我们可以分块回答询问。我的做法是记录下每个块内部的不同数值出现次数,用 $deque$ 维护每个块存储的数字。那么直接翻译题面就行了,简直就是暴力。由于本题开启 $\text {-O2}$,还是跑得很快的。

代码