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.

评论

0条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据