2026IRC智能竞技大赛真题：大组合数取模解析

赛事锚点：四川省第四届IRC智能竞技大赛（信息学赛项）｜原创算法题 · C++/Python 双版 · 七考点拆解

一、赛题背景

在 IRC 智能竞技大赛的信息学赛项中，有这样一道经典计数题：赛场准备了 n 种不同口味的能量糖果排成一排，要求从中恰好选出 k 种装进一份礼盒。问：在模一个给定大素数 p 的意义下，合法的选法总数有多少？当 n、k 大到 10¹⁸ 量级时，直接算阶乘显然会爆掉，这就需要用卢卡斯定理（Lucas Theorem）把大数按 p 进制逐位拆开再组合。

  

二、题目描述

输入三个整数 n, k, p（p 为素数，且 p ≤ 100000），求 C(n, k) mod p。数据范围：0 ≤ k ≤ n ≤ 10¹⁸。若 k > n，答案为 0。

• 输入
  ：一行三个整数 n、k、p。
• 输出
  ：一个整数，表示 C(n, k) 对 p 取模的结果。
• 样例
  ：输入 100 3 100003，输出 161700（即 C(100,3)=161700，恰好小于 100003，无需取模）。

三、核心算法：卢卡斯定理

卢卡斯定理指出，对于素数 p：

C(n, k) ≡ C(n mod p, k mod p) × C(⌊n/p⌋, ⌊k/p⌋) (mod p)

也就是说，把 n、k 写成 p 进制后，每一位上的组合数相乘再模 p 即可。当 k=0 时递归终止返回 1。由于每一位的 n mod p、k mod p 都 < p，我们只需在 0..p-1 范围内预处理阶乘与阶乘逆元，就能 O(1) 求出小范围组合数 C(a,b) mod p，整体复杂度 O(p + log_p n)。

  

四、参考代码（C++）

#include <bits/stdc++.h> using namespace std; typedef long long ll;  ll MOD; vector<ll> fact, invfact;  // 快速幂：a^b mod MOD ll power(ll a, ll b) {     ll res = 1 % MOD;     a %= MOD;     while (b) {         if (b & 1) res = res * a % MOD;         a = a * a % MOD;         b >>= 1;     }     return res; }  // 预处理阶乘与逆元阶乘（p 为给定素数，p <= 1e5） void build(ll p) {     MOD = p;     fact.assign(p, 1);     for (ll i = 1; i < p; ++i)         fact[i] = fact[i - 1] * i % MOD;     invfact.assign(p, 1);     invfact[p - 1] = power(fact[p - 1], MOD - 2);     for (ll i = p - 1; i > 0; --i)         invfact[i - 1] = invfact[i] * i % MOD; }  // 小范围组合数 C(n, k) mod MOD（n, k < MOD） ll comb(ll n, ll k) {     if (k < 0 || k > n) return 0;     return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD; }  // 卢卡斯定理：把 n、k 按 p 进制逐位拆分 ll lucas(ll n, ll k) {     if (k == 0) return 1;     return comb(n % MOD, k % MOD) * lucas(n / MOD, k / MOD) % MOD; }  int main() {     ll n, k, p;     cin >> n >> k >> p;   // n, k <= 1e18；p 为素数且 p <= 1e5     build(p);     cout << lucas(n, k) << endl;     return 0; }

五、参考代码（Python）

def solve(n, k, p):     # 预处理阶乘与逆元阶乘（p 为给定素数，p <= 1e5）     fact = [1] * p     for i in range(1, p):         fact[i] = fact[i - 1] * i % p     invfact = [1] * p     invfact[p - 1] = pow(fact[p - 1], p - 2, p)     for i in range(p - 1, 0, -1):         invfact[i - 1] = invfact[i] * i % p      def comb(n, k):         if k < 0 or k > n:             return 0         return fact[n] * invfact[k] % p * invfact[n - k] % p      def lucas(n, k):         if k == 0:             return 1         return comb(n % p, k % p) * lucas(n // p, k // p) % p      return lucas(n, k)   # 示例：从 100 个里选 3 个，模 100003 print(solve(100, 3, 100003))   # 输出 161700

六、考点拆解（7 个）

1. 组合恒等式
   ：C(n,k)=C(n,n-k)，取较小值可减半枚举。
2. 模逆元
   ：用费马小定理 pow(den, p-2, p) 求分母逆元（p 为素数）。
3. 阶乘预处理
   ：O(p) 预处理 fact 与 invfact，小范围组合数 O(1) 查询。
4. 卢卡斯拆分
   ：n、k 同时除以 p 递归，把大数拆成 p 进制位。
5. 越界判定
   ：k>n 或 k<0 时组合数为 0，必须在 comb 里先判断。
6. 数据范围
   ：n,k 用 long long / 大整数，避免乘法溢出。
7. k=0 终止
   ：递归边界返回 1，否则会死循环或算错。

七、互动引导

🤔 想一想：如果题目要求计算 C(n,k) mod p 但 p 不是素数（比如合数），费马小定理就不成立了，这时该用什么方法？欢迎在评论区聊聊你的思路，也可以把本题改编成"从 n 排糖果里每行选 1 颗"的二维版本挑战一下！

📚 免费少儿编程资料（夸克网盘领取）

以下资料来自夸克网盘分享。个人号链接暂不支持直接点击，请长按或复制下方链接，打开夸克网盘 App / 网页粘贴即可保存：

1. 1. 全国青少年信息素养大赛复赛集训题目Python&C++.docx
   https://pan.quark.cn/s/93995d3cb150
2. 2. 2024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdf
   https://pan.quark.cn/s/da97b5dbf75d
3. 3. Python背记手册.pdf
   https://pan.quark.cn/s/7568ae9ca92b
4. 4. Python课程
   https://pan.quark.cn/s/a94bf02d00c6
5. 5. 2024信息素养大赛图形化复赛集训题答案3-9
   https://pan.quark.cn/s/6ccab7ec3cbc
6. 6. 2025年03月份电子学会考级真题
   https://pan.quark.cn/s/4403c4228912
7. 7. 2025全国青少年信息素养大赛赛项说明
   https://pan.quark.cn/s/d9d0df4a9f29
8. 8. 青少儿信息素养大赛编程资料
   https://pan.quark.cn/s/4ab6bd83be8a

资料持续更新，关注本号第一时间获取新分享。