[Vijos1067]Warcraft III 守望者的烦恼（DP + 矩阵优化）

可知

f[i] = f[i - 1] + f[i - 2] + ... + f[i - k]

直接矩阵优化就好了

#include <cstdio>

#include <cstring>

#define p 7777777

#define LL long long

int n, k;

struct Matrix

{

	int n, m;

	LL a[11][11];

	Matrix()

	{

		n = m = 0;

		memset(a, 0, sizeof(a));

	}

};

inline Matrix operator * (Matrix x, Matrix y)

{

	int i, j, k;

	Matrix ans;

	ans.n = x.n;

	ans.m = y.m;

	for(i = 1; i <= x.n; i++)

		for(j = 1; j <= y.m; j++)

			for(k = 1; k <= y.n; k++)

				ans.a[i][j] = (ans.a[i][j] + x.a[i][k] * y.a[k][j]) % p;

	return ans;

}

inline Matrix operator ^ (Matrix x, int y)

{

	int i;

	Matrix ans;

	ans.n = ans.m = k;

	for(i = 1; i <= k; i++) ans.a[i][i] = 1;

	for(; y; y >>= 1)

	{

		if(y & 1) ans = ans * x;

		x = x * x;

	}

	return ans;

}

int main()

{

	int i;

	Matrix ans, sum;

	scanf("%d %d", &k, &n);

	ans.m = ans.a[1][1] = 1;

	sum.n = sum.m = ans.n = k;

	for(i = 1; i <= k; i++) sum.a[1][i] = 1;

	for(i = 2; i <= k; i++) sum.a[i][i - 1] = 1;

	sum = sum ^ n;

	ans = sum * ans;

	printf("%lld\n", ans.a[1][1]);

	return 0;

}