这道题显然有，矩阵乘法可解（由数据范围可得）

显然有题目要求: f[n]=∑f[i] (n-k<i<n-1),矩阵乘法相关知识自行google，推荐阅读Matrix67写的一篇文章。

所以构造有数组A(k*k):

000…1

100…1

010…1

001…1

因为看k<10,我们可以先计算出f[1]~f[k],然后用矩阵乘法加速，计算出A^(n-k),最后再f*A^(n-k)乘一下就得出了。

我用的是递归式的矩阵二分取幂，后来才知道这样写会显得你很弱智……我也不知道为什么，然后就顺便再复习了一下，快速幂的非递归写法。

果断C++没学好，还是用pascal写的，这是这道题的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
type arr=array[-1..12,-1..12] of int64;
const md=7777777;
var
  k,i,j:longint;
  n,ans:int64;
  t,q:arr;
  f:array[-1..12] of int64;

function mul(a,b:arr):arr;
var
  c:arr;
  i,j,p:longint;
begin
  fillchar(c,sizeof(c),0);
  for i:=1 to k do
    for j:=1 to k do
      for p:=1 to k do
        c[i,j]:=(c[i,j]+(a[i,p]*b[p,j] mod md)) mod md;
  exit(c);
end;

function dv(x:int64):arr;
var tp:arr;
begin
  if x=1 then exit(t);
  tp:=dv(x div 2);
  tp:=mul(tp,tp);
  if (x mod 2)<>0 then tp:=mul(tp,t);
  exit(tp);
end;

begin
  readln(k); readln(n);
  fillchar(t,sizeof(t),0);
  for i:=1 to k-1 do t[i+1,i]:=1;
  for i:=1 to k do t[i,k]:=1;
  for i:=1 to k do f[i]:=0; f[0]:=1;
  for i:=1 to k do
    for j:=0 to i-1 do
      f[i]:=f[i]+f[j];
  if n<=k then begin writeln(f[n]); halt; end;
  q:=dv(n-k); ans:=0;
  for i:=1 to k do
    ans:=(ans+(f[i]*q[i,k] mod md)) mod md;
  writeln(ans);
end.