P1313 计算系数【洛谷算法习题】

P1313 计算系数网页链接P1313 计算系数题目描述给定一个多项式( 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。noip2011 提高组 day2 第 1 题。解题思路本题核心是二项式定理结合杨辉三角递推直接求解多项式展开式的指定项系数。根据二项式展开公式( a x b y ) k (axby)^k(axby)k中x n y m x^n y^mxnym项的系数由组合数C k n C_k^nCkn​、a n a^nan、b m b^mbm三部分相乘得到且满足n m k nmknmk。代码采用递推模拟展开的方式构建二维数组模拟杨辉三角直接通过a x axax、b y byby的系数递推计算每一项的结果全程对10007 1000710007取模。该方法无需单独计算组合数与幂次逻辑直观简洁时间复杂度O ( k 2 ) O(k^2)O(k2)完美适配k ≤ 1000 k \le 1000k≤1000的数据范围最终直接输出目标项的系数。总结核心逻辑依托二项式定理递推模拟多项式展开过程直接计算目标项系数。关键操作二维数组递推、固定模数10007 1000710007取模、定位目标项位置。效率保障递推计算简洁高效无冗余运算精准匹配题目数据范围与取模要求。代码代码#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll a,b,k,n,m;cinabknm;ll x[1010][1010];x[1][1]1;for(ll i2;ik1;i)for(ll j1;ji;j)x[i][j](x[i-1][j-1]*bx[i-1][j]*a)%10007;coutx[k1][m1];return0;}