luoguCF896D Nephren Runs a Cinema

神仙dp？A了这题就去搞分块

Nephren Runs a Cinema

一眼看过去就是卡特兰数

但VIP用户怎么办？我们发现他们在哪里都不影响答案，直接先不管他们，最后插入即可，就是把方案数乘一个 $\binom{n}{o}$ ， $o$ 代表有多少个VIP

来推倒推导卡特兰数， $Cat_n = \frac{\binom{2n}{n}}{n + 1} = \binom{2n}{n} - \binom{2n}{n - 1}$

所以，合法方案数就是：
$$
(\sum_{j = l}^r \binom{n - o}{\frac{n - o - j}{2}} - \binom{n - o}{\frac{n - o - j}{2} - 1}) * \binom{n}{o}
$$
发现 $i, j$ 必定同奇偶，且 $j$ 是；连续的，直接消掉中间项，变为：
$$
(\binom{n - o}{\frac{n - o - l}{2}} - \binom{n - o}{\frac{n - o - r - 1}{2}}) * \binom{n}{o}
$$
枚举 $o$ 用时 $O(n)$

但模数不是质数，考虑将模数分解，预处理阶乘的时候把包含模数的质因子取出来，记下指数，然后再乘回来

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e5 + 5, D = 40;
int n, p, l, r, phi;
int pr[N], inv[N], fac[N], c[N][D], cnt = 0;
int qpow(int x, int y)
{
    int res = 1;
    while (y)
    {
        if (y & 1)
            res = (LL)res * x % p;
        x = (LL)x * x % p;
        y >>= 1;
    }
    return res;
}
void prev()
{
    phi = p;
    fac[0] = inv[0] = fac[1] = inv[1] = 1;
    int t = p;
    for (int i = 2; i <= t / i; ++i)
    {
        if (t % i)
            continue;
        phi = (LL)phi / i * (i - 1);
        pr[++cnt] = i;
        while (!(t % i))
            t /= i;
    }
    if (t > 1)
        pr[++cnt] = t, phi = (LL)phi / t * (t - 1);
    for (int i = 2; i <= n; ++i)
    {
        t = i;
        for (int j = 1; j <= cnt; ++j)
        {
            c[i][j] = c[i - 1][j];
            while (!(t % pr[j]))
                t /= pr[j], ++c[i][j];
        }
        fac[i] = (LL)fac[i - 1] * t % p;
        inv[i] = qpow(fac[i], phi - 1);
    }
}
int C(int x, int y)
{
    if (y < 0 || x < y || n <= 0)
        return 0;
    if (!y)
        return 1;
    int res = (LL)fac[x] * inv[y] % p * inv[x - y] % p;
    for (int i = 1; i <= cnt; ++i)
        res = (LL)res * qpow(pr[i], c[x][i] - c[y][i] - c[x - y][i]) % p;
    return res;
}
int main()
{
    scanf("%d %d %d %d", &n, &p, &l, &r);
    prev();
    int ans = 0;
    r = min(r, n);
    for (int i = 0; i <= n - l; ++i)
    {
        int t = ((LL)C(n - i, (n - i - l) >> 1) - C(n - i, (n - i - r - 1) >> 1) + p) % p;
        ans = (ans + (LL)t * C(n, i) % p) % p;
    }
    printf("%d\n", ans);
    return 0;
}

废话：

接下来开始搞大分块！