组合计数进阶

有三个字母，其中两个是 A，一个是 B，能拼出多少种不同的字符串？如果把四个不同的选手拉到圆桌前开会，旋转一圈算同一种，又该数出多少种座次？

初学组合计数的同学，脑子里常常只有两个粗暴的动作：遇到题目先写个全排列 $n!$，发现算多了就随便找个数除一下。但除法是有“物理前提”的：只有当你数出来的每一个最终目标，都恰好、无偏差地被重复计算了相同的次数时，除法才具有数学意义！

在这一讲中，我们要沿着“我究竟数了什么、每一个方案被重复数了几次”这条主线，把二项式定理的代数本质、多重集与圆排列的对称性消去，以及信奥中极其锋利的“抽屉存在性证明”彻底拆解通透。

一、二项式定理：代数展开的本质是“在每个括号里做选择”

很多同学背二项式定理时只记住了那一长串公式，但一遇到带负号、带系数的变形就晕头转向。我们先不看公式，回到最质朴的算式：$(a+b)^3$。

初中代数告诉你，它是三个括号连乘：

展开这个式子的物理过程，其实就是从第 1 个括号选一项、第 2 个括号选一项、第 3 个括号选一项，然后乘在一起。

现在问你：展开合并同类项后，$a^2b$ 这一项的系数为什么是 3？

• 要凑出 $a^2b$，意味着在 3 个括号中，必须恰好有 1 个括号贡献 $b$，其余 2 个括号贡献 $a$。
• 你在 3 个括号里挑出 1 个贡献 $b$，总共有多少种挑选方案？显然是 $\binom{3}{1} = 3$ 种！
• 无论你挑的是第 1 个、第 2 个还是第 3 个括号，最终相乘的结果全都是 $a^2b$。同类项合并，系数自然就是 3。

推广到 $n$ 个括号相乘，二项式定理的本来面目就彻底水落石出了：

物理意义：组合数 $\binom{n}{k}$ 根本不是凭空捏造出来的公式，它就是在数：在全部 $n$ 个括号中，究竟挑哪 $k$ 个括号贡献第二项 $b$。 剩下的 $n-k$ 个括号别无选择，只能贡献第一项 $a$。当 $n=0$ 时，没有任何括号可选，空乘积为 1，与代数上的零次幂完全统一。

1. 带系数与符号时，别只抄组合数！

考场上最常见的低级失误，就是一看到求展开项系数，脑子一热直接输出组合数 $\binom{n}{k}$。

实战陷阱：求 $(2x+3y)^4$ 展开式中 $x^2y^2$ 项的系数。

• 第一步：做选择。在 4 个括号里选 2 个贡献 $3y$（剩下 2 个贡献 $2x$），选法确实有 $\binom{4}{2} = 6$ 种。
• 第二步：算权重！每一个括号挑出 $2x$ 时自带系数 2，挑出 $3y$ 时自带系数 3。每一次成功的挑选，都会产生：
  $$(2x)^2 \cdot (3y)^2 = 4x^2 \cdot 9y^2 = 36x^2y^2$$
• 最终系数不是 6，而是组合数与项权重的乘积：
  $$\binom{4}{2} \cdot 2^2 \cdot 3^2 = 6 \times 4 \times 9 = 216$$

如果是 $(a-b)^n$，只需要把第二项直接看作 $(-b)$。选择了几次第二项，就累乘几次 $(-1)$，负号会随着选取的次数 $k$ 的奇偶性交替出现。

2. 双向计数：用组合意义秒杀恒等式

二项式定理不仅能用来算系数，它还是证明组合恒等式的利器。与其在草稿纸上进行繁复的代数变形，不如问一句：左右两边是不是在用两种不同顺序数同一批东西？

恒等式一：全部子集计数

• 左边视点：我们把大小为 $n$ 的集合的所有子集，按“子集元素个数为 $k$”严格分类，把大小为 $0, 1, \dots, n$ 的子集数一一累加。
• 右边视点：集合里的每一个元素独立面对选择——要么进子集，要么不进，共有 2 种可能。$n$ 个元素总共产生 $2^n$ 种不同组合。
• 两边数的是同一个集合的全部子集，答案必然相等！

恒等式二：选拔委员会与主席

• 左边视点：先选一个包含 $k$ 个人的委员会（$\binom{n}{k}$ 种），再在委员会内部民主选举 1 个人担任主席（$k$ 种选法）。
• 右边视点：打破思维定势，我们直接先在全部 $n$ 个人里钦定 1 个人当主席（$n$ 种选法）；剩下的 $n-1$ 个人去留随意，自由决定是否加入该委员会（$2^{n-1}$ 种）。
• 两种挑选顺序数出来的“委员会+主席”配置完全等价，恒等式自然成立。

二、完整程序一：求指定项的系数

1. 输入输出与数据范围

• 输入格式：一行四个整数 n k a b，求 $(ax+by)^n$ 展开式中 $x^{n-k}y^k$ 的系数，答案对 $10^9+7$ 取模。
• 数据范围：$0 \le n \le 10^6$，$-10^6 \le k \le 10^6$，$|a|, |b| \le 10^9$。若 $k < 0$ 或 $k > n$，直接输出 0。
• 样例输入：
  text复制代码

  4 2 2 3
  

• 样例输出：
  text复制代码

  216
  

2. 算法实现思路

直接计算 $\binom{n}{k} a^{n-k} b^k \pmod{10^9+7}$。由于 $MOD = 10^9+7$ 为质数且 $n < MOD$，分母的逆元直接用费马小定理 power(den, MOD - 2) 计算。负数系数输入前必须通过 (x % MOD + MOD) % MOD 规范到非负区间；空乘积（包括 $0^0$）统一规定返回 1。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=1000000007;
const int N=1000005;

int fac[N];

int power(int a,int b){
	int res=1;
	a=(a%MOD+MOD)%MOD;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}

void solve(){
	int n,k,a,b;
	if(!(cin>>n>>k>>a>>b)) return;
	
	// 范围之外不可能凑出对应次数，系数直接为 0
	if(k<0 || k>n){
		cout<<0<<'\n';
		return;
	}
	
	a=(a%MOD+MOD)%MOD;
	b=(b%MOD+MOD)%MOD;
	
	// 预处理阶乘
	fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
	
	// 计算组合数 C(n, k)
	int den=fac[k]*fac[n-k]%MOD;
	int c=fac[n]*power(den,MOD-2)%MOD;
	
	// 累乘项权重 a^(n-k) * b^k
	int ans=c*power(a,n-k)%MOD*power(b,k)%MOD;
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

三、多重集排列：先贴标签，再把标签擦掉

回到开头的引子：两个 A 和一个 B，究竟能拼出多少种不同字符串？

如果我们把这两个 A 盲目当成完全不同的对象，按全排列公式算出来是 $3! = 6$ 种。可是稍微动笔排一下就知道，真正不同的字符串只有 3 种：AAB、ABA、BAA。

为什么计算结果不多不少，恰好翻了整整一倍？

1. 核心思维：贴标签与擦标签

面对存在相同元素的排列，信奥中最通用也最严谨的思维模型是贴标签法：

1. 第一步（贴标签）：把两个原本相同的 A 强行看成不同的，给它们贴上下标标签，变成 $A_1$ 和 $A_2$。此时 $A_1, A_2, B$ 是三个互不相同的元素，全排列总数是 $3! = 6$ 种：
   • 组 1：$A_1A_2B$ 与 $A_2A_1B$
   • 组 2：$A_1BA_2$ 与 $A_2BA_1$
   • 组 3：$BA_1A_2$ 与 $BA_2A_1$
2. 第二步（擦标签）：现实中两个 A 没有差别，我们把标签撕掉。你会发现：无论两个 A 落在什么位置，$A_1$ 与 $A_2$ 互换产生的 2 种带标签排列，在擦掉标签后全都坍缩成了同一种字符串！
3. 第三步（等量除法）：因为每一个合法字符串都不多不少、恰好对应了 $2! = 2$ 种带标签状态，这种重复是绝对均等的，因此最终答案就是 $\frac{3!}{2!} = 3$。

2. 一般化多重集排列公式

假设我们有 $r$ 种不同的字符，第 $i$ 种字符出现的次数为 $c_i$，总字符数为 $N = \sum_{i=1}^r c_i$。

• 先贴标签：把所有相同字符都编上各不相同的编号，总共有 $N!$ 种排列。
• 再擦标签：对于第 $i$ 类字符，它的 $c_i$ 个相同字符无论占了哪几个位置，内部相互调换都有 $c_i!$ 种不同的标签编号方式。各类字符的标签调换彼此独立（满足乘法原理）。
• 等量坍缩：每一个合法的无标签字符串，在带标签的全排列中都被精确重复计算了 $c_1! \times c_2! \times \cdots \times c_r!$ 次！

因此，不同线性字符串的总数为：

另一个推导视角（选座位）： 我们在纸上画出 $N$ 个空位。

• 先从 $N$ 个空位中选 $c_1$ 个放第一类字符：$\binom{N}{c_1}$ 种；
• 再从剩下的 $N-c_1$ 个空位中选 $c_2$ 个放第二类字符：$\binom{N-c_1}{c_2}$ 种；
• …… 把所有组合数连乘展开：
  $$\frac{N!}{c_1!(N-c_1)!} \times \frac{(N-c_1)!}{c_2!(N-c_1-c_2)!} \times \cdots \times \frac{c_r!}{c_r!0!} = \frac{N!}{c_1! c_2! \cdots c_r!}$$
  中间所有的“剩余项”全部分子分母对消，两种截然不同的物理模型导向了同一个极简公式！

边界细节：如果有某类字符的出现次数 $c_i = 0$，因为 $0! = 1$，它对分母的贡献为 1，完全不影响结果。若全部 $c_i = 0$，空串排列方案数是 1，绝不是 0。

四、完整程序二：多重集全排列计数

1. 输入输出与数据范围

• 输入格式：第一行一个整数 $r$（$1 \le r \le 10^5$），表示字符种类数；第二行给出 $r$ 个非负整数 $c_i$，表示每种字符的数量，保证字符总数 $N = \sum c_i \le 10^6$。输出不同线性字符串数量对 $10^9+7$ 取模的结果。
• 样例输入：
  text复制代码

  3
  2 2 1
  

• 样例输出：
  text复制代码

  30
  

2. 算法实现思路

先读入各类别数量并求和得到总长度 $N$。单次线性递推预处理阶乘数组 fac。分母为各类别阶乘的模积，最后通过单次费马小定理计算分母的模逆元，时间复杂度 $O(N + r + \log MOD)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=1000000007;
const int N=1000005;

int c[N],fac[N];

int power(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}

void solve(){
	int r;
	if(!(cin>>r)) return;
	
	int n=0;
	for(int i=1;i<=r;i++){
		cin>>c[i];
		n+=c[i];
	}
	
	// 预处理 0 到 n 的阶乘
	fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
	
	// 计算分母: c_1! * c_2! * ... * c_r!
	int den=1;
	for(int i=1;i<=r;i++){
		den=den*fac[c[i]]%MOD;
	}
	
	// 分子乘上分母的逆元
	int ans=fac[n]*power(den,MOD-2)%MOD;
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

五、围成一圈：打破线性的“圆排列”

从“排成一排”到“围成一圈”，规则发生了翻天覆地的变化。

1. 基础圆排列：仅旋转等价

场景：$n$ 个不同的人围坐一张没有任何标记的圆桌，桌子旋转后看起来一样的算同一种坐法。

• 如果把他们排成一排，有 $n!$ 种排列。
• 但围成一圈后，任意一个固定的圆座次，如果你从不同的人开始顺时针报数，能读出 $n$ 种不同的线性字符串（例如 ABCD 顺时针转动分别产生 BCDA、CDAB、DABC）。
• 每一种圆排列都被线性排列均等地多算了 $n$ 次。因此答案是：
  $$\frac{n!}{n} = (n-1)!$$

💡 破题定锚法（极其关键的思维技巧）：
面对旋转对称性，最快的方法就是主动破坏对称性！既然大家都在旋转，我们随便挑一个人（比如小明），强行把他“钉死”在最北边的座位上不动。此时圆桌的旋转对称性荡然无存，剩下的 $n-1$ 个人在剩下的 $n-1$ 个固定座位上排列，方案数直接就是 $(n-1)!$。

2. 旋转 vs 镜像翻转（项链与手镯）

如果场景从“圆桌”变成了“珠子串成的手镯”，事情又变了：手镯可以拿起来翻个面看。

• 固定 A 之后，顺时针读是 A-B-C-D，翻过来从反面看就成了 A-D-C-B。
• 如果题目只允许纯旋转，A-B-C-D 和 A-D-C-B 是两种不同的方案（邻居相同但左右手方向相反）；
• 如果题目明确说明翻转（镜像反射）也视为相同：
  • 当 $n \ge 3$ 时，每一个圆排列与它的轴对称镜像两两配对，方案数在圆排列的基础上再次折半：
    $$\frac{(n-1)!}{2}$$
  • 特判边界：当 $n=1$ 或 $n=2$ 时，翻转并不会产生新的相对空间关系，答案依然是 1，不能盲目套公式除以 2！

3. 灵魂警示：有重复元素时，为什么绝对不能直接除以 $n$？

很多同学学完多重集排列和圆排列，就会耍小聪明拼凑公式：“如果有重复元素围成一圈，先算多重集排列 $\frac{N!}{\prod c_i!}$，再除以 $N$ 不就行了？”

绝对不行！这是考场上最致命的假算法！

我们拿 2 个 A 和 2 个 B 围成一圈做实验：

• 线性排列有 $\frac{4!}{2!2!} = 6$ 种：AABB, BBAA, BAAB, ABBA, ABAB, BABA。
• 如果你直接拿 6 除以 4，会算出 $1.5$ 种，这在离散数学里是荒谬的！
• 为什么等量除法失效了？
  • 看 AABB：顺时针旋转分别得到 AABB, BBAA, BAAB, ABBA 共 4 个不同线性串，它的周期是 4，旋转等价类大小确实是 4；
  • 看 ABAB：旋转 1 格得到 BABA，再旋转 1 格又变回了 ABAB！它自身的最小循环节只有 2，旋转等价类的大小只有 2！
• 物理本质：当元素存在重复时，各个排列自身的内部对称性（周期）不一致，导致它们在旋转时“膨胀”出的线性排列个数不再相等！等量除法的基石被彻底粉碎。

(注：带重复元素的项链计数必须依靠 Pólya 计数定理或 Burnside 引理按周期分类统计。在普及和提高阶段，你必须牢记：没有等量重复，绝不能盲目做除法！)

六、有上界的隔板法配合容斥（选学）

(先修提示：本小节需要熟练掌握求方程 $x_1+x_2+\dots+x_M = N$ 非负整数解的基础隔板法，以及基础的容斥原理。)

痛点场景：将 $N$ 个相同的球分给 $M$ 个不同的人。如果不限制上限，方案数就是隔板法求非负整数解的 $\binom{N+M-1}{M-1}$。但如果题目加了一个极为苛刻的条件：每个人最多只能拿 $K$ 个球，该怎么办？

面对上限限制，正向使用隔板法是行不通的。这时候，我们必须用容斥原理来“破坏规则”。

推导过程：

1. 全局宇宙：不管上限，所有人随便拿，总方案数为 $\binom{N+M-1}{M-1}$。
2. 定义违规：什么叫违规？第 $i$ 个人拿了超过 $K$ 个球，也就是他至少拿了 $K+1$ 个球。
3. 钦定违规者： 假设我们要强制让某 1 个人违规。我们先从 $M$ 个人里挑出这个人（$\binom{M}{1}$ 种选法），然后直接往他手里塞 $K+1$ 个球！ 此时，总球数还剩 $N - (K+1)$ 个。剩下的球不管怎么随便分（即使他又拿到了球），他手里的球绝对超过了 $K$。因此，剩余球随意分配的方案就是 $\binom{N - (K+1) + M - 1}{M - 1}$。
4. 容斥交替： 强制 1 人违规可能会算重（比如两人同时违规被算了两次），所以我们要减去 1 人违规，加上 2 人违规，减去 3 人违规…… 如果有 $j$ 个人同时违规，我们就先给这 $j$ 个人每人塞 $K+1$ 个球，剩下的 $N - j(K+1)$ 个球用基础隔板法分。选出 $j$ 个人的方案是 $\binom{M}{j}$。

最终的求和公式为：

【手算小例子】 $N=5$ 个相同球分给 $M=3$ 个人，每人最多拿 $K=2$ 个。穷举合法方案只有 (1,2,2), (2,1,2), (2,2,1) 共 3 种。 用公式计算：

• $j=0$ (无人强制违规)：$\binom{5+3-1}{3-1} = \binom{7}{2} = 21$。
• $j=1$ (钦定 1 人违规)：选 1 人发 3 个球，剩 2 个球随便分。$3 \times \binom{2+3-1}{3-1} = 3 \times \binom{4}{2} = 18$。
• $j=2$ (钦定 2 人违规)：选 2 人各发 3 个球，共需 6 个球，但总共只有 5 个球。剩余球数 $< 0$，不可能发生，方案数为 0。
• 最终结果：$21 - 18 = 3$ 种。公式完美命中！

核心代码要点： 下面只给求和循环，不是独立程序。复用《数学基础》·组合数 $O(1)$ 查询中的 C(n,m)，将组合数表预处理到至少 n+m，并满足 n+m<mod。变量 n,m,k 分别是球数、人数和每人的上限，均用 long long；小写名字不要与数组容量常量 N 混用。

int ans = 0;
for(int j = 0; j <= m; j++){
	int rem = n - j * (k + 1);
	if(rem < 0) break; // 球不够发了，后面的 j 更不可能合法
	
	int ways = C(m, j) * C(rem + m - 1, m - 1) % mod;
	if(j % 2 == 1){
		ans = (ans - ways + mod) % mod;
	} else {
		ans = (ans + ways) % mod;
	}
}

七、范德蒙德恒等式与分类计数（选学）

在信奥计数推导中，有一个常客恒等式叫范德蒙德卷积（Vandermonde's Identity）：

分类解释： 想象你要从 $n$ 个男生和 $m$ 个女生中，总共挑选 $p$ 个人组成一个省队。

• 右边视点（宏观）：我不分男女，一共 $n+m$ 个人，直接挑 $p$ 个，方案数显然是 $\binom{n+m}{p}$。
• 左边视点（微观分类）：省队里的男生人数一定是 $0, 1, 2, \dots, p$ 中的某一个。假设有 $k$ 个男生，那女生必然得有 $p-k$ 个。
  • 挑男生：从 $n$ 个人里挑 $k$ 个，有 $\binom{n}{k}$ 种。
  • 挑女生：从 $m$ 个人里挑 $p-k$ 个，有 $\binom{m}{p-k}$ 种。
  • 搭配起来方案数就是 $\binom{n}{k}\binom{m}{p-k}$。 把所有可能的 $k$ 对应的方案数全部加起来，必然无遗漏、无重复地等于总方案数。

进一步延伸： 当 $n=m=p$ 时，公式变成了：

八、球盒模型的同异边界清点

遇到球放进盒子的题目，不要马上乱套公式。最稳的思路是先在心里默念两句灵魂拷问：

1. 球是一样的，还是不一样的？
2. 盒子是一样的，还是不一样的？

球不同、盒不同、非空的满射计数，见《经典计数模型》·球盒问题。如果盒子也相同，再把这个计数除以 $m!$，得到的就是第二类斯特林数；这里先不展开它的递推，重点辨清下面几种容易混的模型。

1. 球同，盒不同，允许空盒

这就是最经典的求非负整数解问题。

• 物理操作：$n$ 个相同的球，用 $m-1$ 块隔板隔开。
• 答案：$\binom{n+m-1}{m-1}$。

2. 球不同，盒不同，允许空盒

极其容易想复杂的一个送分边界！

• 物理操作：每个球长得都不一样，它们是自由的。第 1 个球有 $m$ 个盒子可以进，第 2 个球也有 $m$ 个盒子可以进……每个球的决策互相独立。
• 答案：$m^n$。代码里就是一个快速幂。

3. 球同，盒同，允许空盒（整数划分模型）

这是最容易跟隔板法搞混的模型。因为盒子一模一样，放成 (1, 2) 和 (2, 1) 在这里算是同一种分配方案！因为没有盒子编号区分顺序，隔板法在这里彻底失效。

• 物理操作：把正整数 $n$ 拆分成最多 $m$ 个无序的正整数之和，剩下的位置就是空盒。
• 状态转移（剥洋葱）： 设 dp[i][j] 表示将 i 个相同球放入 j 个相同盒子的方案数。面对 j 个盒子，只有两种宏观情况：
  1. 至少有一个空盒：既然盒子都一样，那个空盒子留着也没用，不如当它不存在！这部分的方案数完全等价于把 i 个球放进 j-1 个盒子，即 dp[i][j-1]。
  2. 一个空盒都没有：既然不许有空盒，我们干脆先给所有 j 个盒子“垫底”各发 1 个球！发完之后，总球数还剩 i-j 个。这剩下的 i-j 个球再放进 j 个盒子里随便分配，方案数即为 dp[i-j][j]。（注意前提是 $i \ge j$）
• 转移方程：dp[i][j] = dp[i][j-1] + dp[i-j][j]。

4. 完整程序三：整数划分 DP

输入输出与数据范围： 一行两个整数 n 和 m，表示将 n 个相同球放进 m 个相同盒子的方案数，结果对 $10^9+7$ 取模。$1 \le n, m \le 1000$。

• 样例输入：
  text复制代码

  5 3
  

• 样例输出：
  text复制代码

  5
  

  (注：具体方案为 (5,0,0), (4,1,0), (3,2,0), (3,1,1), (2,2,1))

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=1000000007;
const int N=1005;

int dp[N][N];

void solve(){
	int n,m;
	if(!(cin>>n>>m)) return;
	
	// 初始化：0个球放进任何大于等于0的盒子里都是1种方案（全空）
	for(int j=0;j<=m;j++){
		dp[0][j]=1;
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			// 至少有一个空盒的情况
			dp[i][j] = dp[i][j-1];
			
			// 如果球数够垫底，加上没有空盒的情况
			if(i>=j){
				dp[i][j] = (dp[i][j] + dp[i-j][j]) % MOD;
			}
		}
	}
	
	cout<<dp[n][m]<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

九、抽屉原理：不求精确数量，也能一锤定音的“存在性魔法”

前面讲的都是“精准数出有多少种”，但信奥中有一类极高频的难题，根本不问你有多少种，而是让你证明某种极端的条件一定存在。这就是抽屉原理（鸽巢原理）。

1. 基础模型与极端反证

核心定律：将 $N$ 个物体放进 $m$ 个抽屉（$m \ge 1$），则至少存在一个抽屉，里面包含不少于 $\lceil N/m \rceil$ 个物体。

物理推导（反证法）：
如果每个抽屉里装的物体数量都严格小于 $\lceil N/m \rceil$，哪怕每个抽屉都装满临界上限，总数也绝不可能达到 $N$，必然装不下。

• 反向构造保底：如果要确保至少有一个抽屉里装了 $k+1$ 个物体，最坏情况下我们先把每个抽屉都填满 $k$ 个（共 $km$ 个），此时只需要再多添 1 个物体，就能铁证如山地触发条件。因此最少需要准备 $km + 1$ 个物体。

2. 抽屉的竞赛级抽象：把“同余性质”当成抽屉

在实战中，题目绝不会在面上画几个箱子让你装球。物体的形态往往是数字、点或者前缀和，而抽屉则是它们的代数性质（模数余数、坐标奇偶性等）。

经典模型：前缀和与连续子段和整除

命题：给定任意 $n$ 个正整数 $a_1, a_2, \dots, a_n$，必然存在一段非空的连续区间 $[l, r]$，使得该区间的元素和能被 $n$ 整除！

很多同学第一反应是做复杂的动态规划，其实利用抽屉原理一招秒杀：

1. 构造前缀和：定义 $S_k = \sum_{i=1}^k a_i$。加上空前缀 $S_0 = 0$，我们手里一共有 $n+1$ 个前缀和：
   $$S_0, S_1, S_2, \dots, S_n$$
2. 定义抽屉：任意整数除以 $n$ 的余数只有 $0, 1, 2, \dots, n-1$ 共 $n$ 种可能。我们将这 $n$ 种余数看成 $n$ 个抽屉。
3. 入巢触发：现在有 $n+1$ 个前缀和（物体），丢进 $n$ 个余数抽屉里。由抽屉原理，必然至少有两个前缀和的余数完全相同！
4. 区间相减：设这两个前缀和为 $S_i$ 和 $S_j$（且 $0 \le i < j \le n$），因为它们模 $n$ 同余，两式相减：
   $$S_j - S_i \equiv 0 \pmod n$$
   而根据前缀和的物理定义，$S_j - S_i$ 恰好就是连续区间 $[i+1, j]$ 的所有元素之和！由于 $i < j$，该区间非空。证毕！

这个数学证明不仅严丝合缝，更直接指明了算法实现：我们只需要开一个桶数组 pos[rem] 记录每个余数第一次出现的下标，扫一遍前缀和，一旦发现撞车，答案立即当场锁定。

十、渐进式实战与思维练习

1. 练习 1：二项式展开边界实战

• 题目描述：沿用程序一的代码逻辑，输入 n k a b，求解展开式指定项系数。
  • 测试样例 1：输入 3 1 1 -1。求 $(x-y)^3$ 中 $x^2y$ 的系数。理论结果为 $-3$，在模 $10^9+7$ 规范化后输出 1000000004。
  • 测试样例 2：输入 2 3 1 1。询问的 $y$ 的次数 $k=3 > n=2$，已超出多项式上限，程序应敏锐输出 0。
• 训练指引：检验代码在负数系数规范化 (x % MOD + MOD) % MOD 以及非法次数区间的边界防御能力。

2. 练习 2：多重集手推与空集边界

• 题目描述：沿用程序二的代码逻辑，输入种类数与各字符数量。
  • 测试样例 1：第一行输入 2，第二行输入 2 1，输出 3（对应 AAB, ABA, BAA 三种可能）。
  • 测试样例 2：第一行输入 2，第二行输入 0 0，输出 1。
• 训练指引：在草稿纸上真正写出测试样例 1 的全过程，体会“擦标签”的合并逻辑；同时理解为什么所有计数为 0 时对应唯一的空字符串，答案是 1 而不是 0。

3. 练习 3：三种等价关系的降维对比（独立手算）

• 题目描述：有 4 个完全不同的人 A, B, C, D。请分别在以下三种规则下算出座次方案数：
  1. 每个人坐在贴有 1, 2, 3, 4 号标签的固定椅子上；
  2. 围成圆桌，仅仅旋转后相对位置重合的视为同一种方案；
  3. 制作成手镯珠串，旋转和翻转（镜像反射）均视为同一种方案。
• 手算指引：
  1. 编号固定无对称性，答案为 $4! = 24$；
  2. 仅纯旋转对称，答案为 $(4-1)! = 6$；
  3. 旋转加翻转对称，答案为 $\frac{(4-1)!}{2} = 3$。
  • 核心反思：每一次除以一个数，你必须在草稿纸上圈出到底哪几个方案因为哪种对称性被等量合并成了一组。

4. 练习 4：抽屉原理的算法构造题（区间整除定位）

• 题目描述：输入一个正整数 $n$（$n \le 10^5$）和随后 $n$ 个正整数 $a_1, a_2, \dots, a_n$。请在 $O(n)$ 时间内输出任意一对下标 l r（1-based），使得子段和 $\sum_{i=l}^r a_i$ 能被 $n$ 整除。
• 样例输入：
  text复制代码

  4
  2 3 1 6
  

• 样例输出：
  text复制代码

  2 3
  

  (注：第 2 到第 3 项为 3 和 1，和为 4，能被 4 整除；输出 1 4 同样合法)
• 破题引导：开一个全局数组 pos 初始化为 -1，置 pos[0] = 0 表示空前缀和模 $n$ 为 0 出现在位置 0。一边读入一边维护前缀和取模 cur = (cur + a[i]) % n。若 pos[cur] != -1，说明此前在 pos[cur] 处出现过相同余数，当前区间即为 [pos[cur] + 1, i]，直接输出并退出程序；否则记录 pos[cur] = i。利用抽屉原理，循环绝不会无解退出。