UVa 11551 - EXPERIENCED ENDEAVOUR

/*
 * EXPERIENCEDENDEAVOUR.cpp
 *
 *  Created on: ??‏/??‏/????
 *      Author: Mamdouh
 */
 
#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <sstream>
#include <algorithm>
#include <cstring>
#include <math.h>
#define MAX  1000007;
#define PI acos(-1)
using namespace std;
int T, n, r, v, col;
int **arr;
int **mat;
int mod = 1000;
 
int** multiply(int** a, int** b, int len) {
	int** c;
	c = new int*[len];
	for (int i = 0; i < len; i++)
		c[i] = new int[len];
	for (int i = 0; i < len; i++)
		for (int j = 0; j < len; j++)
			c[i][j] = 0;
	for (int i = 0; i < len; i++) {
		for (int j = 0; j < len; j++) {
			for (int k = 0; k < len; k++) {
				c[i][j] += a[i][k] * b[k][j];
				c[i][j] %= mod;
			}
		}
	}
	return c;
}
 
int** matPow(int** m, int pow, int len) {
	if (pow == 1) {
		return m;
	}
	int** power = matPow(m, pow / 2, len);
	power = multiply(power, power, len);
	if (pow % 2) {
		power = multiply(power, m, len);
	}
	return power;
}
int main() {
	cin >> T;
	while (T--) {
		cin >> n >> r;
		arr = new int*[n];
		for (int i = 0; i < n; i++)
			arr[i] = new int[n];
		mat = new int*[n];
		for (int i = 0; i < n; i++)
			mat[i] = new int[n];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				arr[i][j] = 0;
		for (int i = 0; i < n; i++)
			cin >> arr[0][i];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				mat[i][j] = 0;
		for (int i = 0; i < n; i++) {
			cin >> v;
			for (int j = 0; j < v; j++) {
				cin >> col;
				mat[col][i] = 1;
			}
		}
		int** rank = matPow(mat, r, n);
		int** res = multiply(arr, rank, n);
		for (int i = 0; i < n; i++) {
			cout << res[0][i];
			if (i == n - 1)
				cout << endl;
			else
				cout << " ";
		}
	}
	return 0;
}