一道使用矩阵加速的DP

状态转移方程: $dp_i=dp_{i-1}+dp_{i-2}+dp_{i-3}\cdots dp_{i-k}$

蒟蒻的代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 7777777;
int n, l;
struct arr {
	int x;
	int a[15][15];
	arr() {memset(a, 0, sizeof a);}
	void print() {
		for (int i = 1; i <= l; i++) {
			for (int j = 1; j <= l; j++) {
				printf("%lld ", a[i][j]);
			}
			printf("\n");
		}
	}
	arr operator*(const arr& T) const {//重定义乘法
		arr ans;
		for (int i = 1; i <= l; i++) {
			for (int j = 1; j <= l; j++) {
				for (int k = 1; k <= l; k++) {
					ans.a[i][j] += a[i][k] * T.a[k][j];
					ans.a[i][j] %= mod;
				}
			}
		}
		return ans;
	}
};
arr ans, base;
void init(int k) {
	for (int i = 1; i < k; i++) {
		base.a[i][i + 1] = 1;
	}
	for (int i = 1; i <= k; i++) {
		base.a[k][i] = 1;
		ans.a[i][i] = 1;
	}
}
void arrpow(int k) {
	while (k) {
		if (k & 1) ans = ans * base;
		base = base * base;
		k = k >> 1;
	}
}
signed main() {
	scanf("%lld", &l);
	scanf("%lld", &n);
	if (n <= l) {
		printf("1");
		return 0;
	}
	memset(ans.a, 0, sizeof ans.a);
	memset(base.a, 0, sizeof base.a);
	init(l);
	arrpow(n - l + 1);
	int anss = 0;
	ans.print();
	for (int i = 1; i <= l; i++) {
		anss += ans.a[i][1];
		anss %= mod;
	}
	printf("%lld", anss % mod);
	return 0;
}

hack数据：

2 4

5