「BZOJ 4403」序列统计 - 组合数

给定三个正整数 N L R ,统计长度在 1 N 之间,元素大小都在 L R 之间的单调不降序列的数量。输出答案对 10 ^ 6 + 3 取模的结果。

链接

BZOJ 4403

题解

问题等价于,从 [1, R - L + 1] 中选择 N 个数(可重复)的方案数。

M = R - L + 1

答案为

\begin{align} & \sum\limits_{i = 1} ^ N C(i + M - 1, i) \\ = & \sum\limits_{i = 1} ^ N C(i + M - 1, M - 1) \\ = & \sum\limits_{i = 1} ^ N C(i + M - 1, M - 1) + C(m, m) - 1 \\ = & \sum\limits_{i = 2} ^ N C(i + M - 1, M - 1) + C(m, m - 1) + C(m, m) - 1 \\ = & \sum\limits_{i = 2} ^ N C(i + M - 1, M - 1) + C(m + 1, m) - 1 \\ = & \sum\limits_{i = 3} ^ N C(i + M - 1, M - 1) + C(m + 2, m) - 1 \\ = & C(m + n, m) - 1 \\ \end{align}

直接算组合数会超时,需要用 Lucas 定理

C(n, m) \ {\rm mod} \ p = C(\lfloor \frac{n}{p} \rfloor, \lfloor \frac{m}{p} \rfloor) * C(n \ {\rm mod} \ p, m \ {\rm mod} \ p)

n \lt p, m \lt p 时,直接使用公式计算即可。

不要预处理逆元,用到的时候用费马小定理计算即可。

代码

#include <cstdio>

const int MAXN = 1e9;
const int MOD = 1e6 + 3;
const int PHI_MOD = MOD - 1;

long long fac[MOD];

inline long long pow(const long long x, const long long n) {
    long long ans = 1;
    for (long long num = x, t = n; t; num = num * num % MOD, t >>= 1) if (t & 1) ans = ans * num % MOD;
    return ans;
}

inline void makeTable() {
    fac[0] = 1;
    for (int i = 1; i < MOD; i++) fac[i] = fac[i - 1] * i % MOD;
}

inline long long inv(const long long x) {
    return pow(x, PHI_MOD - 1);
}

long long lucas(const int n, const int m) {
    if (n < m) return 0;
    else if (n < MOD && m < MOD) return fac[n] * inv(fac[m]) % MOD * inv(fac[n - m]) % MOD;
    return lucas(n / MOD, m / MOD) * lucas(n % MOD, m % MOD) % MOD;
}

inline int solve(const int n, const int l, const int r) {
    return ((lucas(n + r - l + 1, r - l + 1) - 1) + MOD) % MOD;
}

int main() {
    makeTable();

    int t;
    scanf("%d", &t);
    while (t--) {
        int n, l, r;
        scanf("%d %d %d", &n, &l, &r);
        printf("%d\n", solve(n, l, r));
    }

    return 0;
}