背景
守望者warden，长期在暗夜精灵的的首都艾萨琳内担任视察监狱的任务，监狱是成长条行的，守望者warden拥有一个技能名叫“闪烁”，这个技能可以把她传送到后面的监狱内查看，她比较懒，一般不查看完所有的监狱，只是从入口进入，然后再从出口出来就算完成任务了。
描述
头脑并不发达的warden最近在思考一个问题，她的闪烁技能是可以升级的，k级的闪烁技能最多可以向前移动k个监狱，一共有n个监狱要视察，她从入口进去，一路上有n个监狱，而且不会往回走，当然她并不用每个监狱都视察，但是她最后一定要到第n个监狱里去，因为监狱的出口在那里，但是她并不一定要到第1个监狱。
守望者warden现在想知道，她在拥有k级闪烁技能时视察n个监狱一共有多少种方案？
格式
输入格式
第一行是闪烁技能的等级k(1<=k<=10) 第二行是监狱的个数n(1<=n<=2^31-1)
输出格式
由于方案个数会很多，所以输出它 mod 7777777后的结果就行了
样例1
样例输入1
2
4
样例输出1
5
限制
各个测试点1s
提示
把监狱编号1 2 3 4,闪烁技能为2级， 一共有5种方案 →1→2→3→4 →2→3→4 →2→4 →1→3→4 →1→2→4
小提示：建议用int64，否则可能会溢出
解题思路
分析题目可知，拥有k级闪烁技能时视察n个监狱的方案种数可以由下面递推式得出：
f
(
n
)
=
f
(
n
−
1
)
+
.
.
.
+
f
(
n
−
k
)
{f{ \left( {n} \right) } =f{ \left( {n-1} \right) } +...+f{ \left( {n-k} \right) } }
f(n)=f(n−1)+...+f(n−k) 由于n的范围过大，我们可以用矩阵的快速幂方法求得。由递推式可以构造下面的等式：
得到上面的等式就可以很容易的看出解题思路了：我们先初始化f(0)到f(k-1)的值，再计算左边方阵的n次方，再相乘。结果的第一个值即为所求。
AC代码
#include <bits/stdc++.h>
#define FOR(I,A,B) for(int I = (A); I < (B); I++)
#define FORE(I,A,B) for(int I = (A); I <= (B); I++)
#define PRII pair<int,int>
#define INF 0x3f3f3f3f
#define MOD 7777777
using namespace std
;
long long n
,k
;
long long c
[12];
struct M
{
long long m
[12][12];
}ori
;
void print(M t
){
FOR(i
,0,k
){
FOR(j
,0,k
){
printf("%lld ",t
.m
[i
][j
]);
}printf("\n");
}
}
M
mul(M a
,M b
){
M res
;
FOR(i
,0,k
){
FOR(j
,0,k
){
long long tmp
=0;
FOR(l
,0,k
) tmp
+=a
.m
[i
][l
]*b
.m
[l
][j
];
tmp
=tmp
%MOD
;
res
.m
[i
][j
]=tmp
;
}
}
return res
;
}
M
dg(M t
,long long num
){
M res
;
if(num
==1){
res
=t
;
}else if(num
==2){
res
=mul(t
,t
);
}else if(num
%2){
M tmp
=dg(t
,num
/2);
M tmp2
=mul(tmp
,ori
);
res
=mul(tmp
,tmp2
);
}else{
M tmp
=dg(t
,num
/2);
res
=mul(tmp
,tmp
);
}
return res
;
}
int main()
{
cin
>>k
>>n
;
FOR(i
,0,k
-1) ori
.m
[i
][i
+1]=1;
FOR(i
,0,k
) ori
.m
[k
-1][i
]=1;
long long tt
=1;
c
[0]=1;
FOR(i
,1,k
){
c
[i
]=tt
;
tt
+=c
[i
];
}
M rr
=dg(ori
,n
);
long long res
=0;
FOR(i
,0,k
) res
+=rr
.m
[0][i
]*c
[i
];
cout
<<res
%MOD
<<endl
;
return 0;
}
