基础数学算法-序列统计

题目-序列统计

问题分析

尝试枚举序列长度$k$, 当$k$固定之后, 有多少个单调不下降序列, 并且所有数字在$[L,R]$之间

因为数字之间大小是相对的, 可以映射到$[0,R-L]$, 并且数字是单调不下降的

那么有序列
$$0\le a_1\le a_2...\le a_k\le R-L$$
令$x_1=a_1$, $x_2=a_2-a_1$, $x_k=a_k-a_{k-1}$

问题就转化成了$x_i\ge 0$条件下
$$x_1+x_2+...+x_k\le R-L$$
不定方程的非负整数解的个数

因为每个$x_i\ge 0$不好操作, 令$y_i=x_i+1$, 其中$y_i\ge 1$

$$y_1+y_2+...+y_k\le R-L+k$$

如果是等式, 那么$k$个变量需要放置$k-1$个隔板, 但是这里是$\le$, 因此可以放置$k$个隔板

也就是说最后一个隔板到最后一个小球的长度是$R-L+k-t$, $t$是实际的和

当前$k$的方案数$C_{R-L+k}^k$

那么答案是${\sum }_{k=1}^N{C}_{R-L+k}^k$, 令$m=R-L$

求和展开得到
$$C_{m+1}^1+C_{m+2}^2+...+C_{m+n}^n$$

由组合恒等式$C_a^b=C_a^{a-b}$得到

$$C_{m+1}^m+C_{m+2}^m+...+C_{m+n}^m$$

由组合恒等式$C_a^b=C_{a-1}^b+C_{a-1}^{b-1}$得到

$$C_{m+1}^{m+1}+C_{m+1}^m+C_{m+2}^m+...+C_{m+n}^m-1$$

整理得到

$$C_{m+2}^{m+1}+C_{m+2}^m+...+C_{m+n}^m-1$$

两项两项合并, 最终得到

$$C_{m+n}^{m+1}+C_{m+n}^m-1=C_{m+n+1}^{m+1}-1$$

最终的结果
$$ans=C_{R-L+N+1}^{R-L+1}-1$$

算法步骤

线性方程和线性不定方程的正整数解的个数都可以使用隔板法解决
观察数据范围, $R,L\le 10^9$比较大, 但是取模的数字很小$10^6+3$, 可以使用$lucas$定理计算组合数

代码实现

注意计算阶乘的逆元的时候$i$从$1$开始循环, 并且在$get$函数过程中需要进行取模

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 1e6 + 10, MOD = 1e6 + 3;

int n, l, r;
LL fact[N], infact[N];

LL q_pow(LL a, LL b, LL mod) {
   
    LL ans = 1;
    a %= mod;
    while (b) {
   
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

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

LL get(LL a, LL b) {
   
    if (a < b) return 0;
    LL ans = fact[a] % MOD * infact[b] % MOD * infact[a - b] % MOD;
    return ans;
}

LL lucas(LL a, LL b) {
   
    if (b == 0) return 1;
    return lucas(a / MOD, b / MOD) * get(a % MOD, b % MOD) % MOD;
}

void solve() {
   
    cin >> n >> l >> r;
    LL a = r - l + n + 1;
    LL b = r - l + 1;
    LL ans = lucas(a, b) - 1;
    ans = (ans % MOD + MOD) % MOD;
    cout << ans << '\n';
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    init();
    int T;
    cin >> T;

    while (T--) solve();

    return 0;
}