计算系数 （codevs 1137) 题解

时间：2021-07-12 00:45:59

【问题描述】

给定一个多项式(ax + by)^k，给定a、b、k、n、m，请求出多项式展开后x^n y^m项的系数。

【样例输入】

1 1 3 1 2

【样例输出】

3

【解题思路】

本题为NOIP2011 提高组第一题，看到这玩意我懵了，本人初三狗，完全不会做啊……在老师的指导下终于觉悟，这玩意为二项式定理，其实就是求杨辉三角形的第k行,第n项，在老师推完之后还发现了，其实就是求C(k,m),C为组合数公式，我两种方法都试了，但似乎组合数取模与一半的不一样，于是WA了，顺便求一下哪位神犇看到了请指教一下……这里贴杨辉三角形的代码。求了这个以后，再乘上a^n*b^m即可，注意：a^n与b^m都要边乘边取模，杨辉三角形建立的时候也要取模，最后三者相乘还要取模……

【代码实现】

 var f:array[..,..] of longint;

     a,b,m,n,k,i,j:longint;

 function fac(a,b:int64):int64;

 var t:int64;

     y:longint;

 begin

  t:=;

  for y:= to b do

   t:=(t*a) mod ;//幂运算，注意乘一次就要取一次模

  exit(t);

 end;

 begin

  readln(a,b,k,n,m);

  for i:= to k do

   f[i,]:=;

  for i:= to k do

   for j:= to k do

    f[i,j]:=(f[i-,j]+f[i-,j-])mod ;//建立杨辉三角形，注意取模

  if k= then writeln()

  else

   writeln((f[k,n]*(fac(a,n)mod )*(fac(b,m)mod ))mod );//最后再取模

 end.

杨辉三角形

相关文章