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

P1313 计算系数

网页链接

P1313 计算系数

题目描述

给定一个多项式( b y + a x ) k (by+ax)^k(by+ax)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

输入 #1

1 1 3 1 2

输出 #1

3

说明/提示

【数据范围】

对于30 % 30\%30%的数据，有 $ 0\le k\le 10$。

对于50 % 50\%50%的数据，有 $ a=1， ，，b=1$。

对于100 % 100\%100%的数据，有0 ≤ k ≤ 1000 0\le k\le 10000≤k≤1000，0 ≤ n , m ≤ k 0\le n,m\le k0≤n,m≤k，n + m = k n+m=kn+m=k，0 ≤ a , b ≤ 10 6 0\le a,b\le 10^60≤a,b≤106。

noip2011 提高组 day2 第 1 题。

解题思路

本题核心是二项式定理结合杨辉三角递推，直接求解多项式展开式的指定项系数。根据二项式展开公式，( a x + b y ) k (ax+by)^k(ax+by)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 n+m=kn+m=k。代码采用递推模拟展开的方式，构建二维数组模拟杨辉三角，直接通过a x axax、b y byby的系数递推计算每一项的结果，全程对10007 1000710007取模。该方法无需单独计算组合数与幂次，逻辑直观简洁，时间复杂度O ( k 2 ) O(k^2)O(k2)，完美适配k ≤ 1000 k \le 1000k≤1000的数据范围，最终直接输出目标项的系数。

总结

核心逻辑：依托二项式定理，递推模拟多项式展开过程，直接计算目标项系数。
关键操作：二维数组递推、固定模数10007 1000710007取模、定位目标项位置。
效率保障：递推计算简洁高效，无冗余运算，精准匹配题目数据范围与取模要求。

代码代码

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll a,b,k,n,m;cin>>a>>b>>k>>n>>m;ll x[1010][1010];x[1][1]=1;for(ll i=2;i<=k+1;i++)for(ll j=1;j<=i;j++)x[i][j]=(x[i-1][j-1]*b+x[i-1][j]*a)%10007;cout<<x[k+1][m+1];return0;}