基础数学算法-序列统计

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

题目：序列统计

给定一个整数区间 [L, R]，要求构造长度为 k 的单调不下降序列，其中每个元素都属于该区间。现需统计所有满足条件且长度在 1 到 N 之间的不同序列总数。

问题分析

考虑枚举序列的长度 k（1 ≤ k ≤ N）。对于固定的 k，问题转化为：有多少个满足 a ≤ a ≤ … ≤ a 且每个 a ∈ [L, R] 的序列？

由于数值间的相对大小才是关键，可通过平移将原区间 [L, R] 映射为 [0, R - L]。此时问题等价于求解非负整数序列满足：

0 ≤ a ≤ a ≤ … ≤ a ≤ R - L

引入差分变量：令 x = a，x = a - a，…，x = a - a，则所有 x ≥ 0，并且有：

x + x + … + x ≤ R - L

此即求该不等式下非负整数解的个数。为了便于处理，引入新变量 y = x + 1，则 y ≥ 1，原式变为：

y + y + … + y ≤ R - L + k

这类问题可通过“隔板法”思想解决。进一步地，通过组合恒等式的推导可得，当固定 k 时，方案数为组合数 C(R - L + k, k)。

因此总答案为对所有 k 从 1 到 N 求和：

ans = Σ_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, ab)，将其转换为：

C(m+1,m) + C(m+2,m) + … + C(m+n,m)

再根据递推关系 C(a,b) = C(a1,b) + C(a1,b1)，连续合并项后可得最终结果为：

C(m + n + 1, m + 1) 1

即最终答案为：

ans = C(R - L + N + 1, R - L + 1) 1

算法步骤

• 将原始问题通过变量替换和平移变换转化为非负整数解计数问题。
• 使用差分技巧将单调不下降序列转化为和受限的非负整数变量组。
• 应用组合数学中的隔板法与组合恒等式进行化简求和。
• 发现最终表达式可由单一组合数表示，避免逐项计算。
• 考虑到数据范围中 R 和 L 可达 10，但模数较小（10 + 3），采用 Lucas 定理高效计算大数组合数模小质数。

代码实现

预处理阶乘及其逆元表，结合 Lucas 定理完成组合数模运算。注意循环起始点及每一步取模操作以防止溢出。

#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 qpow(LL a, LL b) {
    LL res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

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

LL C(int a, int b) {
    if (b < 0 || a < b) return 0;
    return fact[a] * infact[b] % MOD * infact[a - b] % MOD;
}

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

int main() {
    init();
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> l >> r;
        LL m = r - l;
        LL ans = (lucas(m + n + 1, m + 1) - 1 + MOD) % MOD;
        cout << ans << '\n';
    }
    return 0;
}

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

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：基础数学 include RETURN Lucas while