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

 

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

私人qq：1064864324，加备注，有问题来找我，一起探讨一起进步