题意
你有一个数 $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 时有多少种可能。这是卡特兰数。
卡特兰数有两种形式：
- $\displaystyle \binom{2n}n - \binom{2n}{n - 1}$
- $\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$ 质因数分解，扩展欧几里得解决即可。