【noip2011】【codevs1137】计算系数

var
　　　f:array[-1..1001,-1..1001] of longint;
  　　a,b,m,n,k,i,j:longint;
begin
  　　readln(a,b,k,n,m);
  　　f[1,0]:=b;
  　　f[1,1]:=a;
  　　for i:=2 to k do
    　　　for j:=0 to k do
      　　f[i,j]:=(f[i-1,j]*b+f[i-1,j-1]*a) mod 10007;
  　　writeln(f[k,n]);
end.

不想多说，其实就是一个dp还不带优化。

看到这道题大多数人第一反应应该是公式c(b,k)*a^n*b*m，但是——

这个公式的复杂度和指数有关，并非o（1）的，所以看数据k<=1000显然可以dp

设f[i,j]表示将(ax+by)^i展开后x^j y^(i-j)的系数

初始化f[1,0]=b,f[1,1]:=a;

DP转移方程f[i,j]:=f[i-1,j]*b+f[i-1,j-1]*a

喜欢就收藏一下，记得向好朋友推荐哦