信奥赛C提高组csp-s之快速幂案例实践2题目描述给定一个多项式( b y a x ) k (byax)^k(byax)k请求出多项式展开后x n × y m x^n\times y^mxn×ym项的系数。输入格式输入共一行包含5 55个整数分别为a , b , k , n , m a,b,k,n,ma,b,k,n,m每两个整数之间用一个空格隔开。输出格式输出共一行包含一个整数表示所求的系数。这个系数可能很大输出对10007 1000710007取模后的结果。输入输出样例 1输入 11 1 3 1 2输出 13说明/提示【数据范围】对于30 % 30\%30%的数据有 $ 0\le k\le 10$。对于50 % 50\%50%的数据有 $ a1 b1$。对于100 % 100\%100%的数据有0 ≤ k ≤ 1000 0\le k\le 10000≤k≤10000 ≤ n , m ≤ k 0\le n,m\le k0≤n,m≤kn m k nmknmk0 ≤ a , b ≤ 10 6 0\le a,b\le 10^60≤a,b≤106。思路分析本题要求计算多项式( b y a x ) k (byax)^k(byax)k展开后x n y m x^n y^mxnym项的系数。根据二项式定理展开式的通项为$T_{i} \binom{k}{i} (by)^i (ax)^{k-i} \binom{k}{i} a^{k-i} b^i , x^{k-i} y^i$其中 (x) 的指数为 (k-i)(y) 的指数为 (i)。令 (n k-i)(m i)则 (im)且由题意保证 (nmk)。因此所求系数为$\binom{k}{m} \cdot a^n \cdot b^m$最终结果对 (10007) 取模。由于k ≤ 1000 k \le 1000k≤1000可以直接用杨辉三角递推组合数时间复杂度O ( k 2 ) O(k^2)O(k2)幂运算使用快速幂时间复杂度O ( log n ) O(\log n)O(logn)。注意 (a,b) 先取模再计算幂。代码实现#includebits/stdc.h// 万能头文件usingnamespacestd;constintMOD10007;// 模数intc[1005][1005];// 组合数表 c[k][m]// 快速幂函数计算 x^y % MODintqpow(intx,inty){intres1;x%MOD;// 先取模防止溢出while(y){if(y1)resres*x%MOD;xx*x%MOD;y1;}returnres;}intmain(){inta,b,k,n,m;cinabknm;// 预处理组合数 C[i][j] 模 MODfor(inti0;ik;i){c[i][0]c[i][i]1;// 边界for(intj1;ji;j){// 杨辉三角递推公式c[i][j](c[i-1][j-1]c[i-1][j])%MOD;}}// 计算答案C(k,m) * a^n * b^m 模 MODintansc[k][m]*qpow(a,n)%MOD*qpow(b,m)%MOD;coutansendl;return0;}功能分析快速幂函数qpow输入底数x和指数y返回x^y % MOD。采用二进制拆分思想时间复杂度 (O(\log y))。注意底数先取模避免中间结果过大。主函数流程读入五个整数a, b, k, n, m。预处理组合数用双重循环递推杨辉三角c[i][j]表示( i j ) m o d M O D \binom{i}{j} \bmod MOD(ji)modMOD。外层循环 i 从 0 到 k内层计算每个非边界值。计算答案通过公式c[k][m] * pow(a,n) * pow(b,m) % MOD得到最终系数。输出结果。更多系列知识请查看专栏《信奥赛C提高组csp-s知识详解及案例实践》https://blog.csdn.net/weixin_66461496/category_13113932.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html4、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}