算法日常练习8

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;

vector<vector<int>> operator*(const vector<vector<int>>& A,
                              const vector<vector<int>>& B) {
	int n = A.size();
	vector<vector<int>> ans(n, vector<int>(n, 0));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				long long temp = (long long)A[i][j] * B[j][k] % MOD;
				ans[i][k] = (temp + ans[i][k]) % MOD;
			}
		}
	}
	return ans;
}

vector<vector<int>> fast_pow(vector<vector<int>> &x, int y) {
	vector<vector<int>> ans(x.size(), vector<int>(x.size(), 0)), xx(x);
	for (int i = 0; i < x.size(); i++) ans[i][i] = 1;
	while (y) {
		if (y & 1) ans = ans * xx;
		xx = xx * xx;
		y >>= 1;
	}
	return ans;
}

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> src(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> src[i][j];
		}
	}
	auto ans = fast_pow(src, m);
	for (auto& arr : ans) {
		for (auto& i : arr) cout << i << ' ';
		cout << endl;
	}
	return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int n, m;
int ans = 0;

vector<vector<int>> arr;

int fast_pow(int x, int y) {
	int ans = 1;
	while (y) {
		if (y & 1) ans *= x;
		x *= x;
		y >>= 1;
	}
	return ans;
}

void dfs(int cur_depth, int cur_sum) {
	if (cur_depth == n) {
		if (cur_sum == 0) ans++;
		return;
	}
	for (int i = 1; i <= m; i++) {
		dfs(cur_depth + 1, 
            cur_sum + fast_pow(i, arr[cur_depth][1]) * arr[cur_depth][0]);
	}
}

int main() {
	cin >> n >> m;
	arr.resize(n, vector<int>(2));
	for(int i = 0; i < n; i++) {
		cin >> arr[i][0] >> arr[i][1];
	}
	dfs(0, 0);
	cout << ans << endl;
	return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int main() {
	int n;
	while (cin >> n) {
		if (n == 1) {
			int a;
			cin >> a;
			cout << a << endl;
			continue;
		}
		vector<int> arr(n + 1);
		for (auto& i : arr) cin >> i;
		if (arr[0] == -1 || arr[0] == 1) {
			if (arr[0] == -1) cout << '-';
		} else cout << arr[0];
		if (n == 1) cout << 'x';
		else cout << "x^" << n;
		for (int i = 1; i <= n; i++) {
			if (arr[i] == 0) continue;
			else if (arr[i] == 1 || arr[i] == -1) {
				cout << (arr[i] == -1 ? '-' : '+');
				if (i == n) {
					cout << abs(arr[i]);
					continue;
				}
			} else {
				if (arr[i] < 0) cout << arr[i];
				else cout << '+' << arr[i];
				if (i == n) continue;
			}
			if (i == n - 1) cout << 'x';
			else cout << "x^" << n - i;
		}
		cout << endl;
	}
	return 0;
}

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

int get_digs(ll src) {
	int ans = 0;
	do ans++; while (src /= 10);
	return ans;
}

ll get_r(ll src, int digs) {
	ll ans = 0;
	vector<int> nums;
	for (int i = 0; i < digs; i++) {
		nums.push_back(src % 10);
		src /= 10;
	}
	ll base = 1;
	for (int i = nums.size() - 1; i >= 0; i--, base *= 10) {
		ans += nums[i] * base;
	}
	return ans;
}

ll get_l(ll src, int digs) {
	ll ans = 0;
	vector<int> nums;
	for (int i = 0; i < digs; i++) {
		nums.push_back(src % 10);
		src /= 10;
	}
	sort(nums.begin(), nums.end(), greater<int>());
	ll base = 1;
	for (int i = nums.size() - 1; i >= 0; i--, base *= 10) {
		ans += nums[i] * base;
	}
	return ans;
}

int main() {
	ll n;
	while (cin >> n) {
		int digs = get_digs(n);
		vector<ll> nums{n};
		set <ll> s{n};
		ll l = get_l(n, digs), r = get_r(l, digs), cur = l - r;
		while (!s.count(cur)) {
			nums.push_back(cur);
			s.insert(cur);
			l = get_l(cur, digs), r = get_r(l, digs), cur = l - r;
		}
		int i = 0;
		while (i < nums.size() && nums[i] != cur) i++;
		for (; i < nums.size(); i++) {
			cout << nums[i] << ' ';
		}
		cout << endl;
	}
	return 0;
}