任意门：
背景
守望者-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
24
样例输出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，问到达终点的方案数；
解题思路：
很明显的DP，DP的转移方程也显而易见 F(N) = F(N-1)+F(N-2)+ ... + F(N-K);
找出递推式，很显然可以用矩阵来优化，并且系数为 1，So easy！
以为到这就解决问题了，太粗心啦，注意数据范围，注意数据精度！！！要用 long long
Ac code：
#include#include #include #include #define LL long longusing namespace std;const int MAXN = 11;const LL Mod = 7777777;int N, K;struct mat{ LL m[MAXN][MAXN];}base, tmp, ans;mat muti(mat a, mat b){ mat res; memset(res.m, 0, sizeof(res.m)); for(int i = 1; i <= K; i++) for(int j = 1; j <= K; j++){ if(a.m[i][j]){ for(int k = 1; k <= K; k++){ res.m[i][k] = (res.m[i][k] + a.m[i][j]*b.m[j][k])%Mod;// res.m[i][k] = res.m[i][k]%Mod; } } } return res;}mat qpow(mat a, int n){ mat res; memset(res.m, 0, sizeof(res)); for(int i = 1; i <= K; i++) res.m[i][i] = 1LL; while(n){ if(n&1) res = muti(res, a); n>>=1; a = muti(a, a); } return res;}int main(){ scanf("%d%d", &K, &N); memset(base.m, 0, sizeof(base.m)); base.m[0][1] = 1LL; for(int i = 1; i <= K; i++){ for(int j = 0; j < i; j++) base.m[i][1] += base.m[j][1]%Mod; } if(N <= K) printf("%lld\n", base.m[N][1]); else{ memset(tmp.m, 0, sizeof(tmp.m)); for(int i = 1; i < K; i++){ tmp.m[i][i+1] = 1LL; } for(int i = 1; i <= K; i++) tmp.m[K][i] = 1LL; tmp = qpow(tmp, N-K); mat ans = muti(tmp, base); printf("%lld\n", ans.m[K][1]%Mod); } return 0;}