题目 | 序列统计

LibreOJ10235. 序列统计

https://loj.ac/p/10235

题目描述

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

输入格式

输入第一行包含一个整数 $T$，表示数据组数。

第二到第 $T+1$ 行每行包含三个整数 $N,L$ 和 $R$，$N,L$ 和 $R$ 的意义如题所述。

输出格式

输出包含 $T$ 行，每行有一个数字，表示你所求出的答案对 ${10}^6+3$ 取模的结果。

样例

输入

2
1 4 5
2 4 5

输出

2
5

对于第一组输入，满足条件的两个序列为 $4,5$。

数据范围与提示

对于全部输入，$1\le N,L,R\le {10}^9,1\le T\le 100$，输入数据保证 $L\le R$。

题解

长度为 $N$，令 $L=1$ 时

我们先从长度为 $N$ 的单调不减序列 $a_1,a_2,\dots ,a_N$ 入手，其中 $a_i\in [1,R]$.

单调不减不好处理，我们令 $b_i=a_i+(i-1)$，即可得到一个单调增序列 $b_1,b_2,\dots ,b_N$，其中 $b_i\in [1,R+(N-1)]$.

原序列与变换后的序列能够保证一一对应，并且若变换后的序列满足单调增，原序列一定单调不减。

借助新序列，我们容易得出这种情况的数量为：$C_{R+N-1}^N$

长度为 $N$ 时

我们将上面的结论推广，计算长度为 $N$ 的单调不减序列 $a_1,a_2,\dots ,a_N$ 的情况数，其中 $a_i\in [L,R]$.

我们令 $c_i=a_i-L+1$，即可得到一个新的单调不减序列 $c_1,c_2,\dots ,c_N$，其中 $c_i\in [1,R-L+1]$，我们就可以再套用上面的结论。

这种情况的数量为：$C_{R-L+N}^N$

长度为 $1,2,\dots ,N$ 的总数

最后我们需要将所有情况加到一起，即：

$$\sum _{n=1}^N{C}_{R-L+n}^n$$

直接求和肯定要超时，尝试进行变形：

$$\begin{array}{rl}& \sum _{n=1}^N{C}_{R-L+n}^n\\ =& \sum _{n=1}^N{C}_{R-L+n}^{R-L}\\ =& \sum _{n=1}^N{C}_{R-L+n}^{R-L}+C_{R-L+1}^{R-L+1}-1\\ =& \sum _{n=2}^N{C}_{R-L+n}^{R-L}+C_{R-L+1}^{R-L}+C_{R-L+1}^{R-L+1}-1\\ =& \sum _{n=2}^N{C}_{R-L+n}^{R-L}+C_{R-L+2}^{R-L+1}-1\\ =& \sum _{n=3}^N{C}_{R-L+n}^{R-L}+C_{R-L+2}^{R-L}+C_{R-L+2}^{R-L+1}-1\\ =& \sum _{n=3}^N{C}_{R-L+n}^{R-L}+C_{R-L+3}^{R-L+1}-1\\ & ⋮\\ =& C_{R-L+N+1}^{R-L+1}-1\end{array}$$

最后结果仅为一个组合数。数据规模 ${10}^9$，对质数 ${10}^6+3$ 取模，因此考虑使用卢卡斯定理求解该组合数。

代码

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e6 + 3;
long long fact[MOD + 10];

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

long long fast_pow(long long a, long long b, long long p)
{
    b %= p;
    long long ans = 1;
    while (b)
    {
        if (b % 2)
            ans = a * ans % p;
        a = a * a % p;
        b /= 2;
    }
    return ans;
}

inline long long inv(long long x, long long p)
{
    return fast_pow(x, p - 2, p);
}

long long comb(long long a, long long b, long long p)
{
    if (b > a)
        return 0;
    if (a < p && b < p)
        return fact[a] * inv(fact[b], p) % p * inv(fact[a - b], p) % p;
    return comb(a % p, b % p, p) * comb(a / p, b / p, p) % p;
}

int main()
{
    int n;
    cin >> n;
    init();
    while (n--)
    {
        long long N, L, R;
        cin >> N >> L >> R;
        cout << ((comb(N + (R - L + 1), R - L + 1, MOD) - 1) % MOD + MOD) % MOD << endl;
    }
    return 0;
}