「PMOI-1」抽奖

GitHub 跳转原题关系图返回列表

按固定元素是否出现过来统计不同元素个数之和，把每个长度的贡献化成两段等比数列求和。

OJ: luogu

题目 ID: P7355

难度:普及/提高-

标签:数学计数推导快速幂思维

日期: 2026-06-20 15:17

题意

题面虽然写成“抽奖 + 体验卡 + 永久道具”，但形式化之后，问题其实是：

枚举所有长度在 [0,m] 之间的整数序列；
每个位置都可以填 1..n 中的一个数；
一个序列的权值等于 不同元素个数 + 1；
求所有这些序列权值之和，对 10^9+7 取模。

所以这题本质是一个数学计数题。

思路

先看一个最直接的暴力程序：

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const i64 MOD = 1000000007LL;
const int MAXM = 25;

int T;
int n, m;
int seq_arr[MAXM];
bool used[MAXM];
i64 ans;

// 暴力枚举所有长度为 len 的序列。
void dfs(int pos, int len) {
    if (pos > len) {
        int distinct_cnt = 0;
        memset(used, 0, sizeof(used));

        for (int i = 1; i <= len; i++) {
            if (!used[seq_arr[i]]) {
                used[seq_arr[i]] = true;
                distinct_cnt++;
            }
        }

        ans += distinct_cnt + 1;
        ans %= MOD;
        return;
    }

    for (int x = 1; x <= n; x++) {
        seq_arr[pos] = x;
        dfs(pos + 1, len);
    }
}

i64 solve_one() {
    ans = 0;
    for (int len = 0; len <= m; len++) {
        dfs(1, len);
    }
    return ans;
}

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

    cin >> T;
    while (T--) {
        cin >> n >> m;
        cout << solve_one() << '\n';
    }

    return 0;
}

暴力版做法很朴素：

枚举长度 0..m；
对每个长度枚举所有序列；
统计这个序列里出现了多少种数；
把 不同元素个数 + 1 累加到答案里。

它只能处理很小的数据，但特别适合帮助理解题意，也适合拿来对拍。

固定一个长度来想

设现在只考虑长度恰好为 k 的所有序列。

先看权值里的那个 +1：

长度为 k 的序列总数是 n^k；
每个序列都会贡献一个常数 1；
所以这部分总贡献是 n^k。

怎么统计不同元素个数之和

直接数“每个序列里有多少种不同元素”不太方便。
更好的办法是按元素拆贡献。

固定某个元素 x：

如果一个序列里出现过 x，那么它就会给“不同元素个数”贡献 1；
如果没出现过 x，贡献就是 0。

所以元素 x 的总贡献，等于：

“至少出现过一次 x 的序列个数”

这个数量可以用补集计数：

全部序列数：n^k
完全不含 x 的序列数：(n-1)^k

因此至少出现一次 x 的序列数是：

n^k - (n-1)^k

一共有 n 个元素，所以所有序列的“不同元素个数之和”就是：

n * (n^k - (n-1)^k)

得到固定长度的总贡献

把两部分合起来：

长度为 k 的总贡献 = n^k + n * (n^k - (n-1)^k)

整理可得：

= (n+1) * n^k - n * (n-1)^k

从单个长度推广到全部长度

题目要求长度从 0 到 m 全部都算，所以答案是：

ans = sum((n+1) * n^k - n * (n-1)^k), k=0..m

拆开就是：

(n+1) * (1 + n + n^2 + ... + n^m)
- n * (1 + (n-1) + (n-1)^2 + ... + (n-1)^m)

这两部分都是等比数列。

设公比为 r，则：

1 + r + r^2 + ... + r^m = (r^(m+1)-1)/(r-1)

因为 m 很大，所以幂要用快速幂。

一个必须注意的边界

如果 r ≡ 1 (mod 10^9+7)，那么分母 r-1 在模意义下等于 0，没有逆元。
这时不能再套上面的除法公式，而应该直接返回：

m + 1

代码里把这个情况放进 geometric_sum() 单独处理即可。

代码

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const i64 MOD = 1000000007LL;

int T;
i64 n, m;

// 计算 base^exp mod MOD。
i64 quick_pow(i64 base, i64 exp) {
    i64 ans = 1;
    base %= MOD;

    while (exp > 0) {
        if (exp & 1LL) {
            ans = ans * base % MOD;
        }
        base = base * base % MOD;
        exp >>= 1LL;
    }

    return ans;
}

// 计算 1 + ratio + ratio^2 + ... + ratio^m。
// 这里要特别处理 ratio ≡ 1 (mod MOD) 的情况，此时分母没有逆元。
i64 geometric_sum(i64 ratio, i64 m) {
    ratio %= MOD;
    if (ratio < 0) {
        ratio += MOD;
    }

    if (ratio == 1) {
        return (m + 1) % MOD;
    }

    i64 up = (quick_pow(ratio, m + 1) - 1 + MOD) % MOD;
    i64 down = (ratio - 1 + MOD) % MOD;
    i64 inv_down = quick_pow(down, MOD - 2);
    return up * inv_down % MOD;
}

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

    cin >> T;
    while (T--) {
        cin >> n >> m;

        // 对固定长度 k：
        // 1. 序列总数是 n^k；
        // 2. 不同元素个数之和，可以按“每种道具是否出现过”来统计。
        //    固定一种道具，它出现在序列中的方案数是 n^k - (n-1)^k。
        //    一共 n 种道具，所以不同元素个数总和是
        //    n * (n^k - (n-1)^k)。
        //
        // 因而长度为 k 的所有序列的权值和为：
        // n^k + n * (n^k - (n-1)^k)
        // = (n+1) * n^k - n * (n-1)^k
        //
        // 再把 k = 0..m 全部加起来，就是两段等比数列。
        i64 sum_pow_n = geometric_sum(n, m);
        i64 sum_pow_n_minus_1 = geometric_sum(n - 1, m);

        i64 ans = (n + 1) % MOD * sum_pow_n % MOD;
        ans = (ans - (n % MOD) * sum_pow_n_minus_1 % MOD + MOD) % MOD;

        cout << ans << '\n';
    }

    return 0;
}

复杂度

时间复杂度： $O(log m)$
空间复杂度： $O(1)$

总结

这题关键不是抽奖背景，而是把形式化题面真正读懂：

固定长度后，先拆出常数 1 的贡献；
“不同元素个数之和”改成按元素统计是否出现过；
对固定元素用补集计数；
最后得到两段等比数列，用快速幂求和。

一旦完成这一步拆分，整题就只剩下一个很短的数学公式了。

P7355 「PMOI-1」抽奖

题目描述

活动奖池中共有 $n$ 种道具，dead_X 有 $m$ 张兑奖券。一张兑奖券可以兑换成一次抽奖机会或 $114514$ 金币。

dead_X 决定将一部分兑奖券拿来抽奖，并将剩下的兑奖券兑换成金币。

在一次抽奖机会中，dead_X 会等概率得到所有奖池中一款道具的 $1919810$ 秒体验卡。

由于 dead_X 在活动中买了 VIP 卡，他可以在所有抽奖结束后选择一款抽奖得到的体验卡，将所有这种类型的体验卡上交，并得到对应种类的永久道具。

注意，dead_X 可以不使用这个功能，但是不可以使用多于一次。

有选择困难症的 dead_X 想知道，有多少种可能的活动结果。

两种活动结果不同，当且仅当 dead_X 获得的金币不同，或者在任何一次抽奖中获得的体验卡不同（即抽到体验卡形成的序列不同），或者获得的永久道具不同。

注意，抽奖中获得的都是体验卡，最后选择的永久道具和体验卡在哪一次抽出没有关系。

Update 2023.11.16：出题人看自己好几年前写的题面绷不住了，补一份形式化题面。

定义一个序列的权值是其不同元素个数 $+1$ ，例如 $[1,9,2,6,8,1,7]$ 的权值是 $7$ 。

对于所有长度 $\in[0,m]$ ，每个数 $\in [1,n]$ 的整数序列，求其权值和对 $10^9+7$ 取模的值。

输入格式

本题有多组数据。

第一行一个整数 $T$ ，代表数据组数。

对于每组数据，输入两个正整数 $n,m$ ，分别表示道具的种数和兑奖券的张数。

输出格式

输出共 $T$ 行，每行输出一个正整数，代表方案数对 $10^9+7$ 取模的值。

输入输出样例 #1

输入 #1

text

1
2
3
4
5
65
2 1
2 2
3 3
114 514
1919810 7872754

输出 #1

text

说明/提示

【样例解释】

以下为第二组测试数据所有可能的方案：

假设两种物品分别为 $A$ 和 $B$ 。

兑换 $229028$ 金币。
兑换 $114514$ 金币，获得 $A$ 体验卡。
兑换 $114514$ 金币，获得 $B$ 体验卡。
兑换 $114514$ 金币，获得 $A$ 永久道具。
兑换 $114514$ 金币，获得 $B$ 永久道具。
第一次获得 $A$ 体验卡，第二次获得 $A$ 体验卡。
第一次获得 $A$ 体验卡，第二次获得 $B$ 体验卡。
第一次获得 $B$ 体验卡，第二次获得 $A$ 体验卡。
第一次获得 $B$ 体验卡，第二次获得 $B$ 体验卡。
第一次获得 $A$ 体验卡，第二次获得 $A$ 体验卡，指定 $A$ 为永久道具。
第一次获得 $A$ 体验卡，第二次获得 $B$ 体验卡，指定 $A$ 为永久道具。
第一次获得 $B$ 体验卡，第二次获得 $A$ 体验卡，指定 $A$ 为永久道具。
第一次获得 $A$ 体验卡，第二次获得 $B$ 体验卡，指定 $B$ 为永久道具。
第一次获得 $B$ 体验卡，第二次获得 $A$ 体验卡，指定 $B$ 为永久道具。
第一次获得 $B$ 体验卡，第二次获得 $B$ 体验卡，指定 $B$ 为永久道具。

【数据范围】

Subtask1（10pts）： $n,m\leq5,T\le25$ ；
Subtask2（10pts）： $n=1$ ；
Subtask3（10pts）： $m=1$ ；
Subtask4（20pts）： $n,m\leq1000,T\leq 5$ ；
Subtask5（20pts）： $\sum m\leq10^6$ ；
Subtask6（30pts）：无特殊限制。

对于 $100\%$ 的数据满足， $1\le n,m\leq 10^9$ ， $1\le T\leq 10^5$ 。