zoj3216:Compositions【DP+矩阵乘法】
题目大意:有T组数据,每组数据给出N和K,求N的自然数和分解中,每个数不小于K的方案总数(分解方案有序,也就是说3=1+2和3=2+1是两种方案)。
首先可以想想DP的方程。
f[i]表示c(i,K)(定义与题目相同)的值,那么可以得到:
f[i]:=f[i-1]+f[i-K]
似乎有一定的理解难度,这个递推的正确性很难说,意会一下吧,大致分为一下两种情况:
1、i在i-K的分解基础上,再在分解的数列前面插入一个k。
2、i在i-1的分解基础上,再将分解的数列的第一个数加一。
如果你现在不想知道详细的证明,看到这里就差不多了,接下来是较为严谨的证明:
用f[i,j]表示i用j个不小于K的自然数分解的方案总数,就可以比较显然得到:
f[i,j]:=∑f[i-k,j-1](K<=k<=i-1)
f[i+1,j]:=∑f[i-k,j-1](K<=k<=i)
所以f[i+1,j]=f[i,j]+f[i-K+1,j-1]。
对于所有的j都是如此,而c(i,K)=∑f[i,j](1<=j<=i),把所有的j累积起来后再经整理可得:
f[i]:=f[i-1]+f[i-K]。
PS:注意区分k的大小写,不一样的。
PSS:多想想,再提问题。
然后DP方程是一个常系数线性齐次递推式,所以N虽然很大,但是我们就可以用矩阵乘法搞定它。时间复杂度就为O(K^3logN)。
然后有一些小小的注意点:
1、K=1有点特殊,要么特判出来直接用快速幂,要么用我的代码中的构造矩阵的方式卡掉特殊情况。
2、注意构造出的矩阵只要自乘N-K次。
3、注意取模。
代码:
var n,m,i,j,k,t:longint; a,b,c:array[1..30,1..30]of longint; ans,ans2:array[1..30]of longint; begin read(t); while t<>0 do begin dec(t); read(n,m); if n<m then begin writeln(0); continue; end; fillchar(a,sizeof(a),0); inc(a[1,1]); inc(a[1,m]); for i:=1 to m-1 do a[i+1,i]:=1; fillchar(ans,sizeof(ans),0); ans[1]:=1; n:=n-m; fillchar(b,sizeof(b),0); for i:=1 to m do b[i,i]:=1; repeat if n and 1=1 then begin fillchar(c,sizeof(c),0); for i:=1 to m do for j:=1 to m do for k:=1 to m do c[i,j]:=(c[i,j]+a[i,k]*b[k,j]) mod 1000000007; b:=c; end; fillchar(c,sizeof(c),0); for i:=1 to m do for j:=1 to m do for k:=1 to m do c[i,j]:=(c[i,j]+a[i,k]*a[k,j]) mod 1000000007; a:=c; n:=n shr 1; until n=0; fillchar(ans2,sizeof(ans2),0); for i:=1 to m do for j:=1 to m do ans2[i]:=(ans2[i]+b[i,j]*ans[j]) mod 1000000007; writeln(ans2[1]); end; end.
发表回复