自己出的另一道题

发布于

题意

你有一个数 $a$,初始时是 $0$。
你要生成 $n$ 个对 $a$ 操作。每个操作可以是加 $1$,减 $1$,或者不变。
要求:任意时刻 $a \geq 0$,且最终 $l \leq a \leq r$,其中 $l$ 和 $r$ 是给定的。
答案对给定质数 $p$ 取模。
目前我的做法可以做到 $\mathcal O\left(n \log n\right)$。

题解

看题解之前最好先思考一下。

查看题解
首先暴力一下,枚举每种操作个数,记为 $a, b$ 和 $c = n - a - b$。
首先,考虑只有操作 1 和操作 2 时有多少种可能。这是卡特兰数。
卡特兰数有两种形式:

  1. $\displaystyle \binom{2n}n - \binom{2n}{n - 1}$
  2. $\Large \displaystyle \frac{\binom{2n}n}{n + 1}$
    可以两个都试试。考虑到一种可能,第一种形式是差式,可能可以消去,所以尝试使用方式 1。
    接下来考虑把操作 3 插入。显然是乘上一个 $\displaystyle \binom n c = \binom n {n - a - b} = \binom n {a + b}$。
    目前的式子就出来了(我选择先枚举 $b$, 然后 $a$ 是大于等于 $b - l$,小于等于 $b + r$ 的,这样好处理一点):
    $$\large \sum\limits_{b \geq 0, 2b + l \leq n} \sum\limits_{a = b + l}^{\min\left\{b + r, n\right\}} \binom n{a + b}\left(\binom{a + b}b - \binom{a + b}{b - 1}\right)$$

现在不能差分相消,因为 $a + b$ 会变,考虑改变枚举顺序,先枚举 $s = a + b$,然后枚举 $b$,再算出 $a$。

$$\large \sum\limits_{s = l}^n \left(\binom ns \cdot \sum\limits_{b = \max\left\{0, \left\lfloor\frac{s - r}2\right\rfloor\right\}}^{\left\lfloor\frac{s - l}2\right\rfloor} \left(\binom sb - \binom s{b - 1}\right)\right)$$

于是现在可以差分相消了。

$$\large \sum\limits_{s = l}^n \binom ns\left(\binom s{\left\lfloor\frac{s - l}2\right\rfloor} - \binom s{\left\lfloor\frac{s - r}2 - 1\right\rfloor}\right)$$

显然这不够难

为了强行增加难度,我决定把 $p$ 改为合数,即答案对给定合数取模。
其实也很简单,把 $p$ 质因数分解,扩展欧几里得解决即可。


暂无评论

发表评论