魔力手环-网易互联网2017在线笔试题目

所有解答

特别是魔力手环那个题目，解答方法看得我只有膜拜。

特此记录，备忘以及时不时地来膜拜一下。

#include <bits/stdc++.h>

using namespace std;

void mult(int A[50][50], int B[50][50], int C[50][50], int n) {
	//C=A*B，A/B/C的大小均为n*n
	int T[50][50];
	memset(T, 0, sizeof(T));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				T[i][j] = (T[i][j] + A[i][k] * B[k][j]) % 100;
			}
		}
	}
	memcpy(C, T, sizeof(T));
}
void mypower(int A[50][50], int R[50][50], int n, int m) {
	//求解矩阵A的n次快速幂，结果存入R，A和R是m*m的方阵
	if (n == 0) {
		memset(R, 0, sizeof(int) * 2500);
		for (int i = 0; i < m; i++) R[i][i] = 1;
	}
	else if (n % 2 == 0) {
		mypower(A, R, n / 2, m);
		mult(R, R, R, m);
	}
	else {
		mypower(A, R, n - 1, m);
		mult(A, R, R, m);
	}
}
vector<int> solve(vector<int> seq, int m) {
	int A[50][50], R[50][50], n = (int)seq.size();
	memset(A, 0, sizeof(A));
	for (int i = 0; i < n; i++) A[i][i] = A[i][(i + 1) % n] = 1;
	mypower(A, R, m, n);
	vector<int> res;
	for (int i = 0; i < n; i++) {
		int sum = 0;
		for (int j = 0; j < n; j++) sum = (sum + R[i][j] * seq[j]) % 100;
		res.push_back(sum);
	}
	return res;
}
int main() {
	int n, k;
	vector<int> x;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		int tmp; cin >> tmp;
		x.push_back(tmp);
	}
	vector<int> ans = solve(x, k);
	for (int i = 0; i < ans.size(); i++) i == 0 ? cout << ans[i] : cout << " " << ans[i];
	return 0;
}