大家好，又见面了，我是全栈君。
UVA 11551 – Experienced Endeavour
题意：给定一列数，每一个数相应一个变换。变换为原先数列一些位置相加起来的和，问r次变换后的序列是多少
思路：矩阵高速幂，要加的位置值为1。其余位置为0构造出矩阵，进行高速幂就可以
代码：
#include <cstdio>#include <cstring>const int N = 55;int t, n, r, a[N];struct mat { int v[N][N]; mat() {memset(v, 0, sizeof(v));} mat operator * (mat c) { mat ans; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) ans.v[i][j] = (ans.v[i][j] + v[i][k] * c.v[k][j]) % 1000; } } return ans; }};mat pow_mod(mat x, int k) { mat ans; for (int i = 0; i < n; i++) ans.v[i][i] = 1; while (k) { if (k&1) ans = ans * x; x = x * x; k >>= 1; } return ans;}int main() { scanf("%d", &t); while (t--) { scanf("%d%d", &n, &r); for (int i = 0; i < n; i++) scanf("%d", &a[i]); int x; mat Mat; for (int i = 0; i < n; i++) { scanf("%d", &x); int b; while (x--) { scanf("%d", &b); Mat.v[i][b] = 1; } } Mat = pow_mod(Mat, r); for (int i = 0; i < n; i++) { int ans = 0; for (int j = 0; j < n; j++) { ans = (ans + a[j] * Mat.v[i][j]) % 1000; } printf("%d%c", ans, (i == n - 1 ? '\n' : ' ')); } } return 0;}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/115544.html原文链接：https://javaforall.net
