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

给定三个正整数 、 和 ，统计长度在 到 之间，元素大小都在 到 之间的单调不降序列的数量。输出答案对 取模的结果。

链接

BZOJ 4403

题解

问题等价于，从 中选择 个数（可重复）的方案数。

设

答案为

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

当 时，直接使用公式计算即可。

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

代码

#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;
}