编号 - 题目列表

题意

第 i 只兔子要从 1..Mi 选择编号，所有编号互不相同。求编号方案数模 1e9+7。

思路

把上限从小到大排序。处理第 used 只兔子时，前面已经选出的 used 个编号都不超过当前上限，因此当前共有 limit-used 个可选编号。

根据乘法原理，把所有选择数相乘。若某一步 limit-used<=0，方案数就是零。

例如 [5,8] 的选择数依次是 5 和 7，答案 35。

Python 知识

sorted 返回升序上限列表。
enumerate(limits) 同时给出已使用编号数和当前上限。
max(0,limit-used) 把不可能状态变成乘积中的零。
math.prod 直接计算生成器产生的所有选择数，最后统一取模。
/home/rainboy/mycode/hugo-blog/content/program_language/python/sorting_and_ordering.md：排序与顺序计数。
/home/rainboy/mycode/hugo-blog/content/program_language/python/map_reduce_filter.md：生成器乘积归约。

代码

python

1
2
3
4
5
6
7
8
9
10import sys
from math import prod


MOD = 1_000_000_007


data = list(map(int, sys.stdin.buffer.read().split()))
limits = sorted(data[1:])
print(prod(max(0, limit - used) for used, limit in enumerate(limits)) % MOD)

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29/**
 * P1866 编号
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 55;
const int MOD = 1000000007;

int a[MAXN], n;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    long long ans = 1;
    for (int i = 1; i <= n; ++i) {
        // 第 i 小上限：还剩 a[i] - (i-1) 个数可选
        ans = ans * max(0, a[i] - (i - 1)) % MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

复杂度

排序时间 $O(n\log n)$ ，乘积 $O(n)$ ，空间复杂度 $O(n)$ 。

总结

先处理限制最紧的对象后，已经占用的编号一定都在当前范围内，剩余选择数便可直接计算。

编号

目录

题意

思路

Python 知识

代码

复杂度

总结