HDU [P5015] 233 Matrix

矩阵快速幂

按列递推
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cmath>

#include <cstring>

#define ll long long

using namespace std;

const int MOD = 10000007;

int n, m;

struct Matrix {

	ll num[15][15];

	void clear() {

		memset(num, 0, sizeof(num));

	}

	void unit() {

		clear();

		for(int i = 0; i <= n + 1; i++) num[i][i] = 1;

	}

	Matrix operator * (const Matrix & b) {

		Matrix ans;

		ans.clear();

		for(int i = 0; i <= n + 1; i++) {

			for(int j = 0; j <= n + 1; j++) {

				ll tmp = 0ll;

				for(int k = 0; k <= n + 1; k++) {

					tmp += num[i][k] * b.num[k][j];

				}

				ans.num[i][j] = tmp % MOD;

			}

		}

		return ans;

	}

	Matrix operator ^ (ll k) {

		Matrix ans, tt = (*this);

		ans.unit();

		while(k) {

			if(k & 1ll) ans = ans * tt;

			tt = tt * tt;

			k >>= 1;

		}

		return ans;

	}

	void print() {

		for(int i = 0; i <= n + 1; i ++) {

			for(int j = 0; j <= n + 1; j++) {

				printf("%lld ", num[i][j]);

			}

			printf("\n");

		}

	}

};

int main() {

	while(~scanf("%d %d", &n, &m)) {

		Matrix a, b;

		a.clear(); b.clear();

		for(int i = 0; i <= n + 1; i++) {

			if(i <= n) a.num[i][0] = 10;

			a.num[i][n + 1] = 1;

		}

		for(int i = 1; i <= n; i++) {

			for(int j = 1; j <= i; j++) {

				a.num[i][j] = 1;

			}

		}

		b.num[0][0] = 23; b.num[n + 1][0] = 3;

		for(int i = 1; i <= n; i++) scanf("%lld", &b.num[i][0]);

		b = (a ^ m) * b;

		cout << b.num[n][0] << endl;

	}

	return 0;

}
巴特西

HDU [P5015] 233 Matrix

矩阵快速幂

最新文章

热门文章
