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，加备注，有问题来找我，一起探讨一起进步
原文：http://www.cnblogs.com/victorslave/p/4800610.html