这道题很多同学第一次看到这道题都会想到DFS动态规划递归搜索实际上这些方向都会越想越复杂。这道题真正考察的是组合数学隔板法 / 组合数 数学转化。第三部分 第二题《堆石子》——石子王国里的神奇变身术第一幕石子王国1、石子王国举行了一场比赛。国王拿来了很多石子。他说今天你们要把石子堆成很多堆。2、但是有要求① 第1堆固定有 n 个石子。② 后面的每一堆都必须比前一堆少。例如7 5 3 1可以。因为7531但是7 6 6 2不行。因为66不是严格递减。3、题目问一共有多少种合法方案第二幕先不要急着写程序1、有的同学第一反应枚举所有方案2、例如6 ↓ 5 ↓ 4 ↓ ...不停DFS。但是你会发现数据范围非常大。DFS根本不可能。3、找一找看看有没有数学规律。第三幕观察样例1、例如第一堆固定5要求一共三堆。2、那么后面还能怎么放例如5 4 3可以。还可以5 4 2也可以。还可以5 3 2……规律是啥呢第四幕换一种思考方式1、这道题神奇的一步。1第一堆已经固定a1 n例如第一堆 7那后面的石子数还能是多少2只能是1 2 3 4 5 6是不是3也就是说后面其实就是从1 ~ n-1里面挑数字。2、还需要考虑数字顺序吗1整道题最关键的一句话。例如我们选了2 5 6题目要求严格递减2所以它最后一定会变成7 6 5 23注意我们根本没有选择顺序。因为一旦数字选出来顺序就唯一确定了。这一点非常重要。4因此不用排列只需要组合。第五幕方案数是C(n-1,m-1)1、现在问题已经变得非常简单了。1第一堆固定n2后面还有m-1堆。3那么只需要从1 ~ n-1里面选择m-1个不同数字。4因此方案数就是第六幕参考程序#include iostream using namespace std; // 模数题目要求结果对 1000000007 取模 const int MOD (int)1e9 7; /////////////////////////////////////////////////////// // 快速幂 // // 功能计算 // // base^exp % MOD // // 时间复杂度O(log exp) // // 这里不仅计算乘方后面还会用它求模逆元。 /////////////////////////////////////////////////////// int qpow(int base, int exp) { // 指数等于0 // 根据数学规定 // // a^0 1 if (!exp) return 1; // 如果指数是奇数 // // 例如 // // 3^13 // // 3×(3²)^6 // // 需要多乘一个base if (exp 1) { return (long long)base * qpow((long long)base * base % MOD, exp 1) % MOD; } // 如果指数是偶数 // // 例如 // // 3^12 // // (3²)^6 // // 不需要额外乘base return qpow((long long)base * base % MOD, exp 1); } /////////////////////////////////////////////////////// // 计算组合数 // // 返回C(n,m) // // 使用乘法公式 // // n(n-1)...(n-m1) // C(n,m)-------------------- // m! // // 由于有MOD // // 不能直接除法 // // 所以使用模逆元。 /////////////////////////////////////////////////////// int comb(int n, int m) { // 如果选择数量比总数还多 // 显然没有方案 if (m n) return 0; // 保存答案 int ans 1; //////////////////////////////////////////////////// // 逐步计算组合数 //////////////////////////////////////////////////// for (int i 0; i m; i) { ////////////////////////////////////////////////// // 乘分子 // // 第一次 // n // // 第二次 // n-1 // // 第三次 // n-2 ////////////////////////////////////////////////// ans (long long)ans * (n - i) % MOD; ////////////////////////////////////////////////// // 再除以 // // i1 // // 但是 // // 模运算不能直接除法 // // 所以 // // ×逆元 // // 根据费马小定理 // // x^(MOD-2) // // 就是 // // x 的逆元 ////////////////////////////////////////////////// ans (long long)ans * qpow(i 1, MOD - 2) % MOD; } return ans; } /////////////////////////////////////////////////////// // 主函数 /////////////////////////////////////////////////////// int main() { // m一共多少堆 // n第一堆有多少石子 int m, n; cin m n; //////////////////////////////////////////////////// // 第一堆固定是 n // // 后面还需要 m-1 堆 // // 每一堆必须严格递减 // // 等价于 // // 从 // // 1~n-1 // // 中选择 // // m-1 // // 个不同数字 // // 顺序自动确定 // // 所以答案就是 // // C(n-1,m-1) //////////////////////////////////////////////////// cout comb(n - 1, m - 1) endl; return 0; }程序里面用到了竞赛的压缩写法例如快速幂递归写法费马小定理模逆元边循环乘法计算组合数。第七幕快速幂到底在干什么1、暴力乘法假设老师问大家请计算2¹⁰最普通的方法就是int ans 1; for(int i 1; i 10; i) ans * 2;乘了10 次没有问题。2、如果老师问2¹⁰⁰就要乘100 次还是可以。3、如果老师问2¹⁰⁰⁰⁰⁰⁰⁰⁰⁰怎么办是不是要乘100000000 次显然不可能。所以一定有更快的方法。4、观察规律我们把指数写出来2¹2²2⁴2⁸2¹⁶其实就是不断平方。所以2² (2¹)²2⁴ (2²)²2⁸ (2⁴)²5、快速幂最核心的一句话指数减半底数平方。请同学们一定把这句话记住。6、那指数是奇数怎么办奇数 先乘一个base 剩下指数减半继续算。7、看代码/////////////////////////////////////////////////////// // 快速幂 // // 功能计算 // // base^exp % MOD // // 时间复杂度O(log exp) // // 这里不仅计算乘方后面还会用它求模逆元。 /////////////////////////////////////////////////////// int qpow(int base, int exp) { // 指数等于0 // 根据数学规定 // // a^0 1 if (!exp) return 1; // 如果指数是奇数 // // 例如 // // 3^13 // // 3×(3²)^6 // // 需要多乘一个base if (exp 1) { return (long long)base * qpow((long long)base * base % MOD, exp 1) % MOD; } // 如果指数是偶数 // // 例如 // // 3^12 // // (3²)^6 // // 不需要额外乘base return qpow((long long)base * base % MOD, exp 1); }时间复杂度从 O(n) 变成了 O(log n)。第八幕逆元到底在干什么1、我们有新同学会有这样的疑问逆元是什么费马小定理是什么为什么是 MOD-22、先回答一个最简单的问题为什么需要逆元然后再讲逆元是什么最后我再讲为什么用MOD-2这样学生们就能真正理解。一、首先 为什么需要逆元1、假设我们要求2、数学公式3、程序如果没有取模。直接写ans*5; ans*4; ans/2; ans/1;是不是一点问题都没有答案没有。4、我们的比赛里面。题目会写答案对1000000007取模于是我们每一步都会写ans%MOD;但是模运算里面不能直接做除法。这一条必须记住。二、 那怎么办数学家想到1、除法转乘法例如20÷5其实就是20×(1/5)是不是2、所以如果我们能找到1/5就不用除法了。全部变乘法。3、于是数学家给它起了名字逆元Inverse就是说逆元就是模意义下的倒数。这一句话非常重要。三、 什么叫倒数1、我们小学生已经学过。例如2倒数1/2为什么因为2×1/21例如5倒数1/5因为5×1/51是不是2、所以逆元其实就是模运算里的倒数。四、 可是在模里面没有小数呀1、终于问到重点了。例如模7。我们找2的逆元。2、意思就是找一个数x满足2 * x ≡1(mod7)试试看。2×12不是。2×24不是。2×36不是。2×48模71成功4、所以2的逆元 4因为2×4 ≡1(mod7)5、再试33×515模71所以3的逆元 5是不是很神奇五、费马小定理1、如果MOD1000000007一个一个试。要试十亿次。当然不行。2、数学家证明了1如果MOD是质数。那么根据费马小定理有2两边同时乘得到3也就是说a 的逆元 a^(MOD-2)4所以程序qpow(a,MOD-2)其实就是求1/a是不是同学们一下就清楚了六、 回到comb()1、我们已经能看懂这一句了。ans*qpow(i1,MOD-2);2、例如第一次÷1变成×1第二次÷2变成×2的逆元第三次÷3变成×3的逆元3、于是整个组合数程序实际上写成了× 1的逆元 × 2的逆元 × 3的逆元 ...完全没有除法。4、所以再模运算下使用逆元来算组合数。七、循环怎么写1、例如求数学2、程序第一次×6 ÷1第二次×5 ÷2第三次×4 ÷3是不是正好得到6×5×4 --------- 1×2×3所以整个循环就是一边乘分子一边乘分母的逆元。八、再看下代码/////////////////////////////////////////////////////// // 计算组合数 // // 返回C(n,m) // // 使用乘法公式 // // n(n-1)...(n-m1) // C(n,m)-------------------- // m! // // 由于有MOD // // 不能直接除法 // // 所以使用模逆元。 /////////////////////////////////////////////////////// int comb(int n, int m) { // 如果选择数量比总数还多 // 显然没有方案 if (m n) return 0; // 保存答案 int ans 1; //////////////////////////////////////////////////// // 逐步计算组合数 //////////////////////////////////////////////////// for (int i 0; i m; i) { ////////////////////////////////////////////////// // 乘分子 // // 第一次 // n // // 第二次 // n-1 // // 第三次 // n-2 ////////////////////////////////////////////////// ans (long long)ans * (n - i) % MOD; ////////////////////////////////////////////////// // 再除以 // // i1 // // 但是 // // 模运算不能直接除法 // // 所以 // // ×逆元 // // 根据费马小定理 // // x^(MOD-2) // // 就是 // // x 的逆元 ////////////////////////////////////////////////// ans (long long)ans * qpow(i 1, MOD - 2) % MOD; } return ans; }送给新同学一句最好记的话⭐⭐⭐⭐⭐不要把逆元想得太神秘。只要记住普通数学里除以 5乘 ( 1/5)而在模运算里没有真正的小数所以除以 5乘 5 的逆元至于5 的逆元怎么求如果模数是质数像本题的1000000007可以直接使用快速幂qpow(5, MOD - 2)即可。第九幕整道程序其实最后只有三步1、我们画流程图。就是输入 ↓ 第一堆固定 ↓ 后面需要选 m-1 个数字 ↓ 答案C(n-1,m-1) ↓ 计算组合数 ↓ 输出2、你现在会发现真正难的不是程序而是知道答案为什么是C(n-1,m-1)。程序真正干的事情只有两件计算组合数C(n-1,m-1)由于结果需要对10^97取模因此使用快速幂求模逆元避免直接做除法。第十幕这道题考察了哪些知识知识点是否重点本题作用数学建模⭐⭐⭐⭐⭐将石子问题转化组合问题正整数拆分⭐⭐⭐⭐⭐理解为什么使用组合数组合数计算⭐⭐⭐⭐⭐求 (C(n-1,m-1))快速幂⭐⭐⭐⭐求模逆元费马小定理⭐⭐⭐⭐模意义下实现除法总结这道题是一道综合题写代码前需要同学们先要完成数学转化。