bzoj2004

反正N<=10^9肯定是矩阵乘法
反正p<=10肯定是状压dp
首先有一个非常重要的性质是任意连续P个站，必须保证K辆车必须停在其中的一个站
我们设f[i,S]表示到第i个站搞定了后，这K辆公交车停靠的站的状态集合为S的方案数
由于公交车之间是等价的，因此我们只要知道这K辆公交车离当前站的距离（∈[0,p-1])
显然这有一辆肯定距离当前站距离为0，剩下的k-1辆的距离显然在[1,p-1]中组合
可知状态数为C(k-1,p-1)，不难发现状态数最多是C(5,9)=126
由此可以得到f[i,s]=∑f[i-1,s']
显然我们可以弄出转移矩阵然后矩乘加速

const mo=30031;

var w:array[0..130,0..11] of boolean;
    v:array[0..11] of boolean;
    a,b,c,d:array[0..130,0..130] of longint;
    ch,m,n,k,p,i,j,h,ans:longint;

procedure mul;
  var i,j,k:longint;
  begin
    for i:=1 to m do
      for j:=1 to m do
      begin
        c[i,j]:=0;
        for k:=1 to m do
          c[i,j]:=(c[i,j]+a[i,k]*b[k,j]) mod mo;
      end;
  end;

procedure dfs(x,t:longint);
  var i:longint;
  begin
    if (p-x<k-t) then exit;
    if t=k+1 then
    begin
      inc(m);
      w[m]:=v;
    end;
    for i:=x to p do
    begin
      v[i]:=true;
      dfs(i+1,t+1);
      v[i]:=false;
    end;
  end;

procedure quick(n:longint);
  var t,i,x:longint;
  begin
    x:=n;
    t:=0;
    while x<>0 do
    begin
      inc(t);
      x:=x shr 1;
    end;
    for i:=t-1 downto 0 do
    begin
      a:=c;
      b:=c;
      mul;
      if (1 shl i) and n<>0 then
      begin
        a:=c;
        b:=d;
        mul;
      end;
    end;
  end;

begin
  readln(n,k,p);
  v[1]:=true;
  dfs(2,2);  //搜出所有状态
  for i:=1 to m do
    for j:=1 to m do
    begin
      ch:=1;
      for h:=1 to p do
        if w[i,h] and not w[j,h+1] then  //有一辆有停靠在当前站
        begin
          dec(ch);
          if ch<0 then break;
        end;
      if ch=0 then d[j,i]:=1;
    end;

  n:=n-k;
  for i:=1 to m do
    c[i,i]:=1;
  quick(n);
  writeln(c[1,1] mod mo);
end.