[关闭]
@natsumi 2017-03-26T13:22:42.000000Z 字数 1118 阅读 882

魔力手环 矩阵快速幂

Algorithms


作者:NotDeep
链接:https://www.nowcoder.com/discuss/22696?type=0&order=0&pos=4&page=2
来源:牛客网

分析

把手环数字转为一个向量,然后乘

  1. [1 1 0 0 0]
  2. [0 1 1 0 0]
  3. [0 0 1 1 0]
  4. [0 0 0 1 1]
  5. [1 0 0 0 1]

这个矩阵N次即可。。用个矩阵快速幂,边算边求模。

代码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. void mult(int A[50][50], int B[50][50], int C[50][50], int n) {
  4. int T[50][50];
  5. memset(T, 0, sizeof(T));
  6. for(int i = 0; i < n; i++) {
  7. for(int j = 0; j < n; j++) {
  8. for(int k = 0; k < n; k++) {
  9. T[i][j] = (T[i][j] + A[i][k] * B[k][j]) % 100;
  10. }
  11. }
  12. }
  13. memcpy(C, T, sizeof(T));
  14. }
  15. void mypower(int A[50][50], int R[50][50], int n, int m) {
  16. if(n == 0) {
  17. memset(R, 0, sizeof(int) * 2500);
  18. for(int i = 0; i < m; i++) R[i][i] = 1;
  19. } else if(n % 2 == 0) {
  20. mypower(A, R, n/2, m);
  21. mult(R, R, R, m);
  22. } else {
  23. mypower(A, R, n - 1, m);
  24. mult(A, R, R, m);
  25. }
  26. }
  27. vector<int> solve(vector<int> seq, int m) {
  28. int A[50][50], R[50][50], n = (int)seq.size();
  29. memset(A, 0, sizeof(A));
  30. for(int i = 0; i < n; i++) A[i][i] = A[i][(i + 1) % n] = 1;
  31. mypower(A, R, m, n);
  32. vector<int> res;
  33. for(int i = 0; i < n; i++) {
  34. int sum = 0;
  35. for(int j = 0; j < n; j++) sum = (sum + R[i][j] * seq[j]) % 100;
  36. res.push_back(sum);
  37. }
  38. return res;
  39. }
  40. int main () {
  41. int n, k;
  42. vector<int> x;
  43. cin >> n >> k;
  44. for(int i = 0; i < n; i++) {
  45. int tmp; cin >> tmp;
  46. x.push_back(tmp);
  47. }
  48. vector<int> ans = solve(x, k);
  49. for(int i = 0; i < ans.size(); i++) i == 0 ? cout << ans[i] : cout << " " << ans[i];
  50. return 0;
  51. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注