每年秋招季腾讯的笔试编程题总能在技术社区掀起一波又一波讨论。2017年秋招那道“小Q的歌单”到现在还经常被刚准备校招的同学翻出来问。别看它题干短得像小学生应用题背后藏着的组合计数思想放到今天依然是各大厂笔试面试的高频考点。我当年刷牛客的时候在这道题上栽过跟头后来复盘才发现题目本身不难难的是你愿不愿意先把“数学规律”捋清楚再动手写代码。这篇博文就以这道经典题为引子把它从审题、暴力思路、组合数解法、动态规划解法到边界条件全部拆开揉碎讲一遍。不管你是刚开始备战秋招的应届生还是想补一补算法基础的开发者只要把这题吃透同类“有限资源组合计数”的题目对你来说基本就是送分题了。1. 命题拆解这道题到底在考什么1.1 原题描述与题意转化先还原一下题目的经典版本我按牛客网流传最广的描述来说小Q有X首长度为A的不同的歌以及Y首长度为B的不同的歌。现在小Q想用这些歌组成一个总长度正好为K的歌单每首歌最多使用一次。不考虑歌单内歌曲的排列顺序请问一共有多少种不同的组合方式答案对1000000007取模。这道题的考察点其实非常明确组合计数 取模运算 边界处理。它本质上不是一个“搜索”题也不是“动态规划”题——虽然动态规划能做——它更核心的考点是你能不能把一个生活化的场景抽象成“从两个集合中分别选若干元素满足一个线性约束”的数学模型。我见过不少同学一上来就DFS枚举每首歌用还是不用。虽然X和Y最多100但2的200次方显然不可能跑完这种思路基本等于直接判死刑。所以第一步不是写代码而是把题意转化成数学语言从X首长度为A的歌里选p首从Y首长度为B的歌里选q首只要满足p * A q * B K 0 p X 0 q Y这个歌单的组合方式数就是 C(X, p) * C(Y, q)。因为歌曲互不相同从X首里选p首有C(X, p)种选法Y同理两种选择互相独立乘起来就是最终方案数。这道题的“坑”不在算法复杂度而在你能不能识别出这个“枚举p解出q”的结构。你要是被“歌单”“歌曲长度”这些花哨的描述绕进去了就会觉得它像模拟题可一旦抽离出这个线性方程它就是一个纯组合数学问题。1.2 先用小样例手动推演以牛客官方样例为例K5A2X3B3Y3。我们逐个枚举从A歌中选的数目pp0时剩余长度55不能整除3无效p1时剩余长度3正好等于B的长度q1于是有 C(3,1)C(3,1)339 种p2时剩余长度11不能整除3无效p3时p*A6已经超过K5后面更大的p更不可能直接结束。最终答案就是9。这个手算过程看起来很简单但它揭示了核心算法的骨架枚举p是唯一需要遍历的维度q是解方程得到的不需要再套一层循环。很多第一次写这道题的人会把p和q都枚举一遍写出O(X*Y)的嵌套循环虽然数据量小也没啥问题但一是代码更绕二是如果数据范围放大就危险了。所以“枚举一个变量另一个变量靠等式直接解出来”是这类题最核心的优化思想也是笔试时最体现基本功的地方。2. 从组合数枚举到动态规划两条主流解法的完整推导2.1 组合数解法预处理杨辉三角枚举一遍出答案这道题网上流传最广的正解就是组合数枚举。因为X和Y最大才100我们需要用到的组合数C(n, k)里n不会超过100直接用一个二维数组预处理杨辉三角即可。组合数的递推公式是C(n, k) C(n-1, k-1) C(n-1, k)边界条件是C(n, 0)C(n, n)1。因为题目要求取模1e97所以每一步加完都取模不会溢出。整个算法流程分三步预处理C[0..100][0..100]枚举p从0到X每当p*A大于K就break计算剩余长度rem K - p*A如果rem能被B整除令q rem / B且q在[0, Y]范围内就把C[X][p] * C[Y][q]累加到答案中。代码写出来长这样#include bits/stdc.h using namespace std; const int MOD 1000000007; long long C[105][105]; int main() { int K, A, X, B, Y; cin K A X B Y; // 预处理组合数 for (int i 0; i 100; i) { C[i][0] C[i][i] 1; for (int j 1; j i; j) { C[i][j] (C[i-1][j-1] C[i-1][j]) % MOD; } } long long ans 0; for (int p 0; p X; p) { int used p * A; if (used K) break; // 后面p更大也必然超K直接退出 int rem K - used; if (rem % B ! 0) continue; int q rem / B; if (q Y) continue; // q不能超过Y首B歌的上限 ans (ans C[X][p] * C[Y][q]) % MOD; } cout ans endl; return 0; }代码里几个细节值得说为什么pA大于K就break而不是continue因为A是正整数p越大pA越大一旦超过K后面的p不可能再满足条件直接break能省掉无效迭代。为什么q自动满足q0因为rem K - pA而我们已经保证了pA K所以rem非负没有必要再判断q0。为什么用long longC[X][p]和C[Y][q]相乘之前虽然取过模但两个模1e9级别的数相乘会超过int范围必须先提升到long long再乘。这个解法的复杂度是预处理组合数O(N^2)N100加上枚举O(X)放到笔试里就是秒出结果。2.2 动态规划解法经典的01背包恰好装满如果对组合数学不太熟完全可以用动态规划来做这个思路更通用也是很多背包类问题的基础。我们每首歌只能用一次长度为A的歌有X首长度为B的歌有Y首目标是从这些物品中选出若干个使总长度恰好等于K问方案数。这就是经典的“01背包求方案数”问题只是这个背包里只有两种体积——A和B——并且每种体积有若干件个体。定义dp[j]为“拼出总长度j的歌单方案数”初始化dp[0]1其余为0。然后先把X首长度为A的歌逐个当成物品跑一遍01背包再把Y首长度为B的歌逐个跑一遍01背包。#include bits/stdc.h using namespace std; const int MOD 1000000007; long long dp[1005]; int main() { int K, A, X, B, Y; cin K A X B Y; dp[0] 1; // 处理X首长度为A的歌 for (int i 0; i X; i) { for (int j K; j A; j--) { dp[j] (dp[j] dp[j-A]) % MOD; } } // 处理Y首长度为B的歌 for (int i 0; i Y; i) { for (int j K; j B; j--) { dp[j] (dp[j] dp[j-B]) % MOD; } } cout dp[K] endl; return 0; }这里最关键的一行是内层循环倒序遍历。01背包为了避免同一件物品被选多次必须从K往小里更新。如果正序更新dp[j-A]可能在同一次循环里已经被当前这首歌更新过就会造成“同一首歌被用多次”的错误。这个点笔试时最容易踩很多同学明明思路对就栽在遍历顺序上代码跑出来的答案莫名其妙偏大。这个DP解法的复杂度是O((XY)*K)K如果和原题一样是1000量级那也就20万次运算完全没问题。它的好处是通用就算题目换成三种长度、四种长度的歌你只要加一层循环就能扩展坏处是K一旦放大到10^7甚至更大这个解法就力不从心了。2.3 两种解法的对比与场景选择我把两种解法的特点整理成一个表方便大家按场景选择对比维度组合数枚举01背包DP核心思想枚举一个维度的数量另一个维度用方程解出把每首歌看作一个重量为A或B的物品时间复杂度O(X)主要耗时在预处理组合数O((XY)*K)依赖K的大小不受K影响K再大也无所谓K越大多耗时越高代码量较短但需要理解组合数较长但套路固定可扩展性只适用于“两类物品”的计数可以扩展到多类物品、多种长度考察点组合数学与等式建模背包模型与状态定义笔试题里如果只追求“过”两种解法都可以。但我的建议是平时练习优先把组合数枚举吃透因为笔试的评分很多时候会看代码风格和思路清晰度组合数解法代码短、逻辑直白不容易写错动态规划解法作为保底思路也要会万一遇到题目变了比如歌单顺序有影响、歌曲可以重复用你需要能用背包思想做变形。3. 边界条件与高频踩坑点笔试现场的血泪教训3.1 取模运算的隐蔽陷阱这题答案要对1000000007取模这个模数本身是质数也是竞赛里最常用的模数。小学不会觉得取模有什么问题但随着数据变大坑就出来了。第一个坑是乘法溢出。C[X][p]和C[Y][q]都在取模后理论上小于1e97但其实两个都小于1e97的数相乘最大接近1e18而int最大才21亿多所以必须用long long。很多同学本地跑小数据一点问题没有交上去就WAWrong Answer查来查去才发现是乘法溢出了。第二个坑是负数的模运算。如果你在代码里写了类似ans (ans - something) % MOD这种操作在C里如果ans减完变成负数取模结果也可能是负数输出就错了。正确写法需要先加MOD再取模ans (ans - something MOD) % MOD。这题没有减法操作但如果做变形题减法取模的坑很容易踩。第三个坑是杨辉三角预处理的范围。C数组我开到了105因为X和Y最大是100组合数下标不会超过100。这没问题。但如果你把数组下标写成动态的X和Y而不是固定的101也要保证数组容量够不然越界访问会让你调试到怀疑人生。3.2 数据范围和循环终止条件我见过不少人在枚举p的时候用的是for (int p 0; p X; p)进来先判断if (p*A K) continue而不是break。这两个写法在数据小的时候都能跑出正确结果但背后是有差别的。因为A是正整数p*A是单调递增的所以一旦超过K后面所有p都超过K用break比continue少跑很多无效循环。虽然原题数据量小continue也完全不会超时但作为一个技术面试的笔试题面试官会看你的代码里有没有这种“提前终止”的敏感度。程序员的基本功往往就体现在这种地方。另外q rem / B这里当rem能被B整除时q自然是个整数。但是别忘了q必须小于等于Y因为B歌总共只有Y首。有一个很隐蔽的错误是判断了rem % B 0却没判断q Y结果多算了一堆“不存在”的方案。这个bug在样例数据上不一定能暴露出来因为样例恰好是q1Y3满足条件一旦你写题时自己构造数据测试就会发现问题。笔试没有本地测试机会的时候尤其要小心这类“满足方程但超出资源上限”的情况。3.3 笔试环境下的时间分配心法这道题在腾讯2017秋招笔试里属于中等偏基础的位置通常应该控制在15分钟以内解决。我自己的打法是前2分钟不写代码先读题在纸上列出pA qB K这个方程确定枚举方向中间5分钟直接写组合数预处理和枚举主循环最后3分钟造几组小数据自测比如K0时答案应该是1空歌单X0时只剩B歌的情况AK且BK的交叉情况确认无误再提交。K0这个边界很多人会忽略。题目说总长度正好为K那K0时只能什么歌都不选答案是1。这个结论在组合数枚举里也能自然得到p0q0C[X][0]*C[Y][0]1。但在DP里你只要初始化dp[0]1也能得到同样的结果。笔试时如果题目没给K的范围下限最好加一层判断。4. 从一道题到一类题组合计数思维怎么延伸4.1 “顺序敏感”的变体你还会做吗很多同学把这道题的AC代码背下来就完了但笔试真正考的是你理解不理解背后的原理。把题目稍微换一个条件很多人就懵了如果问题改成“歌单内歌曲顺序不同算作不同歌单”答案会变成什么思路是这样的先从X首A歌里选p首从Y首B歌里选q首此时你手里有pq首歌。现在要给它们排成一个歌单这pq首歌里包含p首A类歌和q首B类歌其中同类歌之间是不同的个体但它们在“长度”这个维度上不可区分。所以排列数不是简单的(pq)!而是多重排列数(pq)! / (p! * q!)这个数也等于 C(pq, p)。于是总的方案数就是C(X, p) * C(Y, q) * C(pq, p)如果你能意识到顺序敏感和非敏感之间只差一个因子就说明你是真的理解了组合计数的结构而不是背代码。腾讯这类公司考算法题经常在这种“看似改了一个词实则考你深度”的地方做文章。4.2 歌曲可以重复使用的完全背包版本另一个常见变形是歌曲数量无限每首歌可以重复使用其他条件不变。这个问题就从01背包方案数变成了完全背包方案数经典对应LeetCode 518题“零钱兑换II”。代码上只需要把内层循环从倒序改成顺序即可for (int i 0; i X; i) { // 这里其实不需要再循环每首歌而是循环首歌? for (int j A; j K; j) { dp[j] (dp[j] dp[j-A]) % MOD; } }不过这个写法更准确地对应“A类歌可以任意次使用”而不是“有X首不同的歌”。如果强调“不同的歌”完全背包的状态应该按长度类型循环而不是按歌曲个体循环。这个微妙的差别是很多人在“会做”和“真懂”之间的分水岭。4.3 数据范围放大之后的进阶解法如果题目把X、Y、K都放大到10^5组合数枚举O(X)看起来还行但DP会直接挂掉。这时候就要上生成函数了。令F(t)表示A类歌的生成函数G(t)表示B类歌的生成函数F(t) (1t^A)^X G(t) (1t^B)^Y答案就是[x^K] F(t)*G(t)即两个多项式乘积中次数为K的系数。用NTT数论变换做多项式卷积复杂度是O(K log K)。这是竞赛选手会考虑的路线但校招笔试一般不会考这么深。我把它列在这里只是想说明任何一道基础题往深了挖都能挖到很高的层次关键是你要有“从具体到抽象”的思维习惯。4.4 同类经典题型的刷题地图如果觉得这道题刷得不过瘾想顺着“组合计数”这个分支建立题库我个人推荐按顺序做以下几类LeetCode 518完全背包方案数和此题变形版几乎一样LeetCode 494目标和把每个数看作可正可负的背包物品本质上属于“两堆划分”问题牛客“拼凑面额”完全背包计数题型更贴近国内笔试风格牛客“小Q的数列”腾讯同场笔试题用来适应同一年份的命题风格Codeforces 1207EXOR Counting用生成函数思想做组合异或计数。刷的时候不要只求AC每道题想三件事状态怎么定义、边界怎么处理、如果数据放大十倍还能不能做。这个思维习惯养成了笔试遇到的陌生题会少很多因为大部分题目都能归入你熟悉的模式里。5. 复盘为什么这道题能成为经典笔试题5.1 短题干里的多重考察点腾讯的笔试向来以“题面简洁、陷阱够深”著称这道“小Q的歌单”完美体现了这种风格。题干不到五行看起来人畜无害但真正写起来涉及了能否把情景建模成线性方程、组合数是否熟练、取模和long long这些细节是否敏感、循环能否提前break。这几个点恰恰是一个工程师日常写业务代码时同样需要的基本素质。我当年第一次做这道题写的是DFS数据范围一大就超时本地测试的时候卡了半小时没跑出来。后来看了别人的题解才意识到这道题最表层的故事是“歌单”里层的本质是“数学建模”。那次之后我养成了一个习惯拿到算法题第一件事不是打开编辑器而是花两分钟在纸上写写画画把约束关系列出来再决定用什么算法。这个习惯帮我省下了很多笔试时间。5.2 这道题当年的现场表现据说当年这道题在笔试系统里的通过率并不高很大一部分原因不是算法不会而是很多人卡在“歌曲不同”这个描述上。有些人以为“不同的歌”和“不同长度的歌”是一回事直接按组合数C(X,p)算有些人则忽略了“每首歌最多只能使用一次”把01背包写成了完全背包答案大了一圈。这也提醒我们笔试的得分点往往藏在对题干关键词的精确理解上。建议读题时把“不同”“最多”“正好”“不考虑顺序”这些限定词圈出来它们在很大程度上决定了你要写哪套算法。