1790.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1790 on 2006-09-10 at 17:55:08 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 128, MOD = 10000;

void powMatrix(int[][N], int, int);
void mul(int[][N], int[][N], int);

int main()
{
	int m[N][N], n, f, v[N], b[N];

	while(scanf("%d", &n) != EOF && n != 0) {
		for(int i = 0; i < n; i++) scanf("%d", &v[i]);
		for(int i = 0; i < n; i++) scanf("%d", &b[i]);
		scanf("%d", &f);
		if(f < n) { printf("%d\n", v[f]); continue; }
		for(int i = 0; i < n-1; i++)
			for(int j = 0; j < n; j++)
				m[i][j] = (j == i+1) ? 1 : 0;
		for(int i = 0; i < n; i++) m[n-1][i] = b[n-1-i];
		powMatrix(m, f-n+1, n);
		int r = 0;
		for(int i = 0; i < n; i++) r = (r+m[n-1][i]*v[i])%MOD;
		printf("%d\n", r);
	}
	
	return 0;
}

void powMatrix(int m[][N], int f, int n)
{
	int a[N][N], i; memcpy(a, m, sizeof(int)*N*n);
	for(i = 31; i >= 0; i--)
		if(f&(1<<i)) break;
	for(i--; i >= 0; i--) {
		mul(m, m, n);
		if(f&(1<<i)) mul(m, a, n);
	}
}
void mul(int a[][N], int b[][N], int n)
{
	int c[N][N] = { 0 };
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			for(int k = 0; k < n; k++)
				c[i][j] = (c[i][j]+a[i][k]*b[k][j])%MOD;
	memcpy(a, c, sizeof(int)*N*n);
}