Всем доброго времени суток, задача такая: Найти элемент произведения (с заданными i и j) какого-то количества матриц. При вычислении произведения применяется следующее правило - если результат операции выходит большим либо равным некоторого простого числа P (часть входных данных), то результат этой операции заменяется на остаток от деления на число P. Задача отсюда, под буквой C.
Проблема во времени выполнения - я написал некоторый код, выполняющийся верно, однако вычисление всего произведения занимает слишком много времени. Кажется, нужно считать только необходимую часть матричного произведения, но я не могу понять, какую именно. Подскажите, пожалуйста!
Входные данные:
3 2
1 2
239
1 2
3 4
4 2
1 3
1 2
2 1
Выходные данные:
20
Написанная мной программа:
#include <iostream>
#include <iomanip>
using namespace std;
void Nullify(int matrix[][201], int n)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
matrix[i][j] = 0;
}
}
}
void Multiple(int mat1[][201], int mat2[][201], int mat3[][201], int n, int p)
{
Nullify(mat3, n);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
for (int k = 1; k <= n; k++)
{
mat3[i][j] += ((mat1[i][k] * mat2[k][j]) % p);
mat3[i][j] %= p;
}
}
}
}
void InputMatrix(int matrix[][201], int n)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> matrix[i][j];
}
}
}
int main()
{
int currentMatrix[201][201] = { 0 };
int result[201][201] = { 0 };
int temp[201][201] = { 0 };
int quanity;
int n;
int x, y;
int p;
cin >> quanity >> n;
cin >> x >> y;
cin >> p;
bool flag = true;
InputMatrix(temp, n);
for (int i = 0; i < quanity - 1; i++)
{
InputMatrix(currentMatrix, n);
if (flag)
{
Multiple(temp, currentMatrix, result, n, p);
flag = false;
}
else
{
Multiple(result, currentMatrix, temp, n, p);
flag = true;
}
}
if (flag)
{
cout << temp[x][y];
}
else
{
cout << result[x][y];
}
}