记录编号	600725	评测结果	AAAAAAAAAA
题目名称	[UVa 10870] 递推关系	最终得分	100
用户昵称	对立猫猫对立	是否通过	通过
代码语言	C++	运行时间	0.535 s
提交时间	2025-05-12 20:13:17	内存使用	3.86 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#define ll long long
using namespace std;
ll d, n, m;
struct qty {
	ll f[16][16];
	qty() {
		memset(f, 0, sizeof(f));
	}
} a, b;
inline qty operator *(qty a, qty b) {
	qty c;
	for (int i = 0; i < d; i++)
		for (int j = 0; j < d; j++)
			for (int k = 0; k < d; k++)
				c.f[i][j] = (c.f[i][j] + (a.f[i][k] * b.f[k][j]) % m) % m;
	return c;
}
int main() {
	freopen("recurrences.in", "r", stdin);
	freopen("recurrences.out", "w", stdout);
	while (scanf("%lld%lld%lld", &d, &n, &m) == 3) {
		if (n == 0 && d == 0 && m == 0)break;
		a = qty();
		b = qty();
		for (int i = 0; i < d; i++)
			scanf("%lld", &b.f[0][i]);
		for (int i = 1; i < d; i++)
			b.f[i][i - 1] = 1;
		for (int i = 0; i < d; i++)
			scanf("%lld", &a.f[d - i - 1][0]);
		qty ans;
		for (int i = 0; i < d; i++)ans.f[i][i] = 1;
		if (n <= d) {
			printf("%lld\n", a.f[0][d - n] % m);
			continue;
		}
		n -= d;
		while (n) {
			if (n & 1)ans = ans * b;
			b = b * b;
			n /= 2;
		}
		ans = ans * a;
		printf("%lld\n", ans.f[0][0]);
	}
}